Python fibonacci sequence optimized 4 examples

John D K -

In this article we will have a look of:

  • simple Fibonacci with recursion
  • Fibonacci numbers with memoization and recursion
  • Fibonacci sequence with bottom-up and not recursion
  • Fibonacci by object and method

Fibonacci sequence basic example

The simplest is the closest to the definition for producing numbers of Fibonacci is:

def fib(i):
    if i <= 2:
        return 1;
    else:
        f = fib(i-1) + fib(i-2)
        print('calc', i)
    return f
print(fib(6))

result:

calc 3  calc 4  calc 3  calc 5  calc 3  calc 4  calc 6  
8

As you can see we are calculating some numbers several times. For example we are calculating 3 - 3 times which is a performance issue for bigger numbers. In order to improve the result we can use memoization which is part of dynamic programing.

Fibonacci numbers memoization example

Memoization will allow us to calculate each number in the sequence only once:

def fibMemo(i):
    if i in memo:
        return memo[i]
    if i <= 2:
        return 1;
    else:
        f = fibMemo(i-1) + fibMemo(i-2)
        memo[i] = f
    print('calc', i,  memo)
    return f
memo = {}
print(fibMemo(6))

result:

calc 3 {3: 2}
calc 4 {3: 2, 4: 3}
calc 5 {3: 2, 4: 3, 5: 5}
calc 6 {3: 2, 4: 3, 5: 5, 6: 8}
8

We are using hint for the values which are calculated already and we are saving calculations - for 3 we have only 1. Similar approach to this one is bottom-up approach which is not using recursion but for loop.

Fibonacci sequence with bottom-up

It's similar approach to memoization without using recursion. In some cases could be slightly better than memoization :


def fibBottom(i):
    fib = {}
    for k in range(i+1):
        if k <= 2: f = 1
        else:
            f = fib[k - 1] + fib[k - 2]
            print('calc', k , fib)
        fib[k] = f
    return fib[i]
print(fibBottom(6))

result:

calc 3 {0: 1, 1: 1, 2: 1}
calc 4 {0: 1, 1: 1, 2: 1, 3: 2}
calc 5 {0: 1, 1: 1, 2: 1, 3: 2, 4: 3}
calc 6 {0: 1, 1: 1, 2: 1, 3: 2, 4: 3, 5: 5}8}
8

Fibonacci numbers with class and method OOP

Using class and method is also fast and efficient way.:

class Fibon:
    old = 1
    fib = 1
    current = 1

    def next(self):
        print('calc', self.current , self.fib)
        newFib = self.fib + self.old;
        self.old = self.fib;
        self.fib = newFib;
        self.current+=1
        return fib;

fibon = Fibon()
while(fibon.current < 5):
    k = fibon.next()
print(fibon.fib)

result:

calc 1 1
calc 2 2
calc 3 3
calc 4 5 
8

You can check also this example in Java:

Java 8 fast non recursive Fibonacci

Benchmark of the methods

Simple test and bench mark for all four examples with Fibonacci 40 is giving me:

102334155 - bench simple took - 35742.329ms.
102334155 - bench memo took - 0.034ms.
102334155 - bench bottom - took 0.025ms.
102334155 - bench class - took 0.044ms.

as you can see the pure recursion is really slow and inefficient in comparison to the other methods.