Java Language StackOverflowError & récursivité en boucle


Exemple

Si un appel récursif devient "trop ​​profond", cela se traduit par une StackOverflowError . Java alloue une nouvelle image pour chaque appel de méthode sur la pile de son thread. Cependant, l'espace de la pile de chaque thread est limité. Trop de cadres sur la pile mènent au dépassement de pile (SO).

Exemple

public static void recursion(int depth) {
    if (depth > 0) {
        recursion(depth-1);
    }
}

L'appel de cette méthode avec des paramètres importants (par exemple, la recursion(50000) entraînera probablement un débordement de pile. La valeur exacte dépend de la taille de la pile de threads, qui dépend à son tour de la structure du thread, des paramètres de ligne de commande tels que -Xss ou taille par défaut pour la JVM.

solution de contournement

Une récursivité peut être convertie en une boucle en stockant les données pour chaque appel récursif dans une structure de données. Cette structure de données peut être stockée sur le tas plutôt que sur la pile de threads.

En général, les données requises pour restaurer l'état d'une invocation de méthode peuvent être stockées dans une pile et une boucle while peut être utilisée pour "simuler" les appels récursifs. Les données pouvant être requises incluent:

  • l'objet pour lequel la méthode a été appelée (méthodes d'instance uniquement)
  • les paramètres de la méthode
  • variables locales
  • la position actuelle dans l'exécution ou la méthode

Exemple

La classe suivante permet de récurer une arborescence jusqu'à une profondeur spécifiée.

public class Node {

    public int data;
    public Node left;
    public Node right;

    public Node(int data) {
        this(data, null, null);
    }

    public Node(int data, Node left, Node right) {
        this.data = data;
        this.left = left;
        this.right = right;
    }

    public void print(final int maxDepth) {
        if (maxDepth <= 0) {
            System.out.print("(...)");
        } else {
            System.out.print("(");
            if (left != null) {
                left.print(maxDepth-1);
            }
            System.out.print(data);
            if (right != null) {
                right.print(maxDepth-1);
            }
            System.out.print(")");
        }
    }

}

par exemple

Node n = new Node(10, new Node(20, new Node(50), new Node(1)), new Node(30, new Node(42), null));
n.print(2);
System.out.println();

Des tirages

(((...)20(...))10((...)30))

Cela pourrait être converti à la boucle suivante:

public class Frame {

    public final Node node;

    // 0: before printing anything
    // 1: before printing data
    // 2: before printing ")"
    public int state = 0;
    public final int maxDepth;

    public Frame(Node node, int maxDepth) {
        this.node = node;
        this.maxDepth = maxDepth;
    }

}
List<Frame> stack = new ArrayList<>();
stack.add(new Frame(n, 2)); // first frame = initial call

while (!stack.isEmpty()) {
    // get topmost stack element
    int index = stack.size() - 1;
    Frame frame = stack.get(index); // get topmost frame
    if (frame.maxDepth <= 0) {
        // termial case (too deep)
        System.out.print("(...)");
        stack.remove(index); // drop frame
    } else {
        switch (frame.state) {
            case 0:
                frame.state++;

                // do everything done before the first recursive call
                System.out.print("(");
                if (frame.node.left != null) {
                    // add new frame (recursive call to left and stop)
                    stack.add(new Frame(frame.node.left, frame.maxDepth - 1));
                    break;
                }
            case 1:
                frame.state++;

                // do everything done before the second recursive call
                System.out.print(frame.node.data);
                if (frame.node.right != null) {
                    // add new frame (recursive call to right and stop)
                    stack.add(new Frame(frame.node.right, frame.maxDepth - 1));
                    break;
                }
            case 2:
                // do everything after the second recursive call & drop frame
                System.out.print(")");
                stack.remove(index);
        }
    }
}
System.out.println();

Note: Ceci est juste un exemple de l'approche générale. Souvent, vous pouvez trouver une meilleure façon de représenter un cadre et / ou de stocker les données du cadre.