Comment corriger une erreur « stack overflow » ?

La récursivité, concept fondamental en informatique, consiste à résoudre un problème en le décomposant en sous-problèmes similaires. Elle se traduit souvent par des fonctions qui s’appellent elles-mêmes jusqu’à atteindre une condition d’arrêt. Cependant, cette approche peut entraîner des problèmes de performance ou des erreurs, notamment des dépassements de pile (« stack overflow »).
Pour éviter ces erreurs, il est essentiel de définir correctement les conditions d’arrêt dans les fonctions récursives, ou trouver un algorithme alternatif permettant d’obtenir le même résultat. Découvrons ensemble comment corriger une erreur « stack overflow » avec un exemple en Python.

Un exemple de fonction récursive

Considérons la fonction deep_flatten qui a pour objectif de transformer un tableau contenant des entiers ou des listes d’entiers en une liste contenant tous les entiers contenus dans les listes en profondeur.
Par exemple, si nous appelons deep_flatten avec la liste [1, [2, [3, 4], 5], [6, [7]]] en paramètre, la valeur de retour devrait être [1, 2, 3, 4, 5, 6, 7].

L’implémentation de cette fonction peut se faire en utilisant le principe de récursivité :

#!/usr/bin/env python3
#! -*- coding: utf-8 -*-

def deep_flatten(items):
    """Return a list containing items on its first level from list containing deep list of items"""
    out = []
    for item in items:
        if isinstance(item, list): # When item is a list apply same logic for its items
            out.extend(
                deep_flatten(item)
            )
        else: # It's a standard item,
            out.append(item)

    return out

if __name__ == "__main__":
    original = [1, [2, [3, 4], 5], [6, [7]]]

    print(deep_flatten(original)) # [1, 2, 3, 4, 5, 6, 7]

Le principal avantage de cette implémentation est sa simplicité. En effet, lorsque l’élément est une liste, nous appliquons récursivement le même traitement, sinon nous récupérons l’élément tel quel. En testant cette version avec les données de l’exemple précédent, nous constatons que le résultat obtenu correspond à celui attendu.

L’échec de la récursivité

Nous pourrions donc considérer que l’implémentation actuelle de deep_flatten est correcte et ne présente aucun bogue. En effet, les conditions d’arrêt et la logique algorithmique sont correctes, ce qui permet au programme de s’exécuter correctement.

L’erreur « stack overflow »

Pourtant, comme le montre l’exemple suivant, lorsque les données ont un niveau de profondeur plus important le programme remonte une erreur d’exécution.

 # ...

 if __name__ == "__main__":
-    original = [1, [2, [3, 4], 5], [6, [7]]]
+    # Generate an original list containing 1000 level
+    original = []
+    last = original
+    for _ in range(999):
+        last.append([])
+        last = last[0]
+    last.extend([1, 2, 3])

     print(deep_flatten(original))

La modification du script nous permet de générer une liste original, qui contient des sous listes imbriquées jusqu’à atteindre une profondeur de 1 000 niveaux. Au bout de cette hiérarchie, nous trouvons les entiers 1, 2, et 3.
Après modification, l’exécution du script provoque l’erreur suivante dans le terminal :

$ python3 main.py
Traceback (most recent call last):
  File "./main.py", line 27, in <module>
    print(deep_flatten(original))
          ^^^^^^^^^^^^^^^^^^^^^^^
  ...
  File "./main.py", line 10, in deep_flatten
    deep_flatten(item)
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

Analyse de l’erreur

Cette erreur RecursionError, similaire aux exceptions StackOverflowException (c#) ou StackOverflowError (Java), etc. survient lorsque la pile d’exécution a atteint sa limite. L’interpréteur ou le programme compilé ne peut plus empiler les appels à la fonction suivante et termine donc en erreur.

Un moyen de contournement rapide, et très courant est d’augmenter la taille de la stack. Cependant, si le problème arrive une première fois dans votre programme, il est très probable qu’il surviennent de nouveau !

Comment corriger ce problème ?

Malgré la solution consistant à augmenter la taille de la stack au niveau du système d’exploitation ou de l’interpréteur, il est préférable, à long terme, d’envisager un algorithme plus robuste !

La stratégie de la pile logique

Dans notre situation, comme de nombreuses situations où un programme traite des objets et/ou des collections en profondeurs, nous pouvons revoir la logique en utilisant une pile logique. La nouvelle implémentation de deep_flatten est modifiée en ce sens :

# ...

def deep_flatten(items):
    """Return a list containing items on its first level from list containing deep list of items"""
    out = []

    last = {"index": 0, "items": items} # <1>
    stack = []

    while last is not None:
        # Reset context from last variable
        items = last["items"]

        for index in range(last["index"], len(items)): # Continue the loop from stacked index
            item = items[index]

            if isinstance(item, list): # When item is a list, stack and apply logic for its items
                last["index"] = index + 1 # Update the index to restart at next index
                stack.append(last) # <2>

                last = {"index": 0, "items": item} # <3>
                break
            else: # It's a standard item, flatten item
                out.append(item)
        else:
            # No break, the current context list is completed
            last = stack.pop() if stack else None # <4>

    return out

# ...

Explication de la correction

Ce nouvel algorithme traite les différents niveaux de la liste en paramètre en émulant le fonctionnement sous-jacent de la pile d’appels de fonction de l’interpréteur Python. Contrairement à la version précédente de l’algorithme, cette nouvelle approche déporte la limite du nombre d’appels de fonctions sur celle de la mémoire vive (RAM) disponible du calculateur.

Lorsqu’un élément de type liste est détecté, la boucle met en pause l’exécution du contexte courant pour traiter cette liste via un nouveau contexte (variable last). Le contexte courant est sauvegardé dans la pile logique stack pour une reprise ultérieure. Il est constitué de l’information permettant de reprendre le traitement du contexte (variable index), et de la valeur anciennement passée en paramètre à la fonction (variable items).

De cette manière, l’algorithme gère la récursivité en répétant le traitement grâce à la boucle while, tout en sauvegardant et restaurant le contexte de la boucle à l’aide de la pile logique.

Conclusion

Malgré les risques potentiels de dysfonctionnement liés à l’utilisation de la récursivité dans un programme, la récursivité n’est pas nécessairement à proscrire.
En effet, comme vous l’avez constaté dans la première version de la fonction, l’écriture d’une fonction qui s’appelle elle-même permet de simplifier considérablement l’algorithme. En revanche, la version utilisant une boucle nécessite une attention plus soutenue lors de sa conception pour obtenir le même résultat.

Les appels récursifs peuvent être tolérés dès lors que le nombre d’appels récursifs est fini et inférieur aux limites de la pile d’appel. Cependant, lorsque ce nombre est variable, ou lorsque nous travaillons sur des systèmes sensibles ou disposant de ressources limitées, il est préférable de privilégier des algorithmes alternatifs qui s’appuient sur d’autres stratégies. La seconde version de la fonction est un bon exemple, où nous avons déporté les limites de la pile d’exécution sur celles de la mémoire vive.