一、递归实现斐波那契的初体验

很多刚接触编程的人，学完递归后第一个练的就是斐波那契数列——就是从第三项开始，每一项都等于前两项之和，比如1、1、2、3、5、8、13……用递归写这个逻辑特别直观：要算第n项，就先算出第n-1和第n-2项，把结果加起来就行。

1.1 第一个递归实现的代码

我用Python写个最基础的版本，大家一看就能懂：

# 定义递归函数，计算第n个斐波那契数
def fib(n):
    # 边界条件：第1、2项都是1，这是数列的初始设定
    if n == 1 or n == 2:
        return 1
    # 递归核心逻辑：第n项 = 第n-1项 + 第n-2项
    return fib(n-1) + fib(n-2)

# 测试：计算第6个斐波那契数，应该输出8
print(fib(6))

这个代码跑起来完全没问题，输出也对。但如果换成算第30项，你就会发现明显变慢了——这时候就得警惕，肯定是哪里出了问题。

二、排查痛点：重复计算的问题

为啥算大项会变慢？我们拆解递归的调用过程就清楚了。比如算第5项fib(5)，需要先算fib(4)和fib(3)；算fib(4)的时候，又要先算fib(3)和fib(2)——你看，fib(3)被算了两次！再算第6项fib(6)，fib(4)算1次，fib(3)算2次，fib(2)算3次，fib(1)算2次……越往后面，重复计算的次数会像滚雪球一样暴涨。

2.1 用计数器量化重复计算的数量

为了把这个痛点摆得更具体，我们给函数加个全局计数器，看看每一轮调用的总次数：

# 定义带计数的递归函数，用来统计总调用次数
count = 0
def fib_with_count(n):
    global count
    count +=1 # 每调用一次，计数器加1
    if n == 1 or n == 2:
        return 1
    return fib_with_count(n-1) + fib_with_count(n-2)

# 测试：计算第6项的总调用次数
count = 0
result = fib_with_count(6)
print(f"第6个斐波那契数是{result}，总调用次数是{count}")

跑这个代码你会发现，算第6项总调用了15次；换成算第10项，总调用次数直接飙到109次；算第20项更是达到了13529次！这指数级增长的调用次数，就是递归斐波那契最大的痛点：大量重复计算浪费了时间和资源，效率极低。

三、解决痛点：优化重复计算的方法

既然问题是「同一个数被反复算多次」，那核心解决思路就很简单：已经算过的数，就不用再算第二次，把结果存起来就行——这个方法叫「记忆化」，就像你做数学题时，已经算出过的答案不会再重新算一遍，直接抄就行。

3.1 用字典做记忆化的递归实现

我们可以用一个字典，把已经算过的斐波那契数存进去，下次要算的时候先查字典，有就直接返回，没有再计算：

# 定义带记忆化的递归函数，用字典存已算结果
memo = {1:1, 2:1} # 预存前两个数的结果，不用再算

def fib_memo(n):
    # 如果这个数已经在字典里，直接返回结果
    if n in memo:
        return memo[n]
    # 没算过的话，计算结果并存进字典，避免重复
    memo[n] = fib_memo(n-1) + fib_memo(n-2)
    return memo[n]

# 测试：计算第20项，看看总计算次数
print(fib_memo(20))
print(f"实际计算过的数有{len(memo)}个")

跑这个代码你会发现，算第20项的结果直接秒出，而且只计算了19次（从1到20），和之前的13529次比，效率提升了几百倍！

3.2 记忆化的进阶：用Python内置装饰器

其实Python还有更省事的方法，不用自己写字典，直接用内置的lru_cache装饰器，它会自动帮你缓存计算结果，特别适合懒癌开发者：

# 导入functools模块里的lru_cache装饰器
from functools import lru_cache

# 加装饰器，开启自动缓存功能
@lru_cache(maxsize=None) # maxsize=None表示缓存无上限
def fib_lru(n):
    if n == 1 or n == 2:
        return 1
    return fib_lru(n-1) + fib_lru(n-2)

# 测试：计算第30项，秒出结果
print(fib_lru(30))
# 查看缓存的数量，就是实际计算过的数的数量
print(f"缓存的数有{fib_lru.cache_info().currsize}个")

这个代码和手动写字典的效果一样，代码更短，可读性也更强。

四、相关的细节补充

4.1 应用场景

记忆化的思路不止用来优化斐波那契，只要是「分而治之」的递归问题，都会遇到重复计算的坑，比如求子集、排列组合、背包问题、最小路径和问题等，都可以用记忆化来提升效率。比如你写一个求网格最小路径和的递归函数，也会重复计算同一个格子的路径，加了记忆化后速度会大幅提升。

4.2 技术优缺点

先讲基础递归斐波那契：优点是写法简单，思路直观，刚学递归的时候很适合练手；缺点是效率极低，时间复杂度是指数级（O(2^n)），n稍微大一点就会卡，还会因为递归深度溢出（Python默认递归深度约1000）。 再讲记忆化递归：优点是把时间复杂度降到了线性级（O(n)），效率大幅提升；缺点是需要额外的空间存缓存，如果n特别大，缓存会占用一定内存，但一般场景下完全没问题。如果n超过1000，递归不管怎么优化都会溢出，这时候换迭代法更安全。

4.3 注意事项

用记忆化的时候有几个点要注意：第一，用全局字典做缓存时，要注意重置，比如你第一次算完n=20，第二次算n=10的话，字典里已经有结果，直接用没问题，但如果换了完全不同的计算场景，一定要手动清空字典，不然会出现脏数据；第二，用lru_cache的时候，函数参数不能是可变类型（比如列表），因为可变类型不能哈希，会导致缓存失效；第三，如果n特别大（比如10000），用迭代法更稳妥，迭代法没有递归深度问题，时间复杂度也是O(n)，空间复杂度是O(1)，比如：

def fib_iter(n):
    a, b = 1, 1
    # 从第3项开始，一步步算到第n项
    for _ in range(3, n+1):
        a, b = b, a + b
    return b

# 测试：算第1000项，秒出，不会溢出
print(fib_iter(1000))

五、文章总结

总的来说，递归实现斐波那契数列的核心痛点就是大量重复计算，排查的方法很简单——加计数器或者拆解递归调用树，就能直观看到同一个值被反复计算。解决的核心思路就是「记忆化」，把已经算过的结果存起来，避免重复计算，这是优化递归分治问题的通用方法。如果n不大，用手动字典或者内置装饰器都可以；如果n特别大，换成迭代法更安全高效。掌握这个思路，就能避免很多递归算法的常见坑，提升编程效率。