Laboratoire visuel : récursivité
Regardez l’arbre des appels se construire appel par appel, avec la pile et le dictionnaire de mémoïsation, pour Fibonacci, la factorielle et l’algorithme d’Euclide.
Fibonacci naïf suit ce code :
def fibonacci_recursif(n):
if n == 0:
return 0
if n == 1:
return 1
return fibonacci_recursif(n - 1) + fibonacci_recursif(n - 2)
Fibonacci mémoïsé suit ce code :
def fibonacci_memo(n, memo=None):
if memo is None:
memo = {}
if n == 0:
return 0
if n == 1:
return 1
if n in memo:
return memo[n]
memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
return memo[n]
La factorielle suit ce code :
def factorielle(n):
if n == 0:
return 1
return n * factorielle(n - 1)
L’algorithme d’Euclide suit ce code :
def euclide_recursif(a, b):
if b == 0:
return a
return euclide_recursif(b, a % b)
Laboratoire visuel : récursivité
Chaque appel devient un nœud de l’arbre des appels. Les nœuds rouges sont les appels en cours, c’est-à-dire la pile ; un appel terminé affiche la valeur qu’il renvoie. Comparez le nombre d’appels et la profondeur de la pile.
Avant le premier appel
Lire l’arbre des appels en texte
memo cas de baseCompteurs
Appels lancés0
Appels en cours0
Profondeur maximale0
Additions0
Valeur renvoyée—