什么是斐波那契数列？

想象一下，有一对小兔子，一个月后长大成年，两个月后开始生育，每月生一对小兔子。新出生的小兔子也遵循同样的规律。那么，每个月兔子的总数会是多少呢？ 这就是斐波那契数列的经典模型。

斐波那契数列是一个由 0 和 1 开始的数列，后续的每一项都等于前两项之和。用数学公式表示就是：

• F(0) = 0
• F(1) = 1
• F(n) = F(n-1) + F(n-2) (n > 1)

所以，斐波那契数列的前几项是：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

方法一：递归实现

递归是一种函数调用自身的方法。使用递归实现斐波那契数列非常简洁，代码如下：

def fibonacci_recursive(n):
    """使用递归计算斐波那契数列的第n项"""
    if n <= 1:
        return n
    else:
        return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

# 示例：计算斐波那契数列的第10项
result = fibonacci_recursive(10)
print(f"斐波那契数列的第10项是: {result}")

代码解释：

• fibonacci_recursive(n) 函数接受一个整数 n 作为输入，表示要计算斐波那契数列的第 n 项。
• 如果 n 小于等于 1，则直接返回 n (因为 F(0) = 0, F(1) = 1)。
• 否则，递归调用 fibonacci_recursive(n-1) 和 fibonacci_recursive(n-2)，并将结果相加返回。

递归的优缺点：

• 优点： 代码简洁易懂，符合斐波那契数列的数学定义。
• 缺点： 效率非常低。因为在计算过程中会存在大量的重复计算。例如，计算 fibonacci_recursive(5) 时，会计算 fibonacci_recursive(4) 和 fibonacci_recursive(3)，而 fibonacci_recursive(4) 又会计算 fibonacci_recursive(3) 和 fibonacci_recursive(2)。这样，fibonacci_recursive(3) 就被计算了多次。当 n 很大时，会导致 堆栈溢出 的风险，程序可能会崩溃。

方法二：迭代实现

迭代是使用循环来逐步计算结果的方法。使用迭代实现斐波那契数列效率更高，代码如下：

def fibonacci_iterative(n):
    """使用迭代计算斐波那契数列的第n项"""
    if n <= 1:
        return n
    a, b = 0, 1  # 初始化两个变量 a 和 b，分别存储前两项的值
    for _ in range(2, n + 1):
        a, b = b, a + b  # 更新 a 和 b 的值
    return b

# 示例：计算斐波那契数列的第10项
result = fibonacci_iterative(10)
print(f"斐波那契数列的第10项是: {result}")

代码解释：

• fibonacci_iterative(n) 函数接受一个整数 n 作为输入，表示要计算斐波那契数列的第 n 项。
• 如果 n 小于等于 1，则直接返回 n (因为 F(0) = 0, F(1) = 1)。
• 初始化两个变量 a 和 b，分别存储斐波那契数列的前两项的值，即 a = 0 和 b = 1。
• 使用 for 循环从 2 迭代到 n。在每次迭代中，更新 a 和 b 的值。a, b = b, a + b 的意思是：将 b 的值赋给 a，将 a + b 的值赋给 b。这样，a 和 b 就分别存储了斐波那契数列的当前项和下一项的值。
• 循环结束后，b 中存储的就是斐波那契数列的第 n 项的值，将其返回。

迭代的优缺点：

• 优点： 效率高，不会出现堆栈溢出的问题。
• 缺点： 代码相对递归来说，稍微复杂一些。

扩展：使用生成器优化斐波那契数列

生成器是一种特殊的迭代器，可以按需生成值，而不是一次性生成所有值。使用生成器可以更有效地利用内存，尤其是在需要计算斐波那契数列的前N项时。

def fibonacci_generator(n):
    """使用生成器生成斐波那契数列的前n项"""
    a, b = 0, 1
    for _ in range(n):
        yield a  # 使用 yield 关键字返回当前值
        a, b = b, a + b

# 示例：生成斐波那契数列的前10项
for num in fibonacci_generator(10):
    print(num, end=" ")
print()

代码解释：

• fibonacci_generator(n) 函数接受一个整数 n 作为输入，表示要生成斐波那契数列的前 n 项。
• 初始化两个变量 a 和 b，分别存储斐波那契数列的前两项的值，即 a = 0 和 b = 1。
• 使用 for 循环迭代 n 次。在每次迭代中，使用 yield 关键字返回当前 a 的值。yield 关键字会将函数暂停，并将当前值返回给调用者。下次调用时，函数会从上次暂停的位置继续执行。

练习题

1. 编写一个函数，计算斐波那契数列的前N项，并将结果存储在一个列表中。
2. 编写一个函数，判断一个数是否属于斐波那契数列。

希望这篇文章能帮助你理解斐波那契数列以及如何使用Python实现它。祝你编程愉快！