La récursivité

Objectifs

À la fin de ce chapitre, l’élève doit être capable de :

• reconnaître un module récursif et y identifier le cas d’arrêt et l’appel récursif ;
• passer d’une formulation itérative à une formulation récursive, et inversement ;
• exécuter manuellement une fonction récursive et en déduire son rôle ;
• écrire une fonction récursive portant sur un entier, une chaîne de caractères ou un tableau ;
• traduire une fonction récursive en Python.

Plan du chapitre

1. Introduction
2. Notion de récursivité
3. Exécution d’une fonction récursive
4. Du récursif à l’itératif
5. Rôle d’une fonction récursive
6. Les erreurs les plus fréquentes
7. Retenons

1. Introduction

Activité 1

On veut calculer la puissance xⁿ d’un entier x, pour un entier n positif ou nul.

Questions

1. Écrire l’algorithme d’une fonction Puissance(x, n) qui calcule xⁿ à l’aide d’une boucle.
2. Compléter les égalités ci-dessous en faisant apparaître, dans chaque ligne, le résultat de la ligne précédente.
3. Exprimer xⁿ en fonction de xⁿ⁻¹. Pour quelle valeur de n le résultat est-il connu sans aucun calcul ?

5² = 5 * 5              = 25
5³ = 5 * 5 * 5          = 5 * …   = 125
5⁴ = 5 * 5 * 5 * 5      = 5 * …   = 625
5⁵ = 5 * 5 * 5 * 5 * 5  = 5 * …   = 3125

Réponse

1. On multiplie n fois la valeur x : le nombre de répétitions est connu, la boucle est une boucle Pour.

Fonction Puissance (x, n : Entier) : Entier
DEBUT
    P ← 1
    Pour i de 1 à n Faire
        P ← P * x
    Fin Pour
    Retourner P
FIN

TDOL

2. Chaque puissance contient la précédente :

5² = 5 * 5              = 25
5³ = 5 * (5 * 5)        = 5 * 5²  = 125
5⁴ = 5 * (5 * 5 * 5)    = 5 * 5³  = 625
5⁵ = 5 * (5 * 5 * 5 * 5) = 5 * 5⁴ = 3125

3. Pour tout n ≥ 1, xⁿ = x * xⁿ⁻¹. Le résultat est connu sans calcul pour n = 0 : x⁰ = 1.

La fonction Puissance peut donc s’écrire sans boucle : pour calculer Puissance(x, n), il suffit de calculer Puissance(x, n - 1) et de multiplier le résultat par x, sauf lorsque n = 0, où le résultat vaut 1.

Fonction Puissance (x, n : Entier) : Entier
DEBUT
    Si n = 0 Alors
        Retourner 1
    Sinon
        Retourner x * Puissance(x, n - 1)
    FinSi
FIN

La fonction Puissance s’appelle elle-même, sur un exposant plus petit. On dit qu’elle est récursive.

2. Notion de récursivité

2.1 Définition

Définition. Un module est récursif lorsqu’il s’appelle lui-même dans son propre corps. Chaque appel porte sur des données plus simples que celles de l’appel qui le précède.

Un module récursif comporte toujours au moins :

• un cas d’arrêt, dans lequel le résultat est obtenu directement, sans nouvel appel ;
• un appel récursif, qui ramène le problème au même problème sur des données plus simples, plus proches du cas d’arrêt.

Dans la fonction Puissance, le cas d’arrêt est n = 0, et l’appel récursif est Puissance(x, n - 1).

Forme générale d’une fonction récursive

Fonction Nom (paramètres) : Type_résultat
DEBUT
    Si Condition_arrêt Alors
        Retourner Valeur_de_base
    Sinon
        Retourner Nom(paramètres_modifiés)
    FinSi
FIN

Remarque. Cette forme est la plus simple. Une fonction récursive peut avoir plusieurs cas d’arrêt et plusieurs appels récursifs, placés dans les branches d’un Si … Sinon Si … Sinon : c’est le cas de PGCD, Palindrome et Dichotomique, plus loin. L’appel récursif peut aussi faire partie d’un calcul, comme x * Puissance(x, n - 1).

Remarque importante. Dans une fonction récursive, l’instruction Retourner figure dans chacune des branches du Si. C’est la seule situation où une fonction contient plusieurs Retourner. L’instruction Retourner ne se place jamais à l’intérieur d’une boucle.

2.2 Trois questions pour écrire une fonction récursive

Pour écrire une fonction récursive, on répond à trois questions.

Les réponses donnent directement l’algorithme : la deuxième fournit la branche Alors, la troisième la branche Sinon. La première garantit que les appels successifs finissent par atteindre le cas d’arrêt.

La donnée qui évolue ne diminue pas toujours : elle peut aussi augmenter, comme un indice qui avance d’une case à chaque appel jusqu’à la fin d’une chaîne. Ce qui compte, c’est qu’à chaque appel elle se rapproche du cas d’arrêt.

2.3 Itératif et récursif

Remarque importante. La version récursive de Puissance n’a ni variable locale ni module appelé autre qu’elle-même : conformément aux conventions, elle n’a pas de TDOL. Le module qui s’appelle lui-même ne figure pas dans son propre TDOL.

En Python

def Puissance(x, n):
    if n == 0:
        return 1
    else:
        return x * Puissance(x, n - 1)

3. Exécution d’une fonction récursive

3.1 La pile d’exécution

Lorsqu’un module en appelle un autre, l’ordinateur suspend le module appelant, exécute le module appelé, puis reprend le module appelant là où il s’était arrêté. Pour pouvoir reprendre, il mémorise, pour chaque appel en cours, les valeurs de ses paramètres, de ses variables locales et l’endroit où reprendre.

Définition. La pile d’exécution est la zone de la mémoire où sont rangés les appels en cours. Le dernier appel rangé est le premier terminé : on dit que la pile fonctionne selon le principe dernier entré, premier sorti.

Dans un module récursif, chaque appel ajoute un étage à la pile. Les appels s’empilent jusqu’au cas d’arrêt ; puis les appels se terminent l’un après l’autre, du dernier au premier, et chacun rend sa valeur à celui qui l’a appelé.

3.2 Exécution manuelle de l’appel Puissance(2, 4)

L’exécution se fait en deux temps.

La descente. Tant que le cas d’arrêt n’est pas atteint, chaque appel lance l’appel suivant et reste en attente de sa valeur.

La remontée. L’appel Puissance(2, 0) retourne 1 sans nouvel appel. Chaque appel en attente reçoit alors la valeur de l’appel suivant, effectue sa multiplication et retourne son propre résultat.

Remarque importante. Les trois premières colonnes se remplissent de haut en bas, pendant la descente. La dernière se remplit de bas en haut, pendant la remontée : aucune valeur n’est connue avant que le cas d’arrêt soit atteint.

Le schéma représente la pile au moment où elle est la plus haute. L’empilement, flèche de gauche, se lit de bas en haut : chaque appel pose un nouvel étage au-dessus du précédent. Le dépilement, flèche de droite, se lit de haut en bas : l’étage du sommet se termine le premier, retourne sa valeur à l’étage du dessous, et disparaît.

On peut aussi écrire le calcul sous forme développée :

Puissance(2, 4) = 2 * Puissance(2, 3)
                = 2 * 2 * Puissance(2, 2)
                = 2 * 2 * 2 * Puissance(2, 1)
                = 2 * 2 * 2 * 2 * Puissance(2, 0)
                = 2 * 2 * 2 * 2 * 1
                = 16

L’appel Puissance(2, 4) provoque 5 appels en tout : un pour chaque valeur de n, de 4 à 0. Au moment où Puissance(2, 0) s’exécute, les cinq appels sont présents en même temps dans la pile.

3.3 La terminaison

Un module récursif ne se termine que si ses appels atteignent le cas d’arrêt. Deux erreurs l’en empêchent :

• l’absence de cas d’arrêt : chaque appel lance un nouvel appel, sans fin ;
• un appel qui ne rapproche pas du cas d’arrêt.

Exemple. L’appel Puissance(2, -1) provoque les appels Puissance(2, -2), Puissance(2, -3), … : l’exposant s’éloigne de 0 et le cas d’arrêt n’est jamais atteint. Chaque appel ajoute un étage à la pile, dont la taille est limitée : l’exécution s’interrompt par un débordement de pile.

En Python, l’exécution s’interrompt après un millier d’appels environ, avec le message :

RecursionError: maximum recursion depth exceeded

Remarque importante. La fonction Puissance n’est correcte que pour n ≥ 0. Toute fonction récursive suppose une condition sur ses paramètres, qui garantit que le cas d’arrêt sera atteint. C’est au module appelant de la respecter, par exemple par une saisie contrôlée.

Application 1 — Factorielle et PGCD

On considère les trois fonctions itératives suivantes, vues en 3ᵉ année.

Fonction Factorielle (n : Entier) : Entier
DEBUT
    F ← 1
    Pour i de 2 à n Faire
        F ← F * i
    Fin Pour
    Retourner F
FIN

Fonction PGCD (a, b : Entier) : Entier
DEBUT
    Tant que a ≠ b Faire
        Si a > b Alors
            a ← a - b
        Sinon
            b ← b - a
        FinSi
    Fin Tant que
    Retourner a
FIN

Fonction PGCD_Euclide (a, b : Entier) : Entier
DEBUT
    Tant que b ≠ 0 Faire
        r ← a Mod b
        a ← b
        b ← r
    Fin Tant que
    Retourner a
FIN

La factorielle d’un entier n, notée n!, est le produit des entiers de 1 à n, avec 0! = 1. La fonction PGCD calcule le PGCD de deux entiers par la méthode des différences, la fonction PGCD_Euclide par la méthode d’Euclide.

Travail demandé

1. Exprimer n! en fonction de (n - 1)!. Pour quelle valeur de n le résultat est-il connu sans calcul ?
2. En déduire l’algorithme de la fonction récursive Factorielle(n).
3. Donner l’exécution manuelle de l’appel Factorielle(4) : la suite des appels et les valeurs retournées.
4. Écrire l’algorithme de la fonction récursive PGCD(a, b), selon la méthode des différences.
5. Écrire l’algorithme de la fonction récursive PGCD_Euclide(a, b), selon la méthode d’Euclide.
6. Donner l’exécution manuelle des appels PGCD(84, 36) et PGCD_Euclide(84, 36). Comparer le nombre d’appels.
7. Donner l’exécution manuelle de l’appel PGCD_Euclide(18, 48). Que fait le premier appel ?

N.B. L’entier n est positif ou nul. Pour PGCD, les entiers a et b sont strictement positifs. Pour PGCD_Euclide, ils sont positifs ou nuls, et ne sont pas nuls tous les deux.

4! = 4 * 3 * 2 * 1 = 4 * (3 * 2 * 1) = 4 * 3!

Fonction Factorielle (n : Entier) : Entier
DEBUT
    Si n = 0 Alors
        Retourner 1
    Sinon
        Retourner n * Factorielle(n - 1)
    FinSi
FIN

def Factorielle(n):
    if n == 0:
        return 1
    else:
        return n * Factorielle(n - 1)

Factorielle(4) = 4 * Factorielle(3)
               = 4 * 3 * Factorielle(2)
               = 4 * 3 * 2 * Factorielle(1)
               = 4 * 3 * 2 * 1 * Factorielle(0)
               = 4 * 3 * 2 * 1 * 1
               = 24

Fonction PGCD (a, b : Entier) : Entier
DEBUT
    Si a = b Alors
        Retourner a
    Sinon Si a > b Alors
        Retourner PGCD(a - b, b)
    Sinon
        Retourner PGCD(a, b - a)
    FinSi
FIN

def PGCD(a, b):
    if a == b:
        return a
    elif a > b:
        return PGCD(a - b, b)
    else:
        return PGCD(a, b - a)

Fonction PGCD_Euclide (a, b : Entier) : Entier
DEBUT
    Si b = 0 Alors
        Retourner a
    Sinon
        Retourner PGCD_Euclide(b, a Mod b)
    FinSi
FIN

def PGCD_Euclide(a, b):
    if b == 0:
        return a
    else:
        return PGCD_Euclide(b, a % b)

Application 2 — Palindrome

Un palindrome est un mot qui se lit de la même façon de gauche à droite et de droite à gauche, comme "RADAR" ou "ELLE". La chaîne inversée d’une chaîne ch est la chaîne ch écrite de droite à gauche : l’inverse de "BAC" est "CAB".

Travail demandé

1. Pour quelles chaînes sait-on, sans aucune comparaison, qu’elles sont des palindromes ? Pour une chaîne plus longue, à quelle condition est-elle un palindrome ?
2. En déduire l’algorithme de la fonction récursive Palindrome(ch) qui vérifie si la chaîne ch est un palindrome.
3. Donner l’exécution manuelle des appels Palindrome("RADAR") et Palindrome("RESTER").
4. Écrire l’algorithme de la fonction récursive Inverser(ch) qui retourne la chaîne inversée de ch.
5. Donner l’exécution manuelle de l’appel Inverser("BAC").

N.B. Les chaînes sont écrites en majuscules.

Fonction Palindrome (ch : Chaîne de caractères) : Booléen
DEBUT
    Si Long(ch) < 2 Alors
        Retourner Vrai
    Sinon Si ch[0] ≠ ch[Long(ch) - 1] Alors
        Retourner Faux
    Sinon
        Retourner Palindrome(Sous_chaine(ch, 1, Long(ch) - 1))
    FinSi
FIN

def Palindrome(ch):
    if len(ch) < 2:
        return True
    elif ch[0] != ch[len(ch) - 1]:
        return False
    else:
        return Palindrome(ch[1:len(ch) - 1])

Inverser("BAC") = "C" + Inverser("BA")

Fonction Inverser (ch : Chaîne de caractères) : Chaîne de caractères
DEBUT
    Si ch = "" Alors
        Retourner ""
    Sinon
        Retourner ch[Long(ch) - 1] + Inverser(Sous_chaine(ch, 0, Long(ch) - 1))
    FinSi
FIN

def Inverser(ch):
    if ch == "":
        return ""
    else:
        return ch[len(ch) - 1] + Inverser(ch[0:len(ch) - 1])

Application 3 — Notes d’un devoir

Les notes, entières, obtenues par les élèves d’un groupe à un devoir de l’année 2027 sont rangées dans un tableau T de n entiers, déclaré ainsi :

Exemple : n = 6.

Travail demandé

1. Écrire l’algorithme de la fonction récursive Somme(T, n) qui retourne la somme des n premiers éléments de T.
2. Donner l’exécution manuelle de l’appel Somme(T, 6) sur l’exemple.
3. Écrire l’algorithme de la fonction récursive Maximum(T, n) qui retourne la plus grande note du tableau, puis donner l’exécution manuelle de l’appel Maximum(T, 6).
4. Écrire l’algorithme de la fonction récursive Recherche_Seq(T, n, x) qui vérifie si la note x figure parmi les n premiers éléments de T.
5. Écrire l’algorithme de la fonction récursive Occurrences(T, n, x) qui retourne le nombre d’élèves ayant obtenu la note x.
6. Le tableau est maintenant trié par ordre croissant. Écrire l’algorithme de la fonction récursive Dichotomique(T, d, f, x) qui vérifie, par une recherche dichotomique, si la note x figure entre les indices d et f du tableau T. Donner l’exécution manuelle de la recherche de 15, puis de celle de 16.

N.B. Le tableau T est déjà rempli, et n ≥ 1.

Fonction Somme (T : Tab, n : Entier) : Entier
DEBUT
    Si n = 0 Alors
        Retourner 0
    Sinon
        Retourner T[n - 1] + Somme(T, n - 1)
    FinSi
FIN

def Somme(T, n):
    if n == 0:
        return 0
    else:
        return T[n - 1] + Somme(T, n - 1)

Fonction Maximum (T : Tab, n : Entier) : Entier
DEBUT
    Si n = 1 Alors
        Retourner T[0]
    Sinon
        m ← Maximum(T, n - 1)
        Si T[n - 1] > m Alors
            Retourner T[n - 1]
        Sinon
            Retourner m
        FinSi
    FinSi
FIN

def Maximum(T, n):
    if n == 1:
        return T[0]
    else:
        m = Maximum(T, n - 1)
        if T[n - 1] > m:
            return T[n - 1]
        else:
            return m

Fonction Recherche_Seq (T : Tab, n, x : Entier) : Booléen
DEBUT
    Si n = 0 Alors
        Retourner Faux
    Sinon Si T[n - 1] = x Alors
        Retourner Vrai
    Sinon
        Retourner Recherche_Seq(T, n - 1, x)
    FinSi
FIN

def Recherche_Seq(T, n, x):
    if n == 0:
        return False
    elif T[n - 1] == x:
        return True
    else:
        return Recherche_Seq(T, n - 1, x)

Fonction Occurrences (T : Tab, n, x : Entier) : Entier
DEBUT
    Si n = 0 Alors
        Retourner 0
    Sinon Si T[n - 1] = x Alors
        Retourner 1 + Occurrences(T, n - 1, x)
    Sinon
        Retourner Occurrences(T, n - 1, x)
    FinSi
FIN

def Occurrences(T, n, x):
    if n == 0:
        return 0
    elif T[n - 1] == x:
        return 1 + Occurrences(T, n - 1, x)
    else:
        return Occurrences(T, n - 1, x)

Fonction Dichotomique (T : Tab, d, f, x : Entier) : Booléen
DEBUT
    Si d > f Alors
        Retourner Faux
    Sinon
        milieu ← (d + f) Div 2
        Si T[milieu] = x Alors
            Retourner Vrai
        Sinon Si T[milieu] > x Alors
            Retourner Dichotomique(T, d, milieu - 1, x)
        Sinon
            Retourner Dichotomique(T, milieu + 1, f, x)
        FinSi
    FinSi
FIN

def Dichotomique(T, d, f, x):
    if d > f:
        return False
    else:
        milieu = (d + f) // 2
        if T[milieu] == x:
            return True
        elif T[milieu] > x:
            return Dichotomique(T, d, milieu - 1, x)
        else:
            return Dichotomique(T, milieu + 1, f, x)

4. Du récursif à l’itératif

4.1 Principe

Au Bac, on demande aussi le passage inverse : écrire la version itérative d’une fonction récursive donnée.

Il n’existe pas de règle unique : la méthode dépend de ce que fait la fonction après son appel récursif.

• Si l’appel est suivi d’un calcul, comme dans Puissance, Somme ou Inverser, la boucle refait la remontée, dans le même ordre : c’est l’exemple 4.2.
• Si l’appel n’est suivi d’aucun calcul, comme dans PGCD ou Recherche_Seq, les paramètres deviennent les variables de la boucle, qui continue tant qu’aucun cas d’arrêt n’est atteint : c’est l’exemple 4.3.

4.2 Exemple : Inverser

On part de la fonction récursive de l’application résolue 2.

Fonction Inverser (ch : Chaîne de caractères) : Chaîne de caractères
DEBUT
    Si ch = "" Alors
        Retourner ""
    Sinon
        Retourner ch[Long(ch) - 1] + Inverser(Sous_chaine(ch, 0, Long(ch) - 1))
    FinSi
FIN

Pendant la remontée de l’appel Inverser("BAC"), les valeurs retournées sont successivement "", "B", "AB", puis "CAB" : à chaque étape, le caractère suivant de ch, dans l’ordre de lecture, est placé devant le résultat précédent.

• Le cas d’arrêt retourne "" : la variable résultat chinv est initialisée à "".
• Chaque étape de la remontée place un caractère devant le résultat : l’instruction répétée est chinv ← ch[i] + chinv.
• Il y a autant d’étapes que de caractères, nombre connu d’avance : la boucle est une boucle Pour.

Fonction Inverser (ch : Chaîne de caractères) : Chaîne de caractères
DEBUT
    chinv ← ""
    Pour i de 0 à Long(ch) - 1 Faire
        chinv ← ch[i] + chinv
    Fin Pour
    Retourner chinv
FIN

TDOL

La boucle refait exactement la remontée : après chaque tour, chinv contient la valeur retournée par l’appel correspondant.

4.3 Exemple : Recherche_Seq

On part de la fonction récursive de l’application résolue 3.

Fonction Recherche_Seq (T : Tab, n, x : Entier) : Booléen
DEBUT
    Si n = 0 Alors
        Retourner Faux
    Sinon Si T[n - 1] = x Alors
        Retourner Vrai
    Sinon
        Retourner Recherche_Seq(T, n - 1, x)
    FinSi
FIN

La fonction a deux cas d’arrêt, et le second peut survenir avant la fin du tableau : le nombre d’appels n’est pas connu d’avance, la boucle est une boucle Tant que. On continue tant qu’aucun des deux cas d’arrêt n’est atteint, c’est-à-dire tant que n > 0 et T[n - 1] ≠ x.

Fonction Recherche_Seq (T : Tab, n, x : Entier) : Booléen
DEBUT
    Tant que (n > 0) Et (T[n - 1] ≠ x) Faire
        n ← n - 1
    Fin Tant que
    Retourner n > 0
FIN

À la sortie de la boucle, n > 0 signifie que la boucle s’est arrêtée sur T[n - 1] = x : l’élément est trouvé. n = 0 signifie que tous les éléments ont été examinés sans succès.

Remarque importante. La condition de la boucle Tant que est la négation de la disjonction des cas d’arrêt : on s’arrête si n = 0 ou T[n - 1] = x, donc on continue si n > 0 et T[n - 1] ≠ x.

5. Rôle d’une fonction récursive

5.1 Démarche

Pour déterminer le rôle d’une fonction récursive donnée, on l’exécute manuellement sur une valeur particulière, puis on généralise le résultat observé. La démarche comporte trois étapes.

1. Exécuter manuellement la fonction sur la valeur donnée, sous forme de tableau : une ligne par appel, les valeurs retournées remplies de bas en haut.
2. Observer ce que fait chaque appel : quelle partie de la donnée il traite, et ce qu’il ajoute au résultat de l’appel suivant.
3. Généraliser, puis vérifier le rôle trouvé sur une seconde valeur choisie soi-même.

Remarque importante. Le rôle s’exprime par ce que la fonction calcule, pas par la façon dont elle le calcule. « Elle retourne la somme des chiffres de n » est un rôle ; « elle ajoute n Mod 10 à l’appel suivant » n’en est pas un.

5.2 Exemple

Fonction Inconnue (n : Entier) : Entier
DEBUT
    Si n < 10 Alors
        Retourner n
    Sinon
        Retourner n Mod 10 + Inconnue(n Div 10)
    FinSi
FIN

Travail demandé : donner l’exécution manuelle de l’appel Inconnue(2027), puis en déduire le rôle de la fonction Inconnue, sachant que n est un entier positif.

Exécution manuelle

Observer. n Mod 10 est le chiffre des unités de n, et n Div 10 est le nombre n privé de ce chiffre. Chaque appel détache le dernier chiffre et l’ajoute au résultat de l’appel suivant ; le dernier appel retourne le chiffre qui reste. Le résultat est 7 + 2 + 0 + 2 = 11.

Généraliser et vérifier. La fonction Inconnue retourne la somme des chiffres de n. Vérification sur n = 48 : Inconnue(48) = 8 + Inconnue(4) = 8 + 4 = 12, et 4 + 8 = 12.

6. Les erreurs les plus fréquentes

Les erreurs suivantes sont relevées sur les fonctions du cours. Chaque conséquence a été obtenue en exécutant la fonction erronée.

Remarque importante. Les deux premières erreurs, et celle de Dichotomique, ont la même cause : le cas d’arrêt n’est jamais atteint. Devant toute fonction récursive, on vérifie que chaque appel rapproche la donnée du cas d’arrêt.

7. Retenons

Récursivité. Un module est récursif lorsqu’il s’appelle lui-même dans son propre corps, sur des données plus simples.

Deux parties. Un module récursif comporte au moins un cas d’arrêt, résolu sans appel, et un appel récursif qui rapproche la donnée du cas d’arrêt. Sans cela, l’exécution s’interrompt par un débordement de pile.

Trois questions. Quelle donnée évolue d’un appel à l’autre, vers le cas d’arrêt ? Quel est le cas d’arrêt, et que vaut le résultat ? Comment se ramène-t-on à l’appel suivant ?

Exécution. Les appels s’empilent jusqu’au cas d’arrêt, puis se dépilent en retournant leurs valeurs, du dernier appel au premier. Dans une trace, la colonne des valeurs retournées se remplit de bas en haut.

Teste tes connaissances

Un quiz corrigé question par question, puis des flashcards pour mémoriser les notions du chapitre.