Java Language
Rekursion

Einführung

Bemerkungen

Die Grundidee der Rekursion

Was ist Rekursion:

Rekursion ist im Allgemeinen, wenn eine Funktion sich direkt oder indirekt aufruft. Zum Beispiel:

// This method calls itself "infinitely"
public void useless() {
    useless();  // method calls itself (directly)
}

Bedingungen für das Anwenden einer Rekursion auf ein Problem:

Es gibt zwei Voraussetzungen für die Verwendung rekursiver Funktionen zur Lösung eines bestimmten Problems:

1. Es muss eine Basisbedingung für das Problem geben, die der Endpunkt für die Rekursion sein wird. Wenn eine rekursive Funktion die Basisbedingung erreicht, führt sie keine weiteren (tieferen) rekursiven Aufrufe aus.

2. Jede Rekursionsebene sollte ein kleineres Problem versuchen. Die rekursive Funktion unterteilt das Problem somit in immer kleinere Teile. Vorausgesetzt, dass das Problem endlich ist, wird sichergestellt, dass die Rekursion beendet wird.

In Java gibt es eine dritte Voraussetzung: Es sollte nicht notwendig sein, zu tief zu rekursieren, um das Problem zu lösen. siehe Deep Rekursion ist in Java problematisch

Beispiel

Die folgende Funktion berechnet die Fakultäten anhand der Rekursion. Beachten Sie, wie sich die Methode factorial innerhalb der Funktion aufruft. Bei jedem Aufruf von selbst wird der Parameter n um 1 reduziert. Wenn n den Wert 1 (Basisbedingung) erreicht, wird die Funktion nicht tiefer rekonstieren.

public int factorial(int n) {
    if (n <= 1) { // the base condition 
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}

^{Dies ist keine praktische Methode zum Berechnen von Fakultäten in Java, da Integer-Überlauf oder Aufruf-Stack-Überlauf (dh StackOverflowError Ausnahmen) für große Werte von n nicht berücksichtigt werden.}

Berechnung der N-ten Fibonacci-Zahl

Die folgende Methode berechnet die Nte Fibonacci-Zahl unter Verwendung der Rekursion.

public int fib(final int n) {
    if (n > 2) {
        return fib(n - 2) + fib(n - 1);
    }
    return 1;
}

Das Verfahren implementiert einen Basisfall (n <= 2) und einen rekursiven Fall (n> 2). Dies veranschaulicht die Verwendung der Rekursion zum Berechnen einer rekursiven Beziehung.

Dieses Beispiel ist zwar veranschaulichend, aber auch ineffizient: Jede einzelne Instanz der Methode ruft die Funktion zweimal auf, was zu einem exponentiellen Wachstum der Anzahl der Aufrufe der Funktion führt, wenn N zunimmt. Die obige Funktion ist O (2 ^N ), aber eine äquivalente iterative Lösung hat die Komplexität O (N). Darüber hinaus gibt es einen Ausdruck "geschlossener Form", der in O (N) Gleitkommamultiplikationen ausgewertet werden kann.

Berechnen der Summe der Zahlen von 1 bis N

Die folgende Methode berechnet die Summe der Ganzzahlen von 0 bis N unter Verwendung der Rekursion.

public int sum(final int n) {
    if (n > 0) {
        return n + sum(n - 1);
    } else {
        return n;
    }
}

Diese Methode ist O (N) und kann mithilfe der Tail Call-Optimierung auf eine einfache Schleife reduziert werden. Tatsächlich gibt es einen Ausdruck in geschlossener Form , der die Summe in O(1) -Operationen berechnet.

Berechnung der N-ten Potenz einer Zahl

Die folgende Methode berechnet den Wert von num , der mit exp auf exp erhöht wurde:

public long power(final int num, final int exp) {
    if (exp == 0) {
        return 1;
    }
    if (exp == 1) {
        return num;
    }
    return num * power(num, exp - 1);
}

Dies veranschaulicht die oben genannten Prinzipien: Die rekursive Methode implementiert einen Basisfall (zwei Fälle, n = 0 und n = 1), der die Rekursion beendet, und einen rekursiven Fall, der die Methode erneut aufruft. Diese Methode ist O (N) und kann mithilfe der Tail Call-Optimierung auf eine einfache Schleife reduziert werden.

Umkehren einer Zeichenfolge mit Rekursion

Nachfolgend finden Sie einen rekursiven Code zum Umkehren einer Zeichenfolge

/**
 * Just a snippet to explain the idea of recursion
 *
 **/

public class Reverse {
    public static void main (String args[]) {
        String string = "hello world";
        System.out.println(reverse(string)); //prints dlrow olleh
    }

    public static String reverse(String s) {
        if (s.length() == 1) {
            return s;
        }
    
        return reverse(s.substring(1)) + s.charAt(0);
    }
}

Durchlaufen einer Baumdatenstruktur mit Rekursion

Betrachten Sie die Knotenklasse mit 3 Elementdaten, linkem unterem Zeiger und rechtem unterem Zeiger wie unten.

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

Wir können den Baum durchqueren, der durch Verbinden der Objekte mehrerer Node-Klassen wie unten erstellt wurde. Der Durchlauf wird als Durchlauf des Baums in der Reihenfolge bezeichnet.

public static void inOrderTraversal(Node root) {
        if (root != null) {          
            inOrderTraversal(root.left); // traverse left sub tree
            System.out.print(root.data + " "); // traverse current node
            inOrderTraversal(root.right); // traverse right sub tree
        }
    }

Wie oben gezeigt, können wir mithilfe der Rekursion die Baumdatenstruktur durchlaufen , ohne eine andere Datenstruktur zu verwenden, die mit dem iterativen Ansatz nicht möglich ist.

Arten der Rekursion

Rekursion kann je nach dem Ort des rekursiven Methodenaufrufs entweder als Head-Rekursion oder als Tail-Rekursion kategorisiert werden.

Bei der Rekursion "head" kommt der rekursive Aufruf, wenn er auftritt, vor einer anderen Verarbeitung in der Funktion (denken Sie daran, dass dies am Anfang oder Kopf der Funktion geschieht).

Bei der Tail-Rekursion ist es genau umgekehrt: Die Verarbeitung erfolgt vor dem rekursiven Aufruf. Die Wahl zwischen den beiden rekursiven Stilen mag beliebig erscheinen, aber die Wahl kann den Unterschied ausmachen.

Eine Funktion mit einem Pfad mit einem einzelnen rekursiven Aufruf am Anfang des Pfads verwendet die sogenannte Rekursion "head". Die faktorielle Funktion eines vorherigen Exponats verwendet die Rekursion des Kopfes. Sobald er feststellt, dass eine Rekursion erforderlich ist, ruft er sich zuerst mit dem dekrementierten Parameter auf. Eine Funktion mit einem einzelnen rekursiven Aufruf am Ende eines Pfads verwendet die Tail-Rekursion.

public void tail(int n)              public void head(int n)
{                                       {
   if(n == 1)                             if(n == 0)
      return;                                return;
   else                                   else
      System.out.println(n);                 head(n-1);

   tail(n-1);                              System.out.println(n);
}                                        }

Wenn der rekursive Aufruf am Ende einer Methode auftritt, wird dies als tail recursion . Die Schwanzrekursion similar to a loop . Die method executes all the statements before jumping into the next recursive call .

Wenn der rekursive Aufruf am beginning of a method, it is called a head recursion auftritt beginning of a method, it is called a head recursion . Die method saves the state before jumping into the next recursive call .

Referenz: Der Unterschied zwischen Rekursion von Kopf und Schwanz

StackOverflowError & Rekursion in Schleife

Wenn ein rekursiver Aufruf "zu tief" geht, führt dies zu einem StackOverflowError . Java ordnet jedem Methodenaufruf im Stack seines Threads einen neuen Frame zu. Der Platz des Stapels jedes Threads ist jedoch begrenzt. Zu viele Frames auf dem Stack führen zum Stack Overflow (SO).

Beispiel

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

Das Aufrufen dieser Methode mit großen Parametern (z. B. recursion(50000) wahrscheinlich zu einem Stapelüberlauf. Der genaue Wert hängt von der Thread-Stack-Größe ab, die wiederum von der Threadkonstruktion, den Befehlszeilenparametern wie -Xss oder der -Xss ist Standardgröße für die JVM.

Problemumgehung

Eine Rekursion kann in eine Schleife konvertiert werden, indem die Daten für jeden rekursiven Aufruf in einer Datenstruktur gespeichert werden. Diese Datenstruktur kann auf dem Heapspeicher statt auf dem Threadstapel gespeichert werden.

Im Allgemeinen können die Daten, die zum Wiederherstellen des Zustands eines Methodenaufrufs erforderlich sind, in einem Stapel gespeichert werden, und eine While-Schleife kann verwendet werden, um die rekursiven Aufrufe zu "simulieren". Zu den Daten, die möglicherweise erforderlich sind, gehören:

• das Objekt, für das die Methode aufgerufen wurde (nur Instanzmethoden)
• die Methodenparameter
• lokale Variablen
• die aktuelle Position in der Ausführung oder der Methode

Beispiel

Die folgende Klasse ermöglicht das rekursive Drucken einer Baumstruktur bis zu einer angegebenen Tiefe.

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(")");
        }
    }

}

z.B

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();

Drucke

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

Dies könnte in die folgende Schleife umgewandelt werden:

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();

Hinweis: Dies ist nur ein Beispiel für den allgemeinen Ansatz. Häufig können Sie einen viel besseren Weg finden, einen Frame darzustellen und / oder die Frame-Daten zu speichern.

Die tiefe Rekursion ist in Java problematisch

Betrachten Sie die folgende naive Methode zum Hinzufügen zweier positiver Zahlen mithilfe der Rekursion:

public static int add(int a, int b) {
    if (a == 0) {
        return b;
    } else {
        return add(a - 1, b + 1);  // TAIL CALL
    }
}

Das ist algorithmisch korrekt, hat aber ein großes Problem. Wenn Sie add mit einem großen a aufrufen add stürzt es mit einem StackOverflowError auf einer beliebigen Java-Version bis mindestens Java 9 ab.

In einer typischen funktionalen Programmiersprache (und vielen anderen Sprachen) optimiert der Compiler die Rekursion des Endes . Der Compiler würde feststellen, dass der Aufruf zum add (an der markierten Zeile) ein Tail-Aufruf ist , und die Rekursion als Schleife neu schreiben. Diese Umwandlung wird als Tail-Call-Eliminierung bezeichnet.

Java-Compiler der aktuellen Generation führen jedoch keine Tail Call-Eliminierung durch. (Dies ist kein einfaches Versehen. Hierfür gibt es wesentliche technische Gründe; siehe unten.) Stattdessen führt jeder rekursive Aufruf von add dass ein neuer Frame auf dem Stack des Threads zugewiesen wird. Wenn Sie beispielsweise add(1000, 1) aufrufen, werden 1000 rekursive Anrufe benötigt, um bei der Antwort 1001 anzukommen.

Das Problem ist, dass die Größe des Java-Thread-Stacks beim Erstellen des Threads festgelegt wird. (Dazu gehört der "main" -Thread in einem Singlethread-Programm.) Wenn zu viele Stack-Frames zugewiesen werden, läuft der Stack über. Die JVM erkennt dies und gibt einen StackOverflowError .

Ein Ansatz, um damit umzugehen, besteht darin, einfach einen größeren Stapel zu verwenden. Es gibt JVM-Optionen, die die Standardgröße eines Stacks steuern. Sie können auch die Stackgröße als Thread Konstruktorparameter angeben. Leider "schiebt" dies nur den Stapelüberlauf. Wenn Sie eine Berechnung durchführen müssen, die einen noch größeren Stack erfordert, wird der StackOverflowError zurückgegeben.

Die eigentliche Lösung besteht darin, rekursive Algorithmen zu identifizieren, bei denen eine tiefe Rekursion wahrscheinlich ist, und die Endanrufoptimierung manuell auf Quellcodeebene durchzuführen. Zum Beispiel kann unsere add Methode wie folgt umgeschrieben werden:

public static int add(int a, int b) {
    while (a != 0) {
       a = a - 1;
       b = b + 1;
    }
    return b;
}

(Offensichtlich gibt es bessere Möglichkeiten, zwei Ganzzahlen hinzuzufügen. Das Obige dient lediglich zur Veranschaulichung der Auswirkung der manuellen Anrufbeseitigung.)

Warum die Rückrufbeseitigung (noch) nicht in Java implementiert ist

Es gibt eine Reihe von Gründen, warum das Hinzufügen der Rückrufbeseitigung zu Java nicht einfach ist. Zum Beispiel:

• Ein Teil des Codes könnte auf StackOverflowError angewiesen sein, um beispielsweise die Größe eines Rechenproblems zu beschränken.
• Sandbox-Sicherheitsmanager sind häufig darauf angewiesen, den Aufrufstapel zu analysieren, wenn sie entscheiden, ob nicht privilegierter Code eine privilegierte Aktion ausführen soll.

Wie John Rose in "Tail Calls in der VM" erklärt :

"Die Auswirkungen des Entfernens des Stackframes des Aufrufers sind für einige APIs sichtbar, insbesondere für die Überprüfung der Zugriffskontrolle und für die Stapelverfolgung. Es ist, als hätte der Anrufer des Anrufers den Angerufenen direkt angerufen. Alle Rechte, die der Anrufer besitzt, werden verworfen, nachdem die Kontrolle an den Server übergeben wurde callee. Die Verknüpfung und die Zugänglichkeit der callee-Methode werden jedoch vor der Übertragung der Kontrolle berechnet und berücksichtigen den Aufrufer, der den Anruf ausführt. "

Mit anderen Worten, die Beseitigung von Rückrufen könnte dazu führen, dass eine Zugriffskontrollmethode fälschlicherweise der Meinung ist, dass eine sicherheitsrelevante API von vertrauenswürdigem Code aufgerufen wurde.