Appels récursifs multiples
Sans atteindre la profondeur maximale de récursion, on peut écrire un programme très lent avec une méthode récursive naïve avec des appels multiples.
La fonction de Fibonacci
On considère la fonction naïve :
def fib(n):
if n < 2:
return n
else:
return fib(n - 1) + fib(n - 2)
Ici, fib est une fonction récursive avec appels multiples.
On peut construire à la main le tableau de valeurs
n |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
fib(n) |
0 |
1 |
1 |
2 |
3 |
5 |
8 |
13 |
21 |
34 |
55 |
Mais observons comment fonctionne un script qui appelle fib(5)
Version dynamique ← 
site externe
On constate une profondeur d'appel faible 5, et de manière générale n. Pourtant, il y a de nombreux appels à f : ici \(15\).
On peut faire un script qui compte le nombre d'appels avec une astuce de POO (Programmation Orientée Objet) : une fonction est un objet, on lui donne un attribut compteur que l'on initialise avant utilisation.
def fib(n):
fib.compteur += 1 # à chaque utilisation de `fib`
if n < 2:
return n
else:
return fib(n - 1) + fib(n - 2)
for n in range(10):
fib.compteur = 0 # Initialisation du compteur
fib(n)
print(n, fib.compteur)
for n in [30, 35]:
fib.compteur = 0
fib(n)
print(n, fib.compteur)
On obtient la suite des nombres de Leonardo1
n |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
leo(n) |
1 |
1 |
3 |
5 |
9 |
15 |
25 |
41 |
67 |
109 |
177 |
- Pour
n = 30, on atteint \(2\,692\,537\) appels. - Pour
n = 35, on atteint \(29\,860\,703\) appels, ce qui ralentit déjà un ordinateur.
On est pourtant loin d'une profondeur de 1000 !
Pour rendre le calcul de la fonction de Fibonacci moins naïf, on peut faire de la mémoïsation. On stocke dans un tableau ou un dictionnaire les résultats déjà connus en vue de leur réutilisation.
fib_memo = {0: 0, 1: 1}
def fib(n):
"""Version récursive efficace"""
if n not in fib_memo:
fib_memo[n] = fib(n - 1) + fib(n - 2)
return fib_memo[n]
Les tours de Hanoï
En guise d'exercice, après avoir résolu le problème des tours de Hanoï, déterminer le nombre de déplacements élémentaires en fonction du nombre initial de disques.