Première · Numérique et sciences informatiques

Récursivité : appel, pile d'appels et cas de base

Écrire une fonction récursive simple en Python en identifiant son cas de base, justifier sa terminaison et représenter la pile des appels sur un petit exemple.

Aperçu gratuit
Illustration de la fiche « Récursivité : appel, pile d'appels et cas de base »

Les points essentiels

  • Une fonction est récursive lorsqu'elle s'appelle elle-même sur un problème plus petit ; chaque appel travaille sur des paramètres différents de l'appel précédent.
  • Le cas de base est le cas le plus simple, traité directement sans nouvel appel récursif : sans lui, la fonction ne s'arrête jamais.

Les mots à connaître

Fonction récursive
Fonction dont le corps contient un appel à elle-même, avec des arguments qui rapprochent le calcul d'un cas qu'elle sait traiter directement.
Cas de base
Situation la plus simple, traitée par un return direct sans appel récursif, qui arrête la chaîne des appels (par exemple n == 0 pour la factorielle).

Un exemple pour comprendre

On définit en Python : def fact(n): if n == 0: return 1 else: return n * fact(n-1). Déroulez fact(3) en indiquant la pile des appels et la valeur renvoyée.

Cas de base : n == 0 renvoie 1. Descente : fact(3) attend 3 * fact(2) ; fact(2) attend 2 * fact(1) ; fact(1) attend 1 * fact(0) ; fact(0) renvoie 1. À cet instant la pile contient, du sommet vers le bas : fact(0), fact(1), fact(2), fact(3). Remontée : fact(0) est dépilé et renvoie 1 ; fact(1) renvoie 1 * 1 = 1 ; fact(2) renvoie 2 * 1 = 2 ; fact(3) renvoie 3 * 2 = 6. Résultat : fact(3) = 6, avec 4 appels au total et une profondeur maximale de pile de 4.

Première page de l’Essentiel : Récursivité : appel, pile d'appels et cas de base
Ketty