Python函数实现递归斐波那契数列

斐波那契数列是一个非常经典的数列， 个和第二个数字均为1，之后的数字为前两个数字的和。即，斐波那契数列的定义如下：

F(1) = 1

F(2) = 1

F(n) = F(n-1) + F(n-2) for n > 2

我们可以使用递归的方式来实现斐波那契数列。递归是一种在函数定义中使用函数自身的方法，递归函数会不断调用自身，直到达到某个终止条件停止。在使用递归实现斐波那契数列时，可以使用上述数列的定义作为终止条件。

下面是使用Python实现递归斐波那契数列的代码：

def fibonacci(n):
    # 终止条件
    if n <= 0:
        return "输入的数字必须大于0"
    elif n == 1 or n == 2:
        return 1
    # 递归调用
    else:
        return fibonacci(n-1) + fibonacci(n-2)

在这段代码中，我们定义了一个名为fibonacci的递归函数，该函数接受一个参数n表示所求斐波那契数列的第n项。首先，我们设置了两个终止条件：若n小于等于0，则返回错误提示；若n等于1或2，则返回1。然后，我们使用递归调用，返回fibonacci(n-1) + fibonacci(n-2)。

接下来，我们可以测试一下这个函数：

print(fibonacci(1))  # 1
print(fibonacci(2))  # 1
print(fibonacci(3))  # 2
print(fibonacci(4))  # 3
print(fibonacci(5))  # 5

这些测试应该输出斐波那契数列的对应项的值。

然而，这个递归实现的斐波那契数列有一个非常大的问题，那就是效率非常低。每次调用fibonacci(n)函数时，它会分别调用fibonacci(n-1)和fibonacci(n-2)，然后再将这两个结果相加。这意味着同一个项可能被多次计算，造成了大量的重复计算。

为了解决这个问题，我们可以使用动态规划的方法，将每个计算过的项存储起来，避免重复计算。这样可以大大提高斐波那契数列的计算效率。

下面是使用动态规划实现斐波那契数列的代码：

def fibonacci(n):
    # 初始化存储计算结果的列表
    fib_list = [0] * (n+1)
    fib_list[1] = 1
    fib_list[2] = 1
    # 从第3项开始计算并存储结果
    for i in range(3, n+1):
        fib_list[i] = fib_list[i-1] + fib_list[i-2]
    return fib_list[n]

在这段代码中，我们使用了一个长度为n+1的列表fib_list来存储每个项的计算结果。首先，我们将前两个项设为1，然后从第3项开始，通过循环计算并存储每个项的值。

同样，我们可以测试一下这个函数：

print(fibonacci(1))  # 1
print(fibonacci(2))  # 1
print(fibonacci(3))  # 2
print(fibonacci(4))  # 3
print(fibonacci(5))  # 5

这些测试应该输出斐波那契数列的对应项的值。

总结：

递归是实现斐波那契数列的一种简单方法，但是效率较低，会有大量的重复计算。为了提高效率，可以使用动态规划的方法，将每次计算的结果存储起来，避免重复计算。希望本文的解答对你有帮助！