CC++ & Algorithm

递归优化策略——别让程序“卡住”

较难3
语言版本：C++Python
概述：通过记忆化和改写成迭代，让递归更快，避免重复计算和栈溢出。

递归优化两步走：记忆化与迭代，别让程序“卡住”

递归是一种很“聪明”的编程方式——它让代码自己调用自己，把大问题拆成小问题。比如算台阶数、分糖果、倒着数数，用递归写起来特别清晰。但是递归有两个“小毛病”：重复计算和栈溢出。

  • 重复计算：同一个子问题被反复算很多遍，浪费时间。比如算一个数，可能算了成百上千次相同的计算，就像你每天重复做一样的作业，效率很低。
  • 栈溢出：递归调用一层套一层，如果层数太多（比如超过1000层），电脑内存会“装满”，程序会崩溃报错。

这一节，我们就来学两种常用的优化方法，让递归跑得又快又稳，不再“卡住”。

问题：斐波那契数列的重复计算

先看一个经典例子——斐波那契数列。数列是这样的：0, 1, 1, 2, 3, 5, 8, 13……每个数等于前两个数之和。用递归写起来很简单：

def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

试试算 fib(40)，运行一下，你会发现它慢得像蜗牛爬，甚至会等上好几秒。这到底是为什么？
因为递归像一棵树，每次分裂成两个子问题。算 fib(5) 时，fib(3) 被算了两次，fib(2) 被算了五次……数字越大，重复的次数像山一样堆起来。比如 fib(40) 总共需要算超过3亿次，当然慢了。

生活中的例子：假如你要统计全班同学零花钱的总和，但你不直接加，而是分两组：先算第1到第10个同学的和，再算第11到第20个同学的和。分完组后，你又把每个组再分……结果同一个同学被重复统计了好几次，浪费了大量时间。递归的重复计算也是这个道理。

优化1：记忆化（Memoization）——抄作业的小本本

既然算过的结果会被反复用到，那我们就像抄作业一样，把算过的结果记在“小本本”上。下次再需要时，直接翻本子查，不用重新算。这个“小本本”可以是字典，也可以直接用 Python 自带的装饰器 @lru_cache。

方法1：手动用字典缓存

cache = {}  # 缓存字典，记录已经算过的结果

def fib_memo(n):
    if n in cache:            # 如果结果已经在缓存中
        return cache[n]      # 直接返回，不用再算
    if n <= 1:
        result = n
    else:
        result = fib_memo(n-1) + fib_memo(n-2)
    cache[n] = result        # 把新结果记到小本本上
    return result

print(fib_memo(100))  # 瞬间算出，结果是354224848179261915075

手动写字典的好处是你能清楚看到缓存怎么工作，但每次都要写检查代码。更省事的方法是使用 Python 标准库里的装饰器。

方法2：用 @lru_cache 装饰器（推荐）

lru_cache 是 functools 模块里的一个工具，它会自动帮我们把结果缓存起来，用法就像给函数贴个标签。

from functools import lru_cache

@lru_cache(maxsize=None)  # maxsize=None 表示缓存不设上限
def fib_fast(n):
    if n <= 1:
        return n
    return fib_fast(n-1) + fib_fast(n-2)

print(fib_fast(100))  # 瞬间输出结果

加上 @lru_cache 后，每个 n 只计算一次，后面的调用直接读缓存。运行速度从好几秒变成了瞬间。就像你有一本随时自动更新的“答案本”，再也不用重复计算。

生活中的例子：老师让你每天抄写100个单词。第一天你老老实实全写一遍；第二天老师又让抄一样的100个单词，如果你已经有昨天的本子，直接复制过去，是不是快得多？记忆化就是那个“本子”。

优化2：改成迭代（循环）——扔掉递归包袱

递归虽然好写，但每调用一次函数，电脑都要准备一块临时空间放参数、变量。层数一多，这些临时空间堆叠起来，就会占满内存，导致“栈溢出”。另一种解决方法是把递归改成循环。循环没有函数调用开销，也不会占据栈空间，特别适合像斐波那契这样可以顺次计算的问题。

斐波那契的迭代版本：

def fib_iterative(n):
    a, b = 0, 1          # a是第0项，b是第1项
    for _ in range(n):   # 循环n次
        a, b = b, a + b  # 每次往后推一项：新的a变成原来的b，新的b变成a+b
    return a             # 循环结束后a就是第n项

print(fib_iterative(100))  # 结果和上面一样

优点：

  • 没有重复计算，不会栈溢出。
  • 运行速度甚至比记忆化递归更快，因为少了函数调用的额外成本。

生活中的例子：排队买冰淇淋，队伍很长（相当于递归层数深）。如果每个人都要拍前面人的肩膀让他传话，容易出错又慢（递归）。但如果你从头开始一个个数过去，直接走到队尾（迭代），就简单多了。迭代就是这种“一步步往前走”的方法。

常见错误与注意事项

  1. 忘记设置递归深度限制
    Python 默认递归深度是1000层。如果你试图用递归算一个深度为2000的问题（比如某些复杂的树结构），程序会报错：RecursionError: maximum recursion depth exceeded。虽然可以用 sys.setrecursionlimit(10000) 调整深度，但调太高容易导致程序崩溃（内存耗尽），所以能用迭代就用迭代。

  2. 记忆化但忘了正确存储
    新手可能写成：

    def fib_bad(n):
    cache = {}          # 每次调用都新建一个空字典！缓存永远没存住
    if n in cache: ...

    这样缓存每次递归都会清空，完全没效果。正确做法：把 cache 定义在函数外部，或者作为全局变量，或者用装饰器自动管理。

  3. 误以为记忆化可以解决一切递归问题
    记忆化只解决“重复子问题”的情况。如果递归像“汉诺塔”那样没有重复，记忆化就不会提速。另外，记忆化仍然占用额外内存（缓存），如果 n 非常大（比如 10^7），缓存可能太大，导致内存不足。

  4. 迭代时变量顺序写错
    在循环里，我们写 a, b = b, a + b。如果写成 a = b; b = a + b，那么 a 被修改后，b 用的 a 已经是新的值了，结果全错。Python 的元组赋值可以同时更新，避免了这个错误。

完整可运行示例

下面把三种方法（原始递归、记忆化递归、迭代）放在一起，并分别测试 n=35 的运行时间，让你直观感受差别。

import time
from functools import lru_cache

# 原始递归（很慢）
def fib_raw(n):
    if n <= 1:
        return n
    return fib_raw(n-1) + fib_raw(n-2)

# 记忆化递归（带缓存）
@lru_cache(maxsize=None)
def fib_fast(n):
    if n <= 1:
        return n
    return fib_fast(n-1) + fib_fast(n-2)

# 迭代版（循环）
def fib_iterative(n):
    a, b = 0, 1               # a是第0项，b是第1项
    for _ in range(n):
        a, b = b, a + b       # 每次往后推一步
    return a

# 测试 n=35，观察时间
n = 35

start = time.time()
result1 = fib_raw(n)
time1 = time.time() - start
print(f"原始递归：fib({n}) = {result1}，耗时 {time1:.3f} 秒")

start = time.time()
result2 = fib_fast(n)
time2 = time.time() - start
print(f"记忆化递归：fib({n}) = {result2}，耗时 {time2:.6f} 秒")

start = time.time()
result3 = fib_iterative(n)
time3 = time.time() - start
print(f"迭代版：fib({n}) = {result3}，耗时 {time3:.6f} 秒")

运行结果（大概）：

  • 原始递归：几秒甚至十几秒（n再大点电脑会卡住）
  • 记忆化递归：少于 0.001 秒
  • 迭代版：也少于 0.001 秒

两种优化方法都能让你瞬间得到答案，再也不用等得着急。

学完这些，你还可以看看

  • 动态规划（DP）：记忆化递归实际上是动态规划的一种实现方式（自顶向下）。如果你想更系统地学习解这类问题，可以看看“背包问题”“最短路径”等。
  • 尾递归：在某些语言里，尾递归可以被自动优化成循环（Python 不支持）。但你可以了解这个概念，帮助你理解递归的结构。
  • 递归树分析：学会画递归树，能帮你直观看出重复计算的位置，也能帮你决定是否需要优化。

记住：递归是思维的“放大镜”，让我们看清问题的结构；而优化是程序员的“小扳手”，让代码跑得又快又稳。试着用今天学到的方法，去优化你以前写的递归小项目吧！

例题精讲

1单选题

对于计算斐波那契数列第n项（n较大），直接使用朴素递归（不优化）与使用记忆化递归相比，时间复杂度分别是多少？

AO(2^n) 和 O(n)
BO(n^2) 和 O(n)
CO(2^n) 和 O(n^2)
DO(n) 和 O(log n)
2判断题

将递归算法改写成迭代算法一定能解决栈溢出问题，且运行效率一定更高。

3填空题
下面是一个使用记忆化递归计算斐波那契数列的函数，请补全代码。
def fib(n, memo):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = ___
    return memo[n]
4单选题

以下哪种策略不属于递归优化的常用方法？

A记忆化（缓存子问题结果）
B尾递归优化（使用递推代替回归）
C将递归改写成迭代（手写栈）
D增加递归深度限制（sys.setrecursionlimit）
5填空题
下面的递归函数计算阶乘，请将其改写成迭代版本。
递归版本：
def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n-1)

迭代版本：
def factorial_iter(n):
    result = 1
    for i in range(___, n+1):
        result *= i
    return result