Fibonacci récursif — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 10)

Fibonacci récursif

Complexité des programmes · niveau 3 (difficile)

Énoncé

La suite de Fibonacci est définie par $f (0) = 0$ , $f (1) = 1$ et $f (n) = f (n - 1) + f (n - 2)$ . On la programme directement :


static long fib(int n) {
    if (n < 2) return n;
    return fib(n - 1) + fib(n - 2);
}

Soit $a (n)$ le nombre d'appels de fib provoqués par l'appel fib(n) (celui-ci compris). Écrire l'équation de récurrence de $a (n)$ et montrer que $a (n) = 2 f (n + 1) - 1$ .
En admettant $f (n) \approx φ^{n} / 5$ avec $φ = (1 + 5) /2 \approx 1, 618$ , donner la complexité.
Proposer un programme en $Θ (n)$ .

Corrigé

$a (0) = a (1) = 1$ et $a (n) = 1 + a (n - 1) + a (n - 2)$ pour $n \geq 2$ . Posons $b (n) = a (n) + 1$ : $b (0) = b (1) = 2$ et $b (n) = b (n - 1) + b (n - 2)$ . La suite $b$ vérifie la récurrence de Fibonacci avec $b (0) = 2 f (1)$ et $b (1) = 2 f (2)$ ; par récurrence, $b (n) = 2 f (n + 1)$ , donc $a (n) = 2 f (n + 1) - 1$ . Vérification (programme FibonacciNaif.java) :


n = 10 : f(n) =        55, appels =        177, 2f(n+1)-1 =        177
n = 20 : f(n) =      6765, appels =      21891, 2f(n+1)-1 =      21891
n = 30 : f(n) =    832040, appels =    2692537, 2f(n+1)-1 =    2692537
n = 40 : f(n) = 102334155, appels =  331160281, 2f(n+1)-1 =  331160281

Chaque appel coûte un temps constant hors appels récursifs : le temps est en $Θ (f (n + 1)) = Θ (φ^{n})$ , exponentiel. Chaque fois que $n$ augmente de $1$ , le temps est multiplié par environ $1, 6$ .
On calcule les valeurs par $k$ croissants, en ne gardant que les deux dernières :


static long fibonacci(int n) {
    long a = 0, b = 1;                // a = f(k), b = f(k+1), avec k = 0
    for (int k = 0; k < n; k++) {     // a = f(k) et b = f(k+1)
        long c = a + b; a = b; b = c; // a = f(k+1) et b = f(k+2)
    }
    return a;                         // a = f(n)
}

$n$ tours de boucle : $Θ (n)$ . Le chapitre 11 descend même à $Θ (lo g n)$ avec des puissances de matrices.