Nombre de Fibonacci

Les nombres de Fibonacci sont la suite d’entiers (OEIS A000045) F(n) qui obéit à la récurrence suivante :

F(n) = F(n-1) + F(n-2)

Pour F(0) = 0, F(1) = 1, la série ainsi formée est 0, 1, 1, 2, 3, 5, 8, 13, 21, …

Les nombres de Fibonacci apparaissent dans plusieurs domaines des mathématiques discrètes et des algorithmes.

Implémentation récursive naïve #

Les nombres de Fibonacci sont utilisés comme exemple très courant pour enseigner la récursivité.

fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)