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

user_8849558 0
Viewed 376

I know my simple version of a Python Fibonacci algorithm has a time complexity of 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)

I'm trying to write another Fibonacci recursion, but with O(n) complexity instead. So far I can think of the how to do this with a simple for loop but I'm having trouble wrapping my head around how I can turn it into a recursive function instead. Any help is appreciated!

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(???)
fibonacci recursion python
3 Answers

You can have defaulted parameters that move the sequence forward and use recursion to count down the number of elements:

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

You can use the same approach to obtain the first N values of the sequence:

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

You need to use an iterative process, something like:

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

And just to show you, here it is compared to the version using iteration, basically, recursion acts as our loop:

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

So, everyone should read the Structure and Interpretation of Computer Programs by Ableson and Sussman.

Actually, MIT provides the PDF for free:

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

Start reading section 1.2.1 about linear recursive processes versus iterative recursive processes (the efficient solution), and also, graph recursion (which is what the naive, inefficient solution uses).

user_50144550

I suppose you can learn much more from this post:

How to write the Fibonacci Sequence?

But I'll share a code anyway.

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: If I'm not mistaken, recursive fibonacci will always be O(2^n) / exponential

user_152996830
Related