递归为什么会爆栈：主定理之外的工程现实

图：递归每层的调用帧占栈，过深则栈溢出；迭代只需常量栈

主定理给出的是时间复杂度，但它完全不关心栈空间。每次递归调用都会在调用栈上压一帧，深度为 $d$ 的递归就要占 $O(d)$ 栈。当 $d$ 与 $n$ 同阶（如链表递归、某些分治），栈高可能达到 $O(n)$，一旦超过栈上限就 栈溢出（stack overflow）。

递归 vs 迭代

同样的算法，迭代写法往往只需 $O(1)$ 栈（一个循环变量）。所以工程上常把尾递归改写成循环，或显式用栈/队列模拟递归，把 $O(n)$ 栈压成 $O(1)$。

参考代码：递归改迭代，避免爆栈

# 递归版（深度 n 时占 O(n) 栈，可能溢出）
def factorial_rec(n):
    return 1 if n <= 1 else n * factorial_rec(n - 1)

# 迭代版（仅占 O(1) 栈）
def factorial_iter(n):
    r = 1
    for i in range(2, n + 1):
        r *= i
    return r

print(factorial_iter(5))   # 120

经验法则：能用迭代/尾递归就别用深层线性递归；分治递归深度通常只有 $\Theta(\log n)$（如二分、归并），栈压力小，相对安全；但"每次减 1"的递归深度 $O(n)$，务必改写成循环。

关联推荐

• 二分查找：20 行代码里藏着的对数级智慧 — 递归深度仅 Θ(log n)，栈压力小
• 插入、选择、冒泡排序（KU） — 排序递推深度也是对数级
• 算法与问题求解入门（KU） — 递归作为算法基本思想