理解尾递归：累加器、执行过程与 Python 的优化边界
从待完成的加法判断尾递归，用状态表和不变量解释累加器，再区分代码形式、尾调用优化与 CPython 的实际行为。
从普通递归进入尾递归
本篇覆盖知识点 27—31。尾递归描述递归调用的位置，尾调用优化描述运行时是否能省去增长的调用状态；这两个概念必须分别判断。
知识点 27：最后一个操作，具体指什么
普通求和中的 return n + solve(n−1) 先等待子调用，再执行加法，最后返回。递归调用完成后，还有加法待做，因此不是尾递归。即使递归调用写在最后一行，也不能只看排版来判断。
return solve(n−1, acc+n) 则不同：调用参数在发起子调用前就求值完成；子调用的结果直接成为当前调用的返回结果。当前层没有依赖这个结果的算术工作，这就是尾递归形式。
| 代码形式 | 子调用返回后尚需执行 | 是否为尾递归 |
|---|---|---|
return 1 + solve(n−1) | 加 1，再返回 | 否 |
child = solve(n−1); return n * child | 绑定、乘法、返回 | 否 |
return solve(n−1, acc+n) | 直接把结果返回 | 是（这里的普通函数示例） |
如果还存在 finally 清理、异常处理等待完成工作，必须把它们纳入判断，不能从出现了 return 就断言一定可以消除当前调用状态。
知识点 28：把部分结果放进累加器参数
普通递归把每个 n 留在调用帧里，返回时再加起来。尾递归把已经完成的总和放进参数 acc，下一层接收剩余问题 n−1 与更新后的总和 acc+n。
下例约定 n 为非负整数，acc 为整数；默认调用 sum_tail(3) 得到 6，sum_tail(0) 得到 0。参数 acc 也可以理解为已有总和；sum_tail(3, 10) 将返回 16，而不是 6。
def sum_tail(n, acc=0):
if type(n) is not int or n < 0 or type(acc) is not int:
raise ValueError("n must be non-negative; acc must be an integer")
if n == 0:
return acc
return sum_tail(n - 1, acc + n)
print(sum_tail(3))
print(sum_tail(0))
print(sum_tail(3, 10))知识点 29：求和从返回阶段移到深入阶段
| 即将进入的调用 | 此时 acc 的含义 | 下一步 |
|---|---|---|
sum_tail(3, 0) | 尚未处理任何项 | 计算 0+3，进入 (2, 3) |
sum_tail(2, 3) | 已经处理 3 | 计算 3+2，进入 (1, 5) |
sum_tail(1, 5) | 已经处理 3、2 | 计算 5+1，进入 (0, 6) |
sum_tail(0, 6) | 所有项已处理 | 返回 6 |
深入时总和已经形成；返回时不再逐层相加。可以用不变量核验：acc + S(n) 始终等于初始总和目标。状态从 (n, acc) 变成 (n−1, acc+n) 后，acc+n+S(n−1)=acc+S(n)，所以总目标没有改变。
最后 n=0，剩余和 S(0)=0，所以 acc 就是答案。这解释了累加器为什么正确，而不仅是演示某几个输入恰好返回了相同数字。
知识点 30：优化为何可能减少栈帧
如果上一层已经没有待完成的工作，支持尾调用优化的运行时可以用新的参数替换当前调用状态，再继续执行函数，避免保留不断增长的调用链。对于每层只需要固定大小状态的这类求和，额外调用栈可以从线性增长降为常量。
这是一个优化机会，不是尾递归语法自动带来的结果。语言是否保证这种行为、实现是否支持、当前代码是否满足优化条件，都需要确认。调试栈、异常处理和清理语义也可能影响是否能够消除调用帧。
尾调用优化不会消除算法本身需要保存的数据。例如，传递一个不断扩大的列表，列表仍然占用空间；常量调用栈不等于整个程序只用常量字节。
知识点 31：CPython 不优化用户函数的尾调用
Python 官方在 3.14 说明中明确指出，CPython 没有实现 Python 函数的尾调用优化。因此，上面的 sum_tail 虽然已经是尾递归形式，仍然产生随 n 增长的调用状态，也仍受递归深度限制。
Python 3.14 提到的 tail-call interpreter，是解释器内部以小 C 函数执行操作码时使用的技术；它不会把用户函数的递归自动变成循环。这也不是打开某个 Python 选项就能获得的用户级尾递归优化。
运行 sys.getrecursionlimit() 可以查看当前解释器的限制，但不要把固定数字写成语言保证，也不能假定调用恰好在第 limit 层失败：环境中已有调用也占据深度。
依据：CPython 3.14 对尾调用的说明 ↗ · 递归限制 ↗。
在 Python 中把这份状态直接交给循环
尾递归的两个参数已经包含推进所需的信息，因此这个示例很容易改成 while：每轮更新 acc 和 n，n 为零时返回 acc。逻辑状态推进仍是 (n, acc) → (n−1, acc+n)，但下一轮复用同一次函数调用。
下面返回 6。按简单算术模型，它和递归求和都执行线性次数的加法；循环只保留固定数量的整数变量。Python 整数的实际字节数会随值增长，不能把“固定数量的变量”误写成任意 n 下内存字节绝对固定。
def sum_loop(n):
if type(n) is not int or n < 0:
raise ValueError("n must be a non-negative integer")
acc = 0
while n > 0:
acc += n
n -= 1
return acc
print(sum_loop(3))复盘：分别判断形式、优化与成本
- 为什么 return n + solve(n−1) 不是尾递归？
- sum_tail(3, 10) 的不变量是什么？
- 不做尾调用优化时，返回阶段没有加法，为什么仍需要保留调用帧？
- 尾递归是否自动避免重复子问题？
展开参考答案
子调用返回后还需加法；acc+S(n) 始终等于 16；CPython 仍按普通调用维护返回、局部状态和可观察调用链；尾递归位置不会自动缓存子问题。不要把尾递归、记忆化与运行时优化混为同一种机制。
下一篇将用递归树分析调用总数、深度与重复计算。
参数和表达式求值顺序：Python 求值顺序 ↗。不变量与复杂度是对本文代码的推导。
本系列的来源与许可
本篇是《Hello 算法》相关主题的重新组织与补充讲解。署名、修改说明及 CC BY-NC-SA 4.0 许可见 系列来源说明；对应知识点和官方依据均可从索引核验。