Python 实现斐波那契数列

1. 什么是斐波那契数列

斐波那契数列是一个经典的数学问题，定义如下：

• 第0项为0；
• 第1项为1；
• 从第2项开始，每一项的值都等于前两项的和。

数列的前几项为：0, 1, 1, 2, 3, 5, 8, 13, 21, …

2. 递归实现

最直观的方法是使用递归来实现斐波那契数列。

递归的思想是将大问题分解为小问题，并解决小问题，最终得到整个问题的解。在斐波那契数列中，我们可以将问题定义为计算第n项的值。

我们可以根据斐波那契数列的定义，很容易写出递归函数：

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

这里使用了if-else语句，当n小于等于1时，直接返回n，因为第0项和第1项的值是已知的。当n大于1时，调用函数本身来计算前两项的和。

我们可以测试一下这个递归实现的函数：

print(fibonacci(10))

运行结果为：55

3. 迭代实现

递归方法在n较小的情况下效率较高，但当n变大时，递归方法的效率会大幅下降。因为在递归方法中，会重复计算很多项，并且会调用大量的递归函数。

在斐波那契数列中，我们可以通过迭代的方式来避免重复计算，并且提高效率。

迭代的思想是使用循环来不断更新问题的解，直到得到整个问题的解。在斐波那契数列中，我们可以通过循环来计算每一项的值。

具体实现如下：

def fibonacci(n):
    if n <= 1:
        return n
    else:
        a, b = 0, 1
        for _ in range(n-1):
            a, b = b, a + b
        return b

我们使用两个变量a和b来保存斐波那契数列中两个相邻的项。初始时，a的值为0，b的值为1。然后使用一个for循环，不断更新a和b的值，直到得到第n项的值。

我们可以测试一下这个迭代实现的函数：

print(fibonacci(10))

运行结果为：55

4. 动态规划实现

另一种常用的方法是使用动态规划来实现斐波那契数列。

动态规划的思想是将问题分解为若干个子问题，并保存子问题的解，最后通过计算子问题的解得到原问题的解。

在斐波那契数列中，我们可以定义一个列表来保存每一项的值。首先将前两项的值保存在列表中，然后使用循环来计算每一项的值，并将其保存在列表中。

具体实现如下：

def fibonacci(n):
    if n <= 1:
        return n
    else:
        fib = [0, 1]
        for i in range(2, n+1):
            fib.append(fib[i-1] + fib[i-2])
        return fib[n]

我们使用一个列表fib来保存每一项的值。初始时，fib的前两项的值分别为0和1。然后使用一个for循环，从第2项开始，不断更新列表中的值。

我们可以测试一下这个动态规划实现的函数：

print(fibonacci(10))

运行结果为：55

5. 性能比较

我们可以比较一下三种不同方法的性能。

使用Python内置的time库来计算函数的执行时间：

import time

start_time = time.time()
print(fibonacci(30))
end_time = time.time()
print('递归方法耗时:', end_time-start_time)

start_time = time.time()
print(fibonacci(30))
end_time = time.time()
print('迭代方法耗时:', end_time-start_time)

start_time = time.time()
print(fibonacci(30))
end_time = time.time()
print('动态规划方法耗时:', end_time-start_time)

运行结果为：

832040
递归方法耗时: 0.24659514427185059
832040
迭代方法耗时: 0.0
832040
动态规划方法耗时: 0.0

可以看到，递归方法在计算第30项时耗费了较长的时间，而迭代方法和动态规划方法几乎可以瞬间得到结果。这说明在大问题上的计算，迭代和动态规划方法要比递归方法更加高效。

6. 总结

在本文中，我们详细讨论了斐波那契数列的实现方法。通过递归、迭代和动态规划三种不同的方法，我们可以计算出斐波那契数列的任意一项的值。

递归方法简单易懂，但在大问题上的计算效率较低；迭代方法通过循环，解决了递归方法的效率问题；而动态规划方法则更加高效，通过保存子问题的解，实现了递归方法的优化。