Première · Numérique et sciences informatiques
Comprendre un appel récursif : pile d'appels et cas de base
Suivre pas à pas l'exécution d'une fonction récursive en décrivant la pile d'appels, repérer le cas de base et justifier que la récursion se termine.
Aperçu gratuit

Les points essentiels
- Une fonction récursive est une fonction qui s'appelle elle-même, avec des arguments différents à chaque appel.
- Chaque appel crée un nouveau contexte d'exécution (ses propres paramètres et variables locales), empilé dans la pile d'appels.
Les mots à connaître
- Appel récursif
- Instruction par laquelle une fonction s'invoque elle-même, par exemple fact(n - 1) à l'intérieur de la définition de fact.
- Cas de base
- Condition pour laquelle la fonction renvoie directement une valeur sans appel récursif, par exemple n == 0 qui renvoie 1 dans le calcul de la factorielle.
Un exemple pour comprendre
On considère def fact(n): if n == 0: return 1 else: return n * fact(n - 1). Décrire les appels et la valeur retournée pour fact(3).
Empilement : fact(3) appelle fact(2), qui appelle fact(1), qui appelle fact(0). Pour fact(0), n vaut 0 : c'est le cas de base, il renvoie 1 sans nouvel appel. Dépilement : fact(1) renvoie 1 * 1 = 1 ; fact(2) renvoie 2 * 1 = 2 ; fact(3) renvoie 3 * 2 = 6. La pile a compté 4 appels au maximum en même temps. Résultat : fact(3) = 6, ce qui est bien 3 × 2 × 1.

