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.

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.

