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?”
Python Knowledge Base: Make coding great again.
- Updated:
2024-11-20 by Andrey BRATUS, Senior Data Analyst.
Classical recursion case.
One line lambda recursion.
Closed formula - Golden ratio.
Dynamic programming case.
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.
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]
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
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
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