• 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.