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.

Fonction

Essayer :

Avant le premier appel

Lire l’arbre des appels en texte
    en cours (dans la pile)terminé après ses appelslu dans memo cas de base

    Compteurs

    Appels lancés0
    Appels en cours0
    Profondeur maximale0
    Additions0
    Valeur renvoyée—

    Pile d’appels

      Dictionnaire memo

        Journal des appels