尾递归改造核心是将递归调用变为函数最后动作，通过累加器参数传递中间结果，避免回溯计算；如阶乘中用acc累积乘积，fib可引入两个参数保存前两项实现线性时间复杂度。
递归函数改造成尾递归，核心是把“等待返回后再计算”的逻辑，变成“边递归边累积结果”，让递归调用成为函数体的最后一个动作。Python 本身不自动优化尾递归，但改造过程对理解算法结构、避免栈溢出、甚至转成循环都极有帮助。
尾递归的关键改造原则
不是所有递归都能直接改，但满足“线性分解”特征的（如阶乘、斐波那契、倒序打印）基本都可以。关键看两点：
-
原递归是否在递归调用后还做运算？比如
return n * factorial(n-1)中，factorial(n-1)返回后还要乘n—— 这就不是尾递归； - 能否把中间状态通过参数传递下去？尾递归靠额外参数（常称“累加器”或“acc”）携带当前计算结果，每一步只更新参数，不再依赖上层栈帧。
阶乘：从普通递归到尾递归
原始写法（非尾递归）：
def factorial(n):<br> if n == 0: return 1<br> return n * factorial(n - 1) # 乘法在递归调用之后，需保留当前帧
尾递归改写（引入累加器 acc）：
def factorial(n, acc=1):<br> if n == 0: return acc<br> return factorial(n - 1, n * acc) # 递归调用是最后一行，且结果直接返回
调用方式不变：factorial(5) → 返回 120。本质是把 n × (n−1) × … × 1 的乘积过程，从“回溯时累积”改为“下探时累积”。
斐波那契：为什么普通递归低效？怎么改成尾递归？
原始递归（指数级重复计算）：
def fib(n):<br> if n return fib(n-1) + fib(n-2)
它每次调用都分裂两个分支，fib(5) 会算 fib(3) 两次、fib(2) 三次……时间复杂度 O(2ⁿ)。
尾递归版本（用两个参数记录前两项）：
def fib(n, a=0, b=1):<br> if n == 0: return a<br> if n == 1: return b<br> return fib(n - 1, b, a + b)
例如 fib(5) 执行路径：fib(5,0,1) → fib(4,1,1) → fib(3,1,2) → fib(2,2,3) → fib(1,3,5) → 5
每步只递归一次，时间复杂度降为 O(n)，且无重复子问题。
其他常见算法迁移要点
不是所有递归都适合尾递归，但以下类型可优先尝试：
-
求和/求积类（如 1 到 n 求和）：加一个
acc参数，每次把当前值加进去； -
字符串反转：用
acc累积已处理字符，每次取首字符拼到acc前面； - 链表遍历/查找：传入当前节点和累加结果（如计数、拼接），递归走到下一个节点；
- 注意避坑：树的深度优先遍历（如二叉树中序）天然含“回溯处理”，无法单次尾递归完成，需用栈模拟或改迭代。
本质上，尾递归改造是把隐式的调用栈显式地挪到函数参数里——这一步做完，离写成 while 循环也就差一层纸了。
