递归是一种函数调用自身的编程技巧，常用于解决具有“自相似”结构的问题，如树遍历、分治算法、数学递推等。Python 完全支持递归，但它在递归深度和性能上有明确的限制，并且不提供尾递归优化，我们需要了解这些局限并知道如何应对。
递归的基本形态
一个典型的递归函数包含两个部分：
- 基准条件：终止递归的出口，避免无限调用。
- 递归步骤：将问题分解为更小的子问题并调用自身。
例如，计算阶乘：
def factorial(n):
if n == 0: # 基准条件
return 1
return n * factorial(n - 1) # 递归步骤递归的优点是代码简洁，与数学定义高度一致；缺点是每一次函数调用都会消耗栈空间，调用过深会导致栈溢出。
Python 的递归深度限制
为了避免栈溢出导致解释器崩溃，Python 对递归深度做了硬性限制。可以通过 sys.getrecursionlimit() 查看默认值（通常为 1000）。当递归超过这个深度时，会抛出 RecursionError。
import sys
print(sys.getrecursionlimit()) # 1000
def deep(n):
if n == 0:
return
deep(n - 1)
deep(2000) # RecursionError: maximum recursion depth exceeded虽然可以用 sys.setrecursionlimit() 调大上限，但这只是权宜之计，因为操作系统对 C 栈的大小也有硬性限制，且过深的递归会导致栈帧过载、性能严重下降，甚至导致解释器崩溃。所以不要依赖调大限制来根本解决问题。
尾递归与优化原理
尾递归是递归的一种特殊形式：递归调用是函数执行的最后一条语句，且返回值直接就是递归调用的结果（不再需要进行额外计算）。前面的 factorial(5) 不是尾递归，因为在递归调用后还要乘以 n。改成尾递归版本需要引入累加器：
def factorial_tail(n, acc=1):
if n == 0:
return acc
return factorial_tail(n - 1, acc * n) # 最后一步是递归调用，无额外运算尾递归的好处是：理论上编译器或解释器可以将其优化成循环，重用当前栈帧而不新增栈空间，从而避免栈溢出。这种技术叫做尾递归优化（Tail Call Optimization, TCO）。
Python 为何不支持尾递归优化？
尽管尾递归看起来很诱人，CPython 官方解释器不实现，也明确表示不会实现尾递归优化。原因包括：
- 破坏调试体验：尾递归优化会丢弃中间的栈帧，导致异常回溯信息不完整，调试时链式调用看不清。
- Python 的哲学：Guido van Rossum 认为尾递归优化不是 Pythonic 的做法，他更倾向于鼓励开发者用循环来代替递归，这样代码更清晰、更可控。
- 实现复杂性：Python 的动态特性（如
try/finally、异常、sys._getframe()等）使得正确实现 TCO 非常困难。 - 不符合习惯：Python 对函数式编程的深层次支持有限，循环和生成器表达式通常是更自然的选择。
因此，在 Python 中写尾递归不会获得任何性能或内存上的优势，它和普通递归一样会不断增加栈帧深度。
递归过深的实用解决方案
当你遇到需要深层递归的场景（例如遍历很深的嵌套结构、大规模分治算法）时，有几种可靠的替代方案：
1. 改为迭代或显式栈
绝大多数递归都可以用循环 + 显式栈（list 模拟栈）来改写。例如，深度优先遍历一棵深层树：
# 递归版本（有深度风险）
def dfs_recursive(node):
if node is None:
return
print(node.val)
dfs_recursive(node.left)
dfs_recursive(node.right)
# 迭代版本（使用栈，无栈溢出风险）
def dfs_iterative(root):
stack = [root]
while stack:
node = stack.pop()
if node is None:
continue
print(node.val)
stack.append(node.right) # 注意顺序以模拟递归
stack.append(node.left)迭代版本完全不受递归深度限制，只受可用内存限制，这是最推荐的方式。
2. 使用 functools.lru_cache 消除重复计算
对于具有重叠子问题的递归（如斐波那契数列），缓存已经计算过的结果可以大幅减少递归次数，但无法降低最大深度。这时最好还是改写为循环。
3. 在不得不使用深递归且能控制数据规模时，临时调大递归深度
仅仅在某些算法竞赛、处理已知规模较小的递归（如遍历一个深度不超过 2000 的目录树）时，可以谨慎调大限制。生产代码中不推荐。
4. 使用生成器模拟递归
某些场景下，可以用生成器的惰性求值特性来模拟递归过程，例如遍历一棵树并不需要一次性将所有栈帧堆叠。
现实中的大部分场景不需要深层递归
Python 中常见的递归用途（如 JSON 解析、遍历文件系统、简单分治算法）深度通常远低于 1000。如果发现递归深度接近极限，往往意味着算法设计就有问题，应该反思数据结构和处理逻辑，转向迭代或流式处理。
总之，在 Python 里写递归时记住两个要点：
- 时刻留意数据规模，不要让递归深度接近默认限制。
- 把递归当成“表达问题的一种方式”，而不是“必须这样解决”的手段；一旦可能深度过大，果断改写为迭代版本。