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)