如何优化递归实现的斐波那契数列代码以提升运行速度

问题1：提升递归斐波那契代码运行速度的方法 #

递归实现斐波那契的核心问题是大量重复计算，比如计算F(50)时，会重复计算F(48)、F(47)等无数次，时间复杂度达到O(2ⁿ)，导致运行极慢。可以通过以下几种方式优化：

方式1：记忆化缓存（缓存已计算结果） #

用字典或列表存储已经算出的斐波那契数，避免重复计算。示例代码：

# 用字典做缓存
fib_cache = {1: 1, 2: 1}

def fib(n):
    if n in fib_cache:
        return fib_cache[n]
    fib_cache[n] = fib(n-1) + fib(n-2)
    return fib_cache[n]

# 打印1到50项
for i in range(1, 51):
    print(fib(i))

方式2：改用迭代法（彻底避免递归开销） #

迭代法只维护最近两个斐波那契数，时间复杂度O(n)，空间复杂度O(1)（如果不需要保存所有项），速度远快于递归。示例代码：

def print_fib(n):
    a, b = 1, 1
    print(a)
    if n >= 2:
        print(b)
    for _ in range(3, n+1):
        c = a + b
        print(c)
        a, b = b, c

# 打印1到50项
print_fib(50)

方式3：尾递归优化（Python环境下不推荐） #

虽然尾递归可以消除递归栈的重复调用，但Python解释器默认不支持尾递归优化，实际使用中意义不大，这里不展开。

问题2：临时变量替换实现数列“前移”的可行性 #

这个思路完全可行，本质就是迭代法的核心逻辑：

• 初始时，用两个变量分别保存F(n-2)和F(n-1)（比如a=F(n-2)，b=F(n-1)）
• 计算当前项F(n) = a + b
• 然后将b的值赋给a（即F(n-1)变为新的F(n-2)），将F(n)的值赋给b（即新的F(n-1)）
• 重复这个过程，就相当于让数列的“窗口”不断向前移动，每次只保留最近两个值，极大节省空间。

如果一定要维护列表形式的“前移”，示例代码如下：

# 初始列表保存前两项
fib_list = [1, 1]
print(fib_list[0])
print(fib_list[1])

for _ in range(3, 51):
    # 计算新项
    next_fib = fib_list[0] + fib_list[1]
    print(next_fib)
    # 列表前移：把F(n-1)移到F(n-2)的位置，新项放在F(n-1)的位置
    fib_list[0] = fib_list[1]
    fib_list[1] = next_fib

这种方式和直接用两个变量的效率几乎一致，只是用列表存储了最近两项，实现了你说的“整体前移”效果。

内容的提问来源于stack exchange，提问作者umad