Computing nth Fibonacci number efficiently with Python

Question

I am currently learning Recursion with Micheal.T.Goodrich's "Algorithm and DataStructure with Python". The author suggests a better approach to computing the nth Fibonacci number using recursion without the space complexity of the usual approach. But I just can't wrap my head around the intuition of the program. Can someone explain this:

Normal Recursive function to find nth Fibonacci number

def Fibonacci(n):
    if n < = 1:
       return (n)
    else:
       return Fibonacci(n - 1) + Fibonacci (n - 2)

Optimized solution:

def Fibonnaci(n):
    if n <= 1:
       return (n, 0)
    else:
       (a, b) = Fibonacci(n - 1)
       return (a+b, a)

Can someone help me in understanding the optimized solution?

It seems like you can physically write out, on paper, what happens when n is 2 or 3. Alternatively add some print statements. — Mark, Aug 22 '20 at 06:31
The optimized solution is returning a pair of consecutive entries in the sequence, f(n) and f(n-1). That way it only needs to recurse once rather than twice. — Tom Karzes, Aug 22 '20 at 06:32

score 0 · Answer 1 · answered Aug 22 '20 at 06:34

Try looking at the second solution like this. For each row (except the base case) you are looking at (a+b, a) where a,b come from the row beneath it.

n=7 --> (8+5=13, 8)
n=6 --> (5+3=8, 5)
n=5 --> (3+2=5, 3)
n=4 --> (2+1=3, 2)
n=3 --> (1+1=2, 1)
n=2 --> (1+0=1, 1)
n=1 --> (1, 0)       // n <= 1

Fib sequence: {1, 1, 2, 3, 5, 8, 13}

Computing nth Fibonacci number efficiently with Python

1 Answers1