Chapitre 4 – La récursivité: Penser comme un programme qui s’appelle lui-même

La récursivité est une méthode de résolution où une fonction s'appelle elle-même pour traiter une version réduite du même problème. C'est une manière élégante et parfois naturelle de penser certains problèmes… à condition de bien poser les bases.

Comprendre la récursivité : Une fonction récursive se décompose toujours en un cas de base qui arrête la récursion et un appel récursif qui traite une version simplifiée du problème. Sans cas de base bien défini, la fonction s'appellera indéfiniment jusqu'à provoquer un débordement de pile (stack overflow).

Visualisation du concept de récursivité fonction(n) fonction(n-1) fonction(n-2) fonction(n-3) Appel récursif Retour de valeur

1. Le principe

Une fonction récursive se compose de deux parties essentielles :

Composant Description Importance
Cas de base Condition qui arrête la récursion Sans lui, la fonction s'appelle indéfiniment (stack overflow)
Appel récursif La fonction s'appelle avec une donnée plus simple Doit se rapprocher du cas de base à chaque appel

Exemple : calcul de la factorielle (n!)

fonction factorielle(n)
  SI n == 0 ALORS retourner 1
  SINON retourner n * factorielle(n - 1)

Trace d'exécution : factorielle(4)

Trace d'exécution : factorielle(4) factorielle(4) 4 × ? factorielle(3) 3 × ? factorielle(2) 2 × ? factorielle(1) 1 × ? factorielle(0) = 1 Retourne 1 1 × 1 = 1 2 × 1 = 2 3 × 2 = 6 4 × 6 = 24 Le cas de base (n=0) arrête la récursion et commence la remontée des résultats

Pile d'appels en mémoire

Pile d'appels pour factorielle(4) factorielle(4) factorielle(3) factorielle(2) factorielle(1) factorielle(0) Début Sommet Ordre d'appel Taille de pile maximale: 5 Attention: Risque de Stack Overflow si trop d'appels!

2. Avantages et limites

Récursif Itératif
Lisibilité ++ +
Performance - ++
Utilisation mémoire -- ++
Complexité du code + -
Idéal pour Arbres, fractales, problèmes naturellement récursifs Calculs simples, boucles, parcours linéaires

Comparaison récursif vs itératif

Avantages de la récursivité :

  • Code plus lisible pour certains problèmes (ex: arbres)
  • Moins de lignes de code
  • Solution élégante pour les problèmes divisibles en sous-problèmes identiques

Inconvénients de la récursivité :

  • Empilement des appels récursifs en mémoire
  • Risque de boucle infinie sans cas de base
  • Moins performant que l'itératif dans certains cas
  • Limité par la taille maximale de la pile d'appels (stack size)
Comparaison de consommation mémoire Taille du problème (n) Mémoire utilisée 10 100 1000 10000 Zone de stack overflow Récursif Itératif

3. Vers l'itératif

Certains algorithmes peuvent être réécrits en version itérative pour économiser la mémoire. Cela demande d'utiliser des structures comme les piles, vues au chapitre suivant.

Version récursive

fonction factorielle(n)
  SI n == 0 ALORS 
      retourner 1
  SINON 
      retourner n * factorielle(n - 1)
  FIN SI
FIN fonction

Version itérative

fonction factorielle(n)
  resultat = 1
  POUR i DE 1 À n FAIRE
      resultat = resultat * i
  FIN POUR
  retourner resultat
FIN fonction

Temps d'exécution comparé (exemple typique)

Taille (n) Récursif Itératif Ratio
10 0.02 ms 0.01 ms 2×
100 0.2 ms 0.05 ms 4×
1000 2.5 ms 0.5 ms 5×
10000 Stack Overflow 5 ms ∞

4. Exemples concrets d'utilisation

Fibonacci

fonction fibonacci(n)
  SI n <= 1 ALORS 
      retourner n
  SINON 
      retourner fibonacci(n-1) + fibonacci(n-2)
  FIN SI
FIN fonction

Note: version naïve, très inefficace pour de grandes valeurs

Parcours d'arbre

fonction parcourir(noeud)
  SI noeud EST NULL ALORS
      retourner
  FIN SI
  
  parcourir(noeud.gauche)
  visiter(noeud)
  parcourir(noeud.droite)
FIN fonction

Recherche dichotomique

fonction recherche(tableau, valeur, debut, fin)
  SI debut > fin ALORS
      retourner -1
  FIN SI
  
  milieu = (debut + fin) / 2
  
  SI tableau[milieu] == valeur ALORS
      retourner milieu
  SINON SI tableau[milieu] > valeur ALORS
      retourner recherche(tableau, valeur, debut, milieu-1)
  SINON
      retourner recherche(tableau, valeur, milieu+1, fin)
  FIN SI
FIN fonction

Tour de Hanoï

fonction hanoi(n, debut, fin, intermediaire)
  SI n == 1 ALORS
      déplacer(debut, fin)
  SINON
      hanoi(n-1, debut, intermediaire, fin)
      déplacer(debut, fin)
      hanoi(n-1, intermediaire, fin, debut)
  FIN SI
FIN fonction

À retenir

1

Toujours définir un cas de base pour arrêter la récursion

2

Chaque appel récursif doit rapprocher du cas de base

3

Attention à la profondeur de récursion et aux limites de la pile

  • La récursivité repose toujours sur un cas de base et un appel récursif
  • C'est utile pour les structures comme les arbres, les fractales, les algorithmes de tri ou de recherche
  • Elle doit être utilisée avec précaution pour éviter les débordements de pile
  • Une fonction récursive peut être transformée en version itérative (souvent plus performante)
  • L'optimisation par queue de récursion (tail recursion) peut améliorer les performances