斐波那契数列递归与非递归实现的指定项计算及性能对比

以下实现默认数列下标从0开始，即第0项为0，第1项为1，以此类推，和题目给出的数列{0,1,1,2,3,5……}规则完全匹配。

实现代码（Python示例） #

递归实现 #

def fib_recursive(n):
    # 边界判断
    if n == 0:
        return 0
    if n == 1:
        return 1
    # 递归拆分计算
    return fib_recursive(n-1) + fib_recursive(n-2)

非递归（迭代）实现 #

def fib_iterative(n):
    # 边界判断
    if n == 0:
        return 0
    if n == 1:
        return 1
    # 维护前两项值遍历计算
    prev_prev, prev = 0, 1
    for _ in range(2, n+1):
        current = prev_prev + prev
        prev_prev = prev
        prev = current
    return prev

测试结果与耗时对比 #

测试环境：Python 3.10，Intel Core i5-12400 处理器，耗时取10次运行平均值：

性能差异分析 #

• 时间复杂度差异：普通未优化的递归实现时间复杂度为O(2ⁿ)，每计算一个项都会拆成两个子问题，存在海量重复计算，比如计算F(5)时会重复计算2次F(3)、3次F(2)，n越大重复计算量指数级暴涨；迭代实现时间复杂度为O(n)，仅需要从前往后遍历一次，没有任何重复计算，性能稳定。
• 空间复杂度差异：递归实现依赖函数调用栈运行，空间复杂度为O(n)，n过大会直接触发栈溢出报错；迭代实现仅需要维护2个临时变量存储前两项的值，空间复杂度为O(1)，额外内存消耗可以忽略。
• 适用场景差异：递归实现写法简洁、逻辑直观，仅适合用来学习递归原理，或者计算n<30的小数值项；迭代实现性能无明显短板，哪怕计算n=10000的项也能快速返回结果，是生产环境的首选方案。

内容的提问来源于stack exchange，提问作者Hasan Sarker Robin