module · récursivité · 15 min

Une fonction qui s'appelle elle-même, vue de l'intérieur.

Choisissez une fonction récursive, lancez la trace, regardez la pile d'appels grossir puis se vider. Avec Fibonacci, observez le coût caché : les mêmes calculs reviennent encore et encore.

défi · prédire le coût

palier 1 / 4

Sans dérouler la trace : que vaut factorielle(5) ? Saisir le nombre, puis vérifier.

prédisez la valeur

fact(5) = 5 × 4 × 3 × 2 × 1

résultat de factorielle(5)

bac à sable · observation libre

n =

vitesse

événement 1 / 10

pile d'appels1 frame(s)

factorielle(5) en cours…

arbre d'appels5 appels · profondeur 5

factorielle(5)

résultat

appel initial : factorielle(5)

…

factorielle · python

def fact(n):
    if n <= 1:
        return 1
    return n * fact(n - 1)

à retenir

Une fonction récursive doit toujours avoir un cas de base (sans appel récursif) — sinon, la pile explose.
Chaque appel crée un frame sur la pile, avec ses propres paramètres. Quand l'appel rend, son frame est dépilé.
La profondeur de récursion détermine la mémoire utilisée — Python plafonne par défaut à ~1000.
Fibonacci naïf recalcule sans cesse les mêmes valeurs : c'est exponentiel. La mémoïsation ou la version itérative ramènent cela à O(n).

retour au labo