The Fibonacci sequence can be motivated by the following scenario:
A newly born breeding pair of rabbits are put in a field; each breeding pair mates at the age of one month, and at the end of their second month they always produce another pair of rabbits; and rabbits never die, but continue breeding forever.
This problem can be described by the recurrence relation
with initial conditions
Close-Form Solution
Main: Binet’s Formula
The close form solution of the Fibonacci numbers is given by the Binet’s Formula:
where
Info
Since
, Fibonacci numbers converges to for large and the ratio of consecutive Fibonacci numbers converges to the golden ratio .
In Programming
A recursive implementation of the Fibonacci numbers directly translated from the recurrence relation is highly inefficient, but it is still often used as a benchmark for programming languages performing computationally intensive tasks or as a demonstration of parallel algorithms.
def fib(n):
if n < 2:
return n
else:
return fib(n - 1) + fib(n - 2)
While we can make this implementation efficient with memoization, a iterative approach also exists:
def fib(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a+b
return a
For computing very large Fibonacci numbers, we can also use the close-form solution.