Python 时间复杂度为 O(n) 的斐波那契递归（而不是迭代）？

Question

我知道我的 Python 斐波那契算法的简单版本的时间复杂度为 O(2^n)^2:

def fibonacci_naive(n):
    if n < 0:
        return None
    if n == 0 or n == 1:
        return 0
    if n == 2:
        return 1
    return fibonacci_naive(n - 1) + fibonacci_naive(n - 2)

我正在尝试编写另一个 Fibonacci 递归，但复杂度为 O(n)。到目前为止，我可以想到如何用一个简单的 for 循环来做到这一点，但我无法理解如何将它变成一个递归函数。感谢您的帮助！

def fibonacci_fast(n):
    if n < 0:
        return None
    if n == 0 or n == 1:
        return 0
    if n == 2:
        return 1
    fn_minus_2 = 0
    fn_minus_1 = 1
    for _ in range(2, n+1):
        temp = fn_minus_2 + fn_minus_1
        fn_minus_2 = fn_minus_1
        fn_minus_1 = temp
    return fn_minus_1

def fibonacci_fast(n, fn_minus_1=1, fn_minus_2=0):
    if n < 0:
        return None
    if n == 0 or n == 1:
        return 0
    if n == 2:
        return 1
    return fibonacci_fast(???)

Answer 1

您需要使用迭代过程，例如：

def fib_r(n, depth=2, minus_1=1, minus_2=0):
    if n == 0:
        return 0
    elif n == 1:
        return 1

    elif depth < n:
        return fib_r(n=n, depth=depth+1, minus_1=minus_1 + minus_2, minus_2=minus_1)
    else:
        return minus_1 + minus_2

只是为了向您展示，这里是与使用迭代的版本进行比较，基本上，递归充当我们的循环：

In [1]: def fib(n):
   ...:     a, b = 0, 1
   ...:     for _ in range(n):
   ...:         a, b = b, a+b
   ...:     return a
   ...:

In [6]: def fibr(n, depth=2, a=1, b=0):
   ...:     if n == 0:
   ...:         return 0
   ...:     elif n == 1:
   ...:         return 1
   ...:     elif depth < n:
   ...:         return fibr(n=n, depth=depth+1, a=a+b, b=a)
   ...:     else:
   ...:         return a + b
   ...:
   ...:
    
In [3]: all(fib(i) == fibr(i) for i in range(1000))
Out[3]: True

因此，每个人都应该阅读 Ableson 和 Sussman 的 Structure and Interpretation of Computer Programs。

事实上，麻省理工学院免费提供PDF：

https://web.mit.edu/alexmv/6.037/sicp.pdf

开始阅读第 1.2.1 节，了解线性递归过程与迭代递归过程（有效的解决方案）以及图递归（这是朴素、低效的解决方案所使用的）。

Answer 2

我想你可以从中学到更多 post:

How to write the Fibonacci Sequence?

不过我还是要分享一个代码。

def fibonacci(n): 
      
    f = [0, 1] #first two nummber as 0, 1
     
    for i in range(2, n+1): #for i from range 2 to n+1
        f.append(f[i-1] + f[i-2])
    return f[n]

P/S：如果我没记错的话，递归斐波那契总是 O(2^n) / 指数

Answer 3

您可以使用默认参数来向前移动序列并使用递归来递减元素数量：

def fibo(N,a=0,b=1): return fibo(N-1,b,a+b) if N else a

您可以使用相同的方法获取序列的前 N 个值：

def fibo(N,a=0,b=1): return [a] + fibo(N-1,b,a+b) if N else []

Python 时间复杂度为 O(n) 的斐波那契递归（而不是迭代）？

Python Fibonacci recursion (and not iteration) with O(n) time?

python

recursion

fibonacci