Appels 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 l'appel multiple.
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
if n < 2:
return n
else:
return fib(n - 1) + fib(n - 2)
for n in range(10):
fib.compteur = 0
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éterminez le nombre de déplacements élémentaires en fonction du nombre de disques initial.