Fibonacci, ou l'arbre qui explose

Fonctions récursives · niveau 2

Énoncé

Coder la suite de Fibonacci ( $F_{0} = 0, F_{1} = 1, F_{n} = F_{n - 1} + F_{n - 2}$ ) en version récursive naïve. Compter ses appels pour $n = 5$ , montrer que sa complexité est exponentielle et proposer la version itérative en $O (n)$ .

Corrigé

def fib(n: int) -> int:
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

Pour $n = 5$ , l'exécution nécessite $15$ appels récursifs (dont 3 évaluations redondantes pour fib(2) et 5 pour fib(1)). Le nombre total d'appels $A (n) = 1 + A (n - 1) + A (n - 2)$ croît à la même vitesse que la suite elle-même, soit de façon exponentielle en $O (1, 61 8^{n})$ . Version itérative en $O (n)$ :

def fib_iter(n: int) -> int:
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

Cette itération effectue $n$ additions, a une profondeur de pile nulle et résout le problème de redondance de calcul.

Énoncé

Corrigé

Exercices semblables