Suite de Fibonacci

Introduction

Approche récursive naïve

Implémentation directe

La suite de Fibonacci, grand classique, peut s'implémenter de diverses façons. On peut d'abord s'y prendre naïvement, en collant à la définition même de la suite :

Fonction F(n)
    Si n <= 1
        Retourner 1
    Retourner F(n - 1) + F(n - 2)
 
Soit n = Lire
Afficher F(n)

Nombre d'appels récursifs

On peut calculer le nombre R_n d'appels récursifs effectués lors d'un appel à F(n) avec n > 1. On a en effet :

$\large R_n\ =\ 1\ +\ R_{n-1}\ +\ R_{n-2}$

On peut alors poser R'_n = R_n + 1 d'où directement :

$\large R'_n\ =\ R'_{n-1}\ +\ R'_{n-2}$

On retrouve la suite de Fibonacci, mais avec des valeurs initiales doublées :

$\large R_0\ =\ 1\ \Rightarrow\ R'_0\ =\ 2$

$\large R_1\ =\ 1\ \Rightarrow\ R'_1\ =\ 2$

En mettant 2 en facteur, on en déduit directement :

$\large R'_n\ =\ 2\,\times\,F_n\ \Rightarrow\ R_n\ =\ 2\,\times\,F_n\ -\ 1$

La croissance de la suite étant exponentielle, ce nombre devient rapidement immense, et cet algorithme n'est applicable sur nos machines que pour des valeurs faibles (pe. moins de 42).

Approche itérative

Implémentation

Une version itérative est plus efficace sans être beaucoup plus complexe.

Soit terme_prec = 1
Soit terme_act = 1
Soit n = Lire
 
Pour k de 2 à n
    Soit tmp = terme_prec + terme_act
    terme_prec = terme_act
    terme_act = tmp
 
Afficher terme_act

La vision matricielle

Présentation de l'idée

$\large \left(\begin{array}{c}F_n\\F_{n-1}\end{array}\right)\ =\ \left(\begin{array}{cc}1&1\\1&0\end{array}\right)\ \cdot\ \left(\begin{array}{c}F_{n-1}\\F_{n-2}\end{array}\right)$

On en déduit par une récurrence descendante directe :

$\large \left(\begin{array}{c}F_n\\F_{n-1}\end{array}\right)\ =\ \left(\begin{array}{cc}1&1\\1&0\end{array}\right)^{n-1}\ \cdot\ \left(\begin{array}{c}1\\1\end{array}\right)$

Complexité

On sait exponentier une matrice carrée en temps logarithmique.