Aller au contenu principal

La récursivité

Introduction​

Définition

En programmation, le concept de récursivité désigne une fonction qui s’appelle elle-même.

Pour bien comprendre, imaginons une fonction qui explore des dossiers sur un ordinateur.

Chaque dossier peut contenir :

  • des fichiers simples 📄 ;
  • d’autres dossiers 📁 à explorer à leur tour.

Plutôt que d’écrire une fonction compliquée qui gère tous les niveaux à la fois, on peut écrire une fonction qui fait toujours la même chose :

“Parcours le contenu du dossier courant, et si tu trouves un sous-dossier, appelle-toi pour explorer ce sous-dossier.”

Pile d’exécution : comprendre ce qu’il se passe​

Pour exécuter du code, Python utilise une pile d’appels (ou pile d’exécution).

À chaque fois qu’une fonction est appelée :

  • Python la place sur le dessus de la pile,
  • exécute son contenu,
  • puis la retire (dépile) une fois terminée.

Imaginons deux fonctions :

def fctA():
    print("Début de A")
    print("Fin de A")

def fctB():
    print("Début de B")
    fctA()
    print("Fin de B")

fctB()

Voici ce qu’il se passe :

  1. fctB() est appelée → elle est mise sur la pile.
  2. À l’intérieur, fctA() est appelée → on l'empile au-dessus.
  3. fctA() s’exécute entièrement puis se dépile.
  4. On reprend fctB() là où on s’était arrêté.

En récursivité, le même schéma s'applique : la fonction appelée est empiliée sur la pile d'exécution, et si elle s'appelle elle-même, alors cette même fonction s'empilera, et le programme s'arrêtera lorsque toutes les fonctions auront été exécutées et dépilées.

Définition de la récursivité​

Une fonction récursive est une fonction qui s’appelle elle-même.

def explore(dossier):
    for element in dossier:
        if element.est_un_fichier():
            print(element.nom)
        else:
            explore(element)  # appel récursif !

Ici, la fonction explore() s’appelle à nouveau pour chaque sous-dossier.
Chaque appel crée une nouvelle instance de la fonction dans la pile d’exécution.

Les deux cas d’une fonction récursive​

Une fonction récursive doit toujours distinguer deux cas :

  1. Le cas d’arrêt : celui où la fonction ne doit plus s’appeler elle-même.
  2. Le cas général : celui où la fonction continue de s’appeler.
Exemple

Imaginons qu’on veuille afficher un compte à rebours :

def compte_a_rebours(n):
    if n == 0:                # ✅ cas d’arrêt
        print("Décollage !")
    else:                     # 🔁 cas général
        print(n)
        compte_a_rebours(n - 1)

👉 Ici :

  • Cas général : on affiche n puis on s’appelle avec n-1.
  • Cas d’arrêt : quand n vaut 0, on s’arrête.

Comment raisonner face à un problème récursif​

Démarche conseillée
  1. Identifier le cas d’arrêt (quand doit-on s’arrêter ?).
  2. Identifier le cas général (quelle action se répète ?).
  3. Vérifier que chaque appel rapproche du cas d’arrêt.

Une erreur classique est d’oublier le cas d’arrêt : dans ce cas, la fonction s’appelle à l’infini jusqu’à provoquer un dépassement de pile (RecursionError en Python).

Exemple mathématique : somme des n premiers entiers​

Formule connue :

  • S(n) = n + S(n-1) avec
  • S(0) = 0

Traduit en Python :

def somme(n):
    if n == 0:         # cas d'arrêt
        return 0
    else:              # cas général
        return n + somme(n - 1)

Appelons somme(3) :

somme(3)
→ 3 + somme(2)
→ 3 + (2 + somme(1))
→ 3 + (2 + (1 + somme(0)))
→ 3 + (2 + (1 + 0))
= 6
Visualisation

Chaque appel est mis sur la pile, puis “se résout” quand on revient en arrière :

somme(3)
 └── somme(2)
      └── somme(1)
           └── somme(0)

À retenir​

Résumé
  • Une fonction récursive s’appelle elle-même.
  • Il faut toujours définir :
    • un cas d’arrêt (condition de fin),
    • un cas général (ce qui se répète).
  • Chaque appel est placé sur la pile d’exécution, puis dépilé à la fin.
  • La récursivité permet d’écrire des fonctions élégantes pour des problèmes répétitifs (exploration de dossiers, structures arborescentes, suites mathématiques, etc.).