Risque de Stack Overflow en Récursivité

Introduction

Dans notre leçon précédente, nous avons comparé les approches itératives (avec des boucles) et récursives. Vous avez appris que si la récursivité peut offrir des solutions élégantes, elle comporte un risque majeur lié à son utilisation de la pile d'appels : le dépassement de pile, ou stack overflow.

Aujourd'hui, nous allons nous attaquer directement à ce concept. L'objectif est de comprendre en profondeur ce qu'est un stack overflow, pourquoi il est particulièrement lié à une récursivité mal contrôlée, et comment s'en prémunir. Maîtriser ce risque est une étape essentielle pour atteindre votre but : écrire du code non seulement "clean", mais aussi robuste et fiable.

1. La Pile d'Appels : une Mémoire Limitée

Rappelez-vous de notre exploration de la pile d'appels. Chaque fois qu'une fonction est appelée, un "contexte" ou "cadre" contenant ses informations (paramètres, variables locales) est empilé. Lorsque la fonction se termine, son cadre est dépilé.

La question cruciale est : que se passe-t-il si on empile sans jamais dépiler, ou si on empile trop de cadres ?

La réponse est simple : la pile d'appels, comme toute mémoire dans un ordinateur, n'est pas infinie. Elle a une taille fixe et limitée. Si une série d'appels de fonction remplit cet espace mémoire jusqu'à la dernière place, toute tentative d'ajouter un cadre supplémentaire provoquera une erreur critique : le dépassement de pile (stack overflow). Le programme s'arrête alors brutalement car il n'a plus l'espace nécessaire pour fonctionner.

Voyons ce que cela donne en pratique.

Cet exemple est fondamental : même avec une logique algorithmique correcte (un cas de base et une progression vers celui-ci), la récursivité peut échouer si la "profondeur" du problème dépasse la capacité de la pile.

2. Les Deux Causes Principales du Stack Overflow

Un dépassement de pile dans un contexte récursif provient généralement de l'un des deux scénarios suivants. L'article suivant, bien qu'orienté vers le langage C, décrit ces causes de manière universelle.

Synthétisons ces deux causes majeures :

Cause 1 : La Récursion Infinie (un défaut de logique)

C'est la cause la plus directe. La fonction s'appelle elle-même sans jamais atteindre de condition d'arrêt. C'est l'équivalent récursif d'une boucle Tant que VRAI FAIRE ... FIN TANT QUE. La pile se remplit jusqu'à déborder.

Cela se produit principalement dans deux cas :

• Absence totale de cas de base : La fonction ne sait tout simplement pas quand s'arrêter.

  Fonction Bug_Recursif(n : Entier)
  DEBUT
      // Il n'y a pas de 'SI ... ALORS RETOURNER' pour arrêter.
      Bug_Recursif(n - 1)
  FIN
  

• Cas de base inatteignable : Il existe un cas de base, mais la logique de l'appel récursif l'évite.

  Fonction Bug_Recursif_Subtil(n : Entier)
  DEBUT
      SI (n = 0) ALORS  // Le cas de base est n=0
          RETOURNER 0
      SINON
          // L'appel s'éloigne du cas de base au lieu de s'en approcher !
          RETOURNER n + Bug_Recursif_Subtil(n + 1) 
      FIN SI
  FIN
  

  Si on appelle Bug_Recursif_Subtil(5), les appels suivants seront pour 6, 7, 8, ... et n'atteindront jamais 0.

Cause 2 : La Récursion Trop Profonde (une limite de ressource)

C'est le scénario que nous avons vu dans le premier article (LINK). Ici, l'algorithme est logiquement correct : il a un cas de base et chaque appel s'en approche. Cependant, le nombre d'appels nécessaires pour résoudre le problème est si grand qu'il dépasse la capacité physique de la pile.

Par exemple, notre fonction Factorielle_Recursive(n) est logiquement parfaite. Mais si nous essayons de l'appeler avec un très grand nombre, comme Factorielle_Recursive(100000), elle tentera d'empiler 100 000 cadres d'appel avant d'atteindre le cas de base n=0. La plupart des systèmes d'exploitation allouent bien moins d'espace que cela à la pile, et un stack overflow se produira bien avant la fin.

3. Comment Prévenir le Stack Overflow ?

Puisque vous visez l'écriture de code de qualité, il est crucial de savoir comment concevoir des algorithmes qui ne s'effondrent pas de cette manière.

Solution n°1 : La Rigueur dans la Conception

La première ligne de défense est une conception irréprochable, comme le souligne l'article de LabEx.

1. Définissez toujours un cas de base clair et atteignable. C'est la règle d'or.
2. Vérifiez que chaque appel récursif vous rapproche du cas de base. Analysez la manière dont les paramètres évoluent. Est-ce que n diminue bien vers 0 ? Est-ce que la taille de la liste se réduit ?

Solution n°2 : La Transformation en Itération

Comme nous l'avons vu dans la leçon précédente, toute fonction récursive peut être réécrite de manière itérative avec une boucle. Si vous anticipez qu'un problème pourrait nécessiter une grande profondeur de récursion, la solution la plus robuste est souvent de choisir l'approche itérative dès le départ.

Repensez à Factorielle_Iterative(100000). Cette version n'utilise qu'un seul cadre sur la pile et met simplement à jour ses variables (total, i) dans une boucle. Elle ne risque aucun stack overflow et calculera le résultat (bien que le nombre soit si énorme qu'il dépasserait la capacité d'un type Entier standard, mais c'est un autre problème !).

Solution n°3 (avancée) : La Limitation de Profondeur

Une technique de sécurité consiste à "instrumenter" votre fonction récursive avec un compteur pour l'arrêter de force si elle va trop loin.

En pseudo-code, cela ressemblerait à ceci :

Constante MAX_PROFONDEUR = 1000

Fonction Recursive_Securisee(parametre, profondeur_actuelle)
DEBUT
    SI (profondeur_actuelle > MAX_PROFONDEUR) ALORS
        // On arrête tout et on signale une erreur
        RETOURNER ERREUR("Profondeur de récursion maximale atteinte")
    FIN SI

    // --- Cas de base ---
    SI (condition_arret) ALORS
        RETOURNER resultat_base
    // --- Cas récursif ---
    SINON
        RETOURNER ... Recursive_Securisee(nouveau_parametre, profondeur_actuelle + 1)
    FIN SI
FIN

Cette approche ne résout pas le problème de fond, mais elle empêche le programme de planter et permet de gérer l'erreur proprement.

Conclusion

Félicitations ! Vous avez maintenant une compréhension complète des forces et des faiblesses de la récursivité.

Les points clés à retenir :

• Le dépassement de pile (stack overflow) est une erreur qui se produit lorsque la pile d'appels est pleine.
• En récursivité, il est causé soit par une récursion infinie (un bug dans la logique), soit par une récursion trop profonde (une limite de ressources système).
• La meilleure prévention est une conception rigoureuse (cas de base clair, progression garantie) ou le choix d'une solution itérative lorsque la profondeur de récursion risque d'être importante.

Comprendre ce risque et savoir quand éviter la récursivité est une marque de maturité en tant que développeur, vous rapprochant de votre objectif de produire un code "clean" et fiable.

Et après ?

Vous avez terminé le module sur l'introduction à la récursivité ! C'est un concept dense, et vous l'avez brillamment maîtrisé. Dans le prochain module, "Algorithmes de Recherche et Tri", nous allons mettre en pratique tout ce que vous avez appris (variables, conditions, boucles, et même la récursivité) pour résoudre des problèmes fondamentaux en informatique : comment trouver efficacement une information dans un ensemble de données, et comment organiser cet ensemble.