python编程之斐波那契数列递归算法

斐波那契数列从第3项起等于前两项之和，Python中可用递归实现：当n≤1时返回n，否则返回fibonacci(n-1)+fibonacci(n-2)。

斐波那契数列是一个经典的数学问题，它的规律是：从第3项开始，每一项都等于前两项之和。数列开头为 0, 1，之后依次是 1, 2, 3, 5, 8, 13……

用公式表示就是：
F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2) （当 n ≥ 2）

H3

在 Python 中，可以用递归方式直观地实现斐波那契数列：

def fibonacci(n):
    if n         return n
    else:
        return fibonacci(n-1) + fibonacci(n-2)

调用示例：

print(fibonacci(6))  # 输出 8

H3

这个函数的工作原理如下：

• 当 n 是 0 或 1 时，直接返回 n，这是递归的终止条件
• 否则，函数调用自身两次，分别计算前两个数的值并相加
• 这种写法结构清晰，贴近数学定义

H3

虽然递归写法简洁，但存在明显缺点：

• 重复计算多：比如计算 F(5) 时，F(3) 会被多次重复计算
• 时间复杂度高达 O(2^n)，随着 n 增大，执行时间急剧上升
• 当 n 较大时（如超过 35），程序会变得很慢

改进方案：

• 使用“记忆化递归”避免重复计算
• 或者改用循环方式实现，效率更高

例如加入缓存的记忆化版本：

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci(n):
    if n         return n
    return fibonacci(n-1) + fibonacci(n-2)

H3

递归实现斐波那契数列易于理解，适合初学者掌握递归思想。但在实际应用中要注意其性能缺陷。对于大数值计算，推荐使用记忆化或迭代方法提升效率。

基本上就这些，不复杂但容易忽略细节。