如何在Python中用函数计算斐波那契数列

斐波那契数列是一种非常常见的数列，被用于各种数学问题中。其定义如下：

- 第0项为0，第1项为1；

- 从第二项开始，每一项都等于前两项之和。

前几项数列如下：

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ...

在Python中，我们可以用函数来计算斐波那契数列。下面是几种不同的实现方式。

## 1. 递归解法

递归是一种很自然的方式来实现斐波那契数列。可以用以下的代码来实现：

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

这个函数定义了一个fib(n)函数，表示第n个斐波那契数。如果n小于等于1，返回n本身；否则，返回前两个斐波那契数的和。这个递归函数的时间复杂度为$O(2^n)$，因为每次调用都会产生两次递归调用。

## 2. 迭代解法

递归的效率比较低，因为每次调用都会产生函数调用的开销。我们可以用迭代的方式来避免这个问题：

def fib(n):
    a, b = 0, 1
    for i in range(n):
        a, b = b, a+b
    return a

这个函数使用了两个变量$a$和$b$来保存前两个斐波那契数，然后一个循环依次计算后面的斐波那契数。这种方式的时间复杂度是$O(n)$，效率比递归高很多。

## 3. 缓存解法

斐波那契数列有一个特点，那就是每个数只依赖于前两个数。也就是说，如果我们已经计算出了前面的数，我们就不需要重复计算，可以把它们缓存起来，以便以后使用。这就是缓存解法。

def fib(n, cache={0: 0, 1: 1}):
    if n not in cache:
        cache[n] = fib(n-1, cache) + fib(n-2, cache)
    return cache[n]

这个函数使用了一个字典来缓存已经计算出来的斐波那契数。如果需要计算的数已经在缓存中，直接返回即可；否则，计算并把结果存入缓存。这种方式能够避免重复计算，时间复杂度为$O(n)$。