## Fibonacci sequence generation.

Leonardo Fibonacci was a great Italian mathematician famous for providing an answer to the question : “How many pairs of rabbits are obtained in a year, excluding cases of death, supposing that each couple gives birth to another couple every month and that the youngest couples are able to reproduce already at the second month of life?”

The Fibonacci sequence is a pretty famous sequence of integer numbers which comes up naturally in many problems and has a nice recursive definition. In programmers world Fibonacci sequence used to study recursion.

The formula is simple: F(n) = F(n-1) + F(n-2) and F(1) = F(2) = 1.

## Classical recursion case.

The most common and oldschool algorithm to generate the Fibonacci sequence is a recursive function that calls itself as many times as needed until it computes the desired Fibonacci number.

``````
def fibonacci_of(n):
if n in {0, 1}:  # Base case
return n
return fibonacci_of(n - 1) + fibonacci_of(n - 2)  # Recursive case

[fibonacci_of(n) for n in range(15)]
``````

OUT: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]

## One line lambda recursion.

Very simple realisation but can be very slow for a large number of N.

``````
fib = lambda n: fib(n - 1) + fib(n - 2) if n > 2 else 1
fib(10)
``````

OUT: 55

## Closed formula - Golden ratio.

Relatively simple and efficient for low number of N, quite esthetic math and rather ugly programming example.

``````
from __future__ import division
import math

def fib(n):
SQRT5 = math.sqrt(5)
PHI = (SQRT5 + 1) / 2
return int(PHI ** n / SQRT5 + 0.5)

fib(11)
``````

OUT: 89

## Dynamic programming case.

Still simple and efficient for low number of N, easy to remember case and really beautiful code example.

``````
def fib(n):
a = 0
b = 1
for __ in range(n):
a, b = b, a + b
return a

fib(6)
``````

OUT: 8