时间复杂度为O(n)的PythonFibonacci递归（而不是迭代）？

我知道我的 Python Fibonacci 算法的简单版本的时间复杂度为 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)

我正在尝试编写另一个斐波那契递归，但复杂度为 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(???)

回答

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

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