博客

要实现斐波那契数列的函数，可以使用递归或迭代的方式，下面分别介绍两种方法的代码实现。

递归实现

斐波那契数列的递推公式为：f(n) = f(n-1) + f(n-2)，其中f(0) = 0，f(1) = 1。

根据递推公式，我们可以写出递归函数fibonacci：

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

函数中实现了以下逻辑：

• 如果n小于0，返回None；
• 如果n等于0，返回0；
• 如果n等于1，返回1；
• 否则，递归求解f(n-1)和f(n-2)的值，并返回它们的和。

这个递归函数能够正确地计算斐波那契数列的值，但是它的效率很低，因为会存在大量的重复计算。例如，计算fibonacci(5)需要计算fibonacci(4)和fibonacci(3)，而计算fibonacci(4)需要再次计算fibonacci(3)，重复计算了一次。

迭代实现

上面的递归实现可以使用迭代来优化。我们可以使用循环来依次计算斐波那契数列的值，而不需要重复计算。

def fibonacci(n):
    if n < 0:
        return None
    elif n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        a, b = 0, 1
        for i in range(2, n+1):
            a, b = b, a+b
        return b

这里我们使用了两个变量a和b来保存计算过程中的中间值。初始化时，a=0，b=1。然后使用循环计算每个斐波那契数列的项的值，并依次更新a和b的值。计算完成后，返回变量b的值即为所求。

这个迭代实现可以避免重复计算，因此效率更高。它的时间复杂度是O(n)，空间复杂度是O(1)。