La récursivité : comprendre les appels et les résultats

Un cap pour ce chapitre

Ce que vous saurez faire

Identifier cas de base et réduction du problème.
Tracer les appels et les retours.
Écrire une récursion qui termine sur son domaine.

Les bases utiles pour commencer

Réduire jusqu’à une réponse immédiate

Pour calculer la somme des entiers de un à n, on peut utiliser S(n)=n+S(n-1) lorsque n est positif, et S(0)=0. La seconde règle est le cas de base : sa réponse ne demande aucun appel supplémentaire. La première réduit le problème vers ce cas.

Le domaine compte : ici n est un entier naturel. Avec une valeur négative, décrémenter n ne rapproche pas de zéro. Une fonction récursive doit donc avoir une spécification, pas seulement un cas d’arrêt visible dans le code. La présence d’un test ne garantit pas que toutes les entrées autorisées l’atteignent.

def somme(n):
    assert isinstance(n, int) and n >= 0
    if n == 0:
        return 0
    return n + somme(n - 1)

Le contrat récursif se lit comme une promesse : si l’appel sur n-1 sait calculer la somme correspondante, ajouter n donne la somme voulue. On justifie séparément que cette réduction finit par atteindre zéro. Correction du résultat et terminaison sont donc deux questions liées, mais distinctes.

Descendre dans les appels

Pour somme(3), le premier appel doit calculer 3+somme(2). Il ne connaît pas encore somme(2), donc reste en attente. Le deuxième doit calculer 2+somme(1), puis le troisième 1+somme(0). Chaque appel possède son propre n local et son propre calcul restant.

Ces contextes s’organisent comme une pile : le dernier appel commencé doit fournir sa réponse avant que son appelant poursuive. On ne remplace pas toutes les variables n par une unique case partagée. Dessiner une ligne par appel évite cette confusion et permet de suivre exactement ce qui sera repris.

Remonter les résultats

somme(0) renvoie zéro. somme(1) peut alors calculer 1+0 et renvoie un. somme(2) reçoit un, calcule 2+1 et renvoie trois. Enfin somme(3) reçoit trois, calcule 3+3 et renvoie six. La descente construit des attentes ; la remontée les résout dans l’ordre inverse.

Le mot return est essentiel : afficher une valeur ne la transmet pas comme résultat à l’appelant. Une fonction qui affiche zéro dans son cas de base mais ne le renvoie pas donnera un résultat inutilisable pour l’addition attendue. Une trace doit donc distinguer affichages éventuels et valeurs réellement retournées.

Choisir la récursion pour sa structure

Les arbres, les découpages d’images et certains parcours se prêtent naturellement à la récursion parce que leurs sous-problèmes ressemblent au problème initial. La somme précédente pourrait aussi s’écrire avec une boucle ; l’intérêt du premier exemple est de rendre le mécanisme visible, pas d’imposer la récursion partout.

Le nombre d’appels et la profondeur maximale sont deux mesures différentes. Une fonction qui appelle deux sous-problèmes peut produire beaucoup d’appels sans tous les conserver simultanément. Python limite la profondeur de récursion ; pour de très longues suites linéaires, une boucle peut être plus adaptée. La terminaison mathématique ne garantit pas l’absence de limites pratiques de pile.

Exemple suivi : séparer les variables des appels

Dans somme(3), dessinez quatre cadres nommés par leur argument. Le cadre n=3 attend « ajouter 3 », celui de n=2 attend « ajouter 2 », celui de n=1 attend « ajouter 1 » et celui de n=0 renvoie immédiatement zéro. Lorsque le dernier cadre disparaît, le cadre n=1 existe encore et conserve sa propre valeur locale. La valeur n=0 ne remplace pas les arguments des cadres précédents.

Le tableau des retours est ainsi (0,0), (1,1), (2,3), (3,6), avec argument puis résultat. Pour contrôler votre trace, vérifiez chaque ligne grâce à la précédente. Un appel de fonction est une expression qui doit fournir une valeur avant que l’addition de son appelant se termine. Dans l’atelier, arrêtez-vous au cas de base et prédisez le prochain retour avant de déplacer le curseur : les résultats futurs restent cachés.

Exemple suivi : une recherche récursive dans une liste

Pour chercher une valeur à partir de l’indice i dans une liste finie, on peut poser trois cas : si i vaut la longueur, renvoyer faux ; si la case i contient la cible, renvoyer vrai ; sinon chercher à partir de i+1. La distance à la fin, longueur moins i, diminue à chaque appel. Le test de fin doit précéder l’accès à la case : dans la liste vide, l’indice zéro n’existe pas.

Sur [4,7,4] avec cible 7, les indices visités sont 0 puis 1, et le vrai remonte sans changer. Avec cible 9, les indices 0, 1, 2 sont examinés, puis l’appel à 3 conclut faux. Cette seconde situation montre un résultat récursif simplement transmis par return, sans addition. Pour une longue liste, une boucle exprime la même recherche avec moins de cadres simultanés ; la version récursive sert à comprendre le découpage du problème.

À vous de faire varier les choses

Dépliez la pile, puis remontez les résultats

Choisissez une somme ou une puissance. Déplacez l’étape pour voir les appels en attente puis leur résolution.

Lire le résultat de l’expérience initiale

Appel f(0) = 0

La descente conserve les opérations en attente.

Étape	Événement	Valeur retournée
0	Appel f(4)	En attente
1	Appel f(3)	En attente
2	Appel f(2)	En attente
3	Appel f(1)	En attente
4	Appel f(0)	0

Indice 2

Le dernier cas renvoie directement le résultat du sous-appel.

Comprendre la correction

La fonction renvoie faux si i atteint la longueur, vrai si t[i]==x, sinon le résultat de contient(t,x,i+1). Les tests contient([4,7,4],4), contient([4,7,4],9), contient([],9) attendent vrai, faux, faux. La recherche absente effectue quatre appels, indices 0 à 3 inclus. Le dernier n’accède à aucune case : il vérifie seulement la fin.

def contient(t, x, i=0):
    if i == len(t):
        return False
    if t[i] == x:
        return True
    return contient(t, x, i + 1)

assert contient([4, 7, 4], 4)
assert not contient([4, 7, 4], 9)
assert not contient([], 9)

L’appel initial suppose i=0 ; les appels internes conservent 0≤i≤len(t). La fonction ne change aucune case de t.

Exercice 7 · Problème de synthèse#

Problème : un cas de base inaccessible

On définit G(0)=0 puis G(n)=1+G(n-2) pour les autres entiers naturels. Tracez les arguments depuis 6 et depuis 5. Le contrat sur tous les naturels est-il respecté ? Proposez une base couvrant la progression et expliquez ce que compterait alors la fonction.

Indice 1

La parité des arguments reste constante.

Indice 2

Une valeur impaire positive atteint un avant de devenir négative.

Comprendre la correction

Depuis 6, on visite 6,4,2,0 et on termine. Depuis 5, on visite 5,3,1,-1,-3 : zéro est manqué. Pour compter les retraits de deux jusqu’à une valeur non positive, on peut poser G(n)=0 pour n≤0 puis garder la récurrence pour n>0. G(5) vaut alors 3 et G(6) vaut 3. Il faut annoncer ce nouveau sens, pas seulement ajouter un test arbitraire.

Les erreurs qui méritent un détour

Oublier de renvoyer le résultat récursif.: Un affichage ne fournit pas à l’appelant la valeur attendue.
Penser qu’un cas de base suffit.: Il faut démontrer que les appels s’en rapprochent pour toute entrée autorisée.

La fiche à garder

L’essentiel à retenir

Une récursion relie le problème à des instances plus petites.
Chaque appel possède son contexte local.
Les résultats remontent après l’atteinte des bases.

Cette notion au bac

Retrouvez ces idées dans un sujet complet, avec des indices, une correction expliquée et des ateliers.

Le prochain pas

Retrouver le catalogue de Terminale

Ce chapitre s’appuie sur le programme officiel de Terminale (PDF, nouvel onglet). Les explications et exercices sont proposés pour l’apprentissage.