labo
module · récursivité · 15 min

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

Choisis une fonction récursive, lance la trace, regarde la pile d'appels grossir puis se vider. Avec Fibonacci, observe 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) ? Saisis le nombre, puis vérifie.

prédis la valeur

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

bac à sable · observation libre
événement 1 / 10
pile d'appels1 frame(s)
factorielle(5) en cours…
appel factorielle(5)
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