尾递归是函数最后一步调用自身且直接返回其结果，可被优化为循环以节省内存；但CPython不支持尾递归优化（TCO），需改用迭代、缓存或显式栈等Python原生优化手段。
什么是尾递归，它为什么能优化递归函数
尾递归是指函数的最后一个操作是调用自身，且该调用的返回值直接作为当前函数的返回值，中间不进行任何额外计算。这种结构让编译器或解释器有机会将递归调用“替换”为循环，避免不断压栈，从而节省内存、防止栈溢出。
Python 解释器（CPython）**不支持尾递归优化**（TCO），这是语言设计上的选择——强调可读性和调试友好性，而非极致性能。所以即使你写出符合尾递归定义的函数，Python 依然会逐层建栈。但理解尾递归逻辑，是转向迭代实现的关键桥梁。
如何把尾递归写法改造成等价的迭代代码
核心思路：用变量显式保存“递归状态”，用 while 循环 替代函数调用。每次循环相当于一次递归调用，更新参数变量即模拟传入新参数。
- 识别原递归函数中的“状态变量”（如累加器、索引、剩余数据）
- 将这些变量初始化为初始递归参数
- 用 while 循环判断终止条件（对应原递归的 base case）
- 在循环体内更新状态变量，不调用自身，而是继续下一轮循环
例如阶乘的尾递归写法：
立即学习“Python免费学习笔记（深入）”；
def fact_tail(n, acc=1):
if n return acc
return fact_tail(n-1, n * acc)
对应迭代版：
def fact_iter(n):
acc = 1
while n > 1:
acc = n * acc
n = n - 1
return acc
不是所有递归都适合转尾递归或迭代，分清适用场景
适合转化的：线性递归（单分支）、有明确累积过程的问题，比如求和、阶乘、最大公约数、列表遍历、二叉树深度优先的简单变体。
难转化或不建议硬转的：
- 树形/分支多的递归（如二叉树中序遍历、N 皇后），需手动模拟调用栈，代码反而更复杂
- 依赖回溯路径的问题（如全排列、路径搜索），迭代需显式维护栈结构，可读性下降
- 问题本身天然递归（如分治算法），强行迭代可能掩盖逻辑本质
此时优先考虑优化递归本身：加缓存（@lru_cache）、限制深度、改用生成器延迟计算。
Python 中真正实用的递归优化手段
既然不能靠尾递归优化，就用 Python 生态里靠谱的办法：
- 对重复子问题，无脑加
@functools.lru_cache()，时间复杂度常能从指数降到多项式 - 用
sys.setrecursionlimit()谨慎提高上限（仅限必要场景，如解析深层嵌套 JSON），但不解决根本问题 - 对大数据量线性递归，直接重写为迭代——结构清晰、内存稳定、速度更快
- 对深度不确定的结构（如 AST、DOM 遍历），用显式栈 + while 循环，完全避开系统调用栈限制
记住：优化目标不是“看起来像尾递归”，而是让程序跑得稳、快、易维护。在 Python 里，多数时候，一个干净的 while 循环比费力模拟 TCO 更值得写。
