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
Illustration de la fiche « Comprendre un appel récursif : pile d'appels et cas de base »

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.

Première page de l’Essentiel : Comprendre un appel récursif : pile d'appels et cas de base
Ketty