Accueil › Cours › La récursivité

Les leçons de ce chapitre

1. Une fonction qui s'appelle elle-même
2. Récursivité sur les chaînes
3. De l'itératif au récursif

Leçon 21.1 : Une fonction qui s'appelle elle-même

11 min

Une fonction est récursive quand elle s'appelle elle-même. L'idée : résoudre un problème en le ramenant au même problème, plus petit. Par exemple n! = n × (n − 1)! : pour calculer 5!, il suffit de savoir calculer 4!.

• Une condition d'arrêt (cas de base) : un cas simple qui se calcule sans appel. Pour la factorielle : 0! = 1.
• Un appel récursif sur un problème plus petit, qui se rapproche du cas de base : n * fact(n - 1).

Attention : Sans condition d'arrêt, ou si l'appel ne se rapproche pas du cas de base, la fonction s'appelle sans fin : Python s'arrête avec une erreur RecursionError.

Astuce : Chaque appel attend le résultat du suivant. fact(3) attend fact(2), qui attend fact(1), qui attend fact(0) = 1 ; puis les multiplications se font en remontant : 1, 1, 2, 6.

En Python

La factorielle, écrite de façon récursive.

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

n = int(input())
print(n, "! =", fact(n))

En algorithme

Même fonction en algorithme : elle s'appelle elle-même dans le Sinon.

DEF FN fact (n : Entier) : Entier
Début
  Si n = 0 Alors
    Retourner 1
  Sinon
    Retourner n * fact(n - 1)
  FinSi
Fin

Algorithme Factorielle
Début
  Lire(n)
  Ecrire(n, " ! = ", fact(n))
Fin

TDO
Objet | Type/Nature
n | Entier

Leçon 21.2 : Récursivité sur les chaînes

11 min

Une chaîne se traite aussi récursivement : on regarde le premier ou le dernier caractère, puis on appelle la fonction sur le reste de la chaîne. Le cas de base est souvent la chaîne vide ou d'un seul caractère.

• Palindrome : un mot qui se lit pareil dans les deux sens (radar). Il l'est si le premier et le dernier caractères sont égaux et si le milieu est un palindrome.
• En Python, ch[1:len(ch) - 1] est le milieu ; en algorithme sous_chaine(ch, 1, long(ch) - 1).

Astuce : Le résultat d'une fonction récursive booléenne peut s'écrire avec et : ch[0] == ch[-1] and palindrome(milieu).

En Python

Le test du palindrome, récursif.

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

mot = input()
if palindrome(mot):
    print(mot, "est un palindrome")
else:
    print(mot, "n'est pas un palindrome")

En algorithme

sous_chaine(ch, 1, long(ch) - 1) enlève le premier et le dernier caractère.

DEF FN palindrome (ch : Chaîne) : Booléen
Début
  Si long(ch) ≤ 1 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

Algorithme Palindrome
Début
  Lire(mot)
  Si palindrome(mot) Alors
    Ecrire(mot, " est un palindrome")
  Sinon
    Ecrire(mot, " n'est pas un palindrome")
  FinSi
Fin

TDO
Objet | Type/Nature
mot | Chaîne

Leçon 21.3 : De l'itératif au récursif

10 min

Beaucoup d'algorithmes qu'on écrit avec une boucle ont une forme récursive naturelle. L'algorithme d'Euclide en est un exemple : PGCD(a, b) = a si b = 0, sinon PGCD(a, b) = PGCD(b, a mod b).

• Ce qui change à chaque tour de boucle devient les paramètres du nouvel appel.
• La condition d'arrêt de la boucle devient le cas de base.

Astuce : La forme récursive est souvent plus courte et proche de la définition mathématique ; la forme itérative utilise moins de mémoire.

En Python

Le PGCD par Euclide, en récursif.

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

a = int(input())
b = int(input())
print("PGCD =", pgcd(a, b))

En algorithme

Le nouvel appel reçoit b et a mod b.

DEF FN pgcd (a, b : Entier) : Entier
Début
  Si b = 0 Alors
    Retourner a
  Sinon
    Retourner pgcd(b, a mod b)
  FinSi
Fin

Algorithme Euclide
Début
  Lire(a)
  Lire(b)
  Ecrire("PGCD = ", pgcd(a, b))
Fin

TDO
Objet | Type/Nature
a, b | Entier

S'entraîner gratuitement

Chaque leçon a 3 exercices gratuits avec indices pour appliquer ce chapitre avec Hannibot.

← Chapitre précédent : Approximation et optimisation · Chapitre suivant : Les algorithmes récurrents →

Tous les chapitres · Voir les devoirs corrigés de 2ème TI

Cours écrit pour Mission Carthage d'après le programme officiel. Ton professeur reste la référence.