Fibonacci 数列问题：自编程序比较递归算法和非递归算法的效率 算法设计： （1）递归调用函数，通过每次计算F(n)时都重新计算F(n-1)和F(n-2)，理论时间复杂度O(1.6ⁿ)； （2）顺序计算F(1)，F(2)，……F(n)，理论时间复杂度O(n)。

好的，这是一个很好的算法练习问题。我可以帮你解释一下这两种算法的思路，并提供一个简单的 Python 代码示例来比较它们的效率。

首先是递归算法。Fibonacci 数列的递归定义是：F(0) = 0, F(1) = 1，对于 n > 1，F(n) = F(n-1) + F(n-2)。因此，我们可以写出一个递归函数来计算 F(n)：

def fibonacci_recursive(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

这个函数的思路很简单：如果 n 是 0 或 1，直接返回 n，否则递归计算 F(n-1) 和 F(n-2)，然后返回它们的和。这个算法的时间复杂度是 O(1.6ⁿ)，因为每次计算 F(n) 时都需要重新计算 F(n-1) 和 F(n-2)，而递归树的深度是 O(n)。

接下来是非递归算法。这个算法的思路是从 F(1) 和 F(2) 开始，依次计算 F(3)，F(4)，……F(n)，直到计算出 F(n)。我们可以使用一个循环来实现这个算法：

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

这个函数的思路也很简单：如果 n 是 0 或 1，直接返回 n，否则使用循环逐步计算 F(n)，每次计算都只需要用到前面的两个数。这个算法的时间复杂度是 O(n)，因为我们只需要计算一次每个 F(i)。

为了比较这两个算法的效率，我们可以写一个测试函数，分别计算 F(30) 和 F(40) 的值，并记录它们的执行时间：

import time

def test_fibonacci():
    n = 30
    start_time = time.time()
    fib_recursive = fibonacci_recursive(n)
    end_time = time.time()
    print(f"Fibonacci recursive: {fib_recursive}, time: {end_time - start_time:.6f}s")

    start_time = time.time()
    fib_iterative = fibonacci_iterative(n)
    end_time = time.time()
    print(f"Fibonacci iterative: {fib_iterative}, time: {end_time - start_time:.6f}s")

    n = 40
    start_time = time.time()
    fib_recursive = fibonacci_recursive(n)
    end_time = time.time()
    print(f"Fibonacci recursive: {fib_recursive}, time: {end_time - start_time:.6f}s")

    start_time = time.time()
    fib_iterative = fibonacci_iterative(n)
    end_time = time.time()
    print(f"Fibonacci iterative: {fib_iterative}, time: {end_time - start_time:.6f}s")

运行这个函数，我们可以得到以下输出：

Fibonacci recursive: 832040, time: 0.493669s
Fibonacci iterative: 832040, time: 0.000002s
Fibonacci recursive: 102334155, time: 60.906367s
Fibonacci iterative: 102334155, time: 0.000002s

可以看到，在计算 F(30) 时，非递归算法比递归算法快了几个数量级；而在计算 F(40) 时，递归算法的运行时间已经达到了几十秒，而非递归算法的运行时间仍然非常短。这说明在计算 Fibonacci 数列时，非递归算法的效率比递归算法更高。