Fonctions récursives

Cours · informatique (tronc commun des prépas scientifiques), chapitre 6 · prépas scientifiques, tronc commun · le début du chapitre, la suite sur Adloun

Les appels récursifs du calcul de la suite de Fibonacci forment un arbre, où les mêmes valeurs reviennent plusieurs fois.

6.1 Introduction et motivation

Pour décrire un escalier, deux options : « une suite de marches » — c'est la boucle — ou bien « une marche, suivie d'un escalier plus petit » — c'est la récursivité. Une fonction récursive est une fonction qui s'appelle elle-même sur une entrée plus petite, jusqu'à atteindre un cas si simple qu'il se résout sans appel. Loin d'être un gadget, c'est une seconde manière de penser les algorithmes, souvent plus proche de la définition mathématique du problème : la dichotomie du chapitre 5 (« chercher dans la moitié »), les figures qui se contiennent elles-mêmes (les fractales), l'énumération de tous les sous-ensembles ou de toutes les permutations — autant de problèmes dont la solution récursive tient en quelques lignes là où la version à boucles demanderait des contorsions.

Le programme met en garde : on ne se cantonne pas aux suites mathématiques (factorielle et compagnie), qui font croire que la récursivité n'est qu'une boucle déguisée. On l'emploie là où elle brille — et on apprend son coût caché : chaque appel empile un contexte, et la pile d'appels peut déborder. Comme toujours, les outils du chapitre 1 suivent : la terminaison d'une récursion est un variant sur l'argument, sa correction une récurrence.

6.2 Le principe

6.2.1 Cas de base, cas récursif

Définition 6.1Fonction récursive

Une fonction est récursive si son corps contient un appel à elle-même. Toute définition récursive correcte comporte :

un (ou plusieurs) cas de base : des entrées résolues directement, sans appel récursif ;
un (ou plusieurs) cas récursifs : la solution s'exprime à partir de la solution du même problème sur une entrée strictement plus petite.


def somme_jusqua(n: int) -> int:
    """Renvoie 0 + 1 + ... + n. Précondition : n >= 0."""
    if n == 0:                       # cas de base
        return 0
    return n + somme_jusqua(n - 1)   # cas récursif : le problème en taille n - 1

Méthode : Concevoir une fonction récursive

Trois questions, toujours les mêmes :

Le cas de base : pour quelles entrées la réponse est-elle immédiate ? (Souvent : $n = 0$ , liste vide, chaîne vide.)
La décomposition : si quelqu'un me donnait la solution pour une entrée plus petite — $n - 1$ , la moitié du tableau, la liste privée de sa tête — comment en déduirais-je la mienne ?
La décroissance : chaque appel récursif rapproche-t-il strictement d'un cas de base ?

Le point 2 est le saut conceptuel : on fait confiance à l'appel récursif, comme on fait confiance à l'hypothèse de récurrence en mathématiques — sans chercher à dérouler mentalement les appels.

6.2.2 Ce que fait vraiment la machine : la pile d'appels

Définition 6.2Pile d'appels

À chaque appel de fonction, l'interpréteur empile un contexte (les paramètres et variables locales de cet appel) ; au return, le contexte est dépilé et l'exécution reprend chez l'appelant. Pour somme_jusqua(3) :


somme_jusqua(3)                       en attente de somme_jusqua(2)
   somme_jusqua(2)                    en attente de somme_jusqua(1)
      somme_jusqua(1)                 en attente de somme_jusqua(0)
         somme_jusqua(0)  -> 0        cas de base : on redescend
      -> 1 + 0 = 1
   -> 2 + 1 = 3
-> 3 + 3 = 6

La descente empile, le cas de base fait demi-tour, la remontée calcule. À tout instant, la pile contient la chaîne des appels en attente — sa hauteur maximale est la profondeur de récursion.

AttentionLe débordement de pile

La pile n'est pas infinie : Python limite la profondeur à environ $1000$ appels. somme_jusqua(10**5) lève RecursionError: maximum recursion depth exceeded — et une récursion sans cas de base atteignable (le bogue récursif par excellence) lève la même erreur après une seconde de silence :


def perdu(n):
    return perdu(n - 1)      # aucun cas de base : 1000 appels, puis RecursionError

Règle pratique : une profondeur en $O (lo g n)$ (dichotomies) ne pose jamais problème ( $30$ niveaux pour $n = 1 0^{9}$ ) ; une profondeur en $O (n)$ interdit les grandes entrées — on convertira alors en boucle.

Exercices du chapitre

Fibonacci, ou l'arbre qui explose corrigé
Le tracé de Sierpinski corrigé
Les sous-listes d'une somme donnée corrigé
Convertir une récursion en boucle corrigé
Les tours de Hanoï corrigé
Générer dans l'ordre du code de Gray corrigé

La suite du cours · Tous les exercices du chapitre