Funktionsweise der Rekursion innerhalb einer For-Schleife

Ich bin neu in der Rekursion und versuche, diesen Codeausschnitt zu verstehen. Ich lerne für eine Prüfung, und dies ist ein “Rezensent”, den ich in der CIS Education Library von Standford gefunden habe (aus Binary Trees von Nick Parlante).

Ich verstehe das Konzept, aber wenn wir INSIDE THE LOOP wiederholen, geht alles schief! Bitte hilf mir. Vielen Dank.

countTrees()-Lösung (C/C++)

/*
 For the key values 1...numKeys, how many structurally unique
 binary search trees are possible that store those keys.
 Strategy: consider that each value could be the root.
 Recursively find the size of the left and right subtrees.
*/

int countTrees(int numKeys) {
    if (numKeys <=1) {
        return(1);
    }

    // there will be one value at the root, with whatever remains
    // on the left and right each forming their own subtrees.
    // Iterate through all the values that could be the root...

    int sum = 0;
    int left, right, root;

    for (root=1; root<=numKeys; root++) {
        left = countTrees(root - 1);
        right = countTrees(numKeys - root);
        // number of possible trees with this root == left*right
        sum += left*right;
    }

    return(sum);  
}  

Stellen Sie sich vor, die Schleife wird “auf Pause” gesetzt, während Sie zum Funktionsaufruf gehen.

Nur weil die Funktion ein rekursiver Aufruf ist, funktioniert sie genauso wie jede andere Funktion, die Sie innerhalb einer Schleife aufrufen.

Der neue rekursive Aufruf startet seinen for Schleife und wieder, pausiert, während die Funktionen erneut aufgerufen werden, und so weiter.

• Für die Rekursion ist es hilfreich, sich die Call-Stack-Struktur vorzustellen.
• Wenn eine Rekursion in einer Schleife sitzt, ähnelt die Struktur (fast) einem n-stelligen Baum.
• Die Schleife steuert horizontal, wie viele Zweige erzeugt werden, während die Rekursion die Höhe des Baums bestimmt.
• Der Baum wird entlang eines bestimmten Zweigs generiert, bis er das Blatt erreicht (Grundzustand), dann horizontal erweitert, um andere Blätter zu erhalten und die vorherige Höhe wiederherzustellen und zu wiederholen.

Ich finde diese Perspektive generell eine gute Denkweise.

Betrachten Sie es so: Es gibt 3 mögliche Fälle für den ersten Anruf:

numKeys = 0
numKeys = 1
numKeys > 1

Die Fälle 0 und 1 sind einfach – die Funktion gibt einfach 1 zurück und Sie sind fertig. Für Numkeys 2 erhalten Sie am Ende:

sum = 0
loop(root = 1 -> 2)
   root = 1:
      left = countTrees(1 - 1) -> countTrees(0) -> 1
      right = countTrees(2 - 1) -> countTrees(1) -> 1
      sum = sum + 1*1 = 0 + 1 = 1
   root = 2:
      left = countTrees(2 - 1) -> countTrees(1) -> 1
      right = countTrees(2 - 2) -> countTrees(0) -> 1
      sum = sum + 1*1 = 1 + 1 = 2

output: 2

für numKeys = 3:

sum = 0
loop(root = 1 -> 3):
   root = 1:
       left = countTrees(1 - 1) -> countTrees(0) -> 1
       right = countTrees(3 - 1) -> countTrees(2) -> 2
       sum = sum + 1*2 = 0 + 2 = 2
   root = 2:
       left = countTrees(2 - 1) -> countTrees(1) -> 1
       right = countTrees(3 - 2) -> countTrees(1) -> 1
       sum = sum + 1*1 = 2 + 1 = 3
   root = 3:
       left = countTrees(3 - 1) -> countTrees(2) -> 2
       right = countTrees(3 - 3) -> countTrees(0) -> 1
       sum = sum + 2*1 = 3 + 2 = 5

 output 5

usw. Diese Funktion ist höchstwahrscheinlich O (n ^ 2), da Sie für alle n Tasten 2 * n-1 rekursive Aufrufe ausführen, was bedeutet, dass die Laufzeit sehr schnell wächst.

Nur um daran zu denken, dass alle lokalen Variablen, wie z numKeys, sum, left, right, root befinden sich im Stapelspeicher. Wenn Sie zu gehen n-th Tiefe der rekursiven Funktion wird es geben n Kopien dieser lokalen Variablen. Wenn die Ausführung einer Tiefe abgeschlossen ist, wird eine Kopie dieser Variablen aus dem Stapel angezeigt.

Auf diese Weise werden Sie verstehen, dass sich die Tiefe der nächsten Ebene NICHT auf die lokalen Variablen der Tiefe der aktuellen Ebene auswirkt (es sei denn, Sie verwenden Referenzen, aber wir befinden uns NICHT in diesem speziellen Problem).

Bei diesem speziellen Problem sollte der Zeitkomplexität sorgfältig Aufmerksamkeit geschenkt werden. Hier sind meine Lösungen:

/* Q: For the key values 1...n, how many structurally unique binary search
      trees (BST) are possible that store those keys.
      Strategy: consider that each value could be the root.  Recursively
      find the size of the left and right subtrees.
      http://stackoverflow.com/questions/4795527/
             how-recursion-works-inside-a-for-loop */
/* A: It seems that it's the Catalan numbers:
      http://en.wikipedia.org/wiki/Catalan_number */
#include <iostream>
#include <vector>
using namespace std;

// Time Complexity: ~O(2^n)
int CountBST(int n)
{
    if (n <= 1)
        return 1;

    int c = 0;
    for (int i = 0; i < n; ++i)
    {
        int lc = CountBST(i);
        int rc = CountBST(n-1-i);
        c += lc*rc;
    }

    return c;
}

// Time Complexity: O(n^2)
int CountBST_DP(int n)
{
    vector<int> v(n+1, 0);
    v[0] = 1;

    for (int k = 1; k <= n; ++k)
    {
        for (int i = 0; i < k; ++i)
            v[k] += v[i]*v[k-1-i];
    }

    return v[n];
}

/* Catalan numbers:
            C(n, 2n)
     f(n) = --------
             (n+1)
              2*(2n+1)
     f(n+1) = -------- * f(n)
               (n+2)

   Time Complexity: O(n)
   Space Complexity: O(n) - but can be easily reduced to O(1). */
int CountBST_Math(int n)
{
    vector<int> v(n+1, 0);
    v[0] = 1;

    for (int k = 0; k < n; ++k)
        v[k+1] = v[k]*2*(2*k+1)/(k+2);

    return v[n];
}

int main()
{
    for (int n = 1; n <= 10; ++n)
        cout << CountBST(n) << '\t' << CountBST_DP(n) <<
                               '\t' << CountBST_Math(n) << endl;

    return 0;
}
/* Output:
1       1       1
2       2       2
5       5       5
14      14      14
42      42      42
132     132     132
429     429     429
1430    1430    1430
4862    4862    4862
16796   16796   16796
 */

Sie können es sich vom Basisfall aus vorstellen und nach oben arbeiten.

Für den Basisfall haben Sie also 1 (oder weniger) Knoten. Es gibt nur 1 strukturell eindeutigen Baum, der mit 1 Knoten möglich ist – das ist der Knoten selbst. Wenn also numKeys kleiner oder gleich 1 ist, geben Sie einfach 1 zurück.

Angenommen, Sie haben mehr als einen Schlüssel. Nun, dann ist einer dieser Schlüssel die Wurzel, einige Elemente befinden sich im linken Zweig und einige Elemente im rechten Zweig.

Wie groß sind diese linken und rechten Äste? Nun, es hängt davon ab, was das Wurzelelement ist. Da Sie die Gesamtmenge möglicher Bäume berücksichtigen müssen, müssen wir alle Konfigurationen (alle möglichen Wurzelwerte) berücksichtigen – also iterieren wir über alle möglichen Werte.

Für jede Iteration i wissen wir, dass i an der Wurzel ist, i – 1 Knoten sind auf dem linken Zweig und numKeys – i Knoten sind auf dem rechten Zweig. Aber natürlich haben wir bereits eine Funktion, die die Gesamtzahl der Baumkonfigurationen bei gegebener Anzahl der Knoten zählt! Es ist die Funktion, die wir schreiben. Rufen Sie also die Funktion rekursiv auf, um die Anzahl der möglichen Baumkonfigurationen der linken und rechten Teilbäume zu erhalten. Die Gesamtzahl der Bäume, die mit i an der Wurzel möglich sind, ist dann das Produkt dieser beiden Zahlen (für jede Konfiguration des linken Teilbaums können alle möglichen rechten Teilbäume vorkommen).

Nachdem Sie alles zusammengefasst haben, sind Sie fertig.

Wenn Sie es also so darstellen, ist es nichts Besonderes, die Funktion rekursiv aus einer Schleife heraus aufzurufen – es ist nur ein Werkzeug, das wir für unseren Algorithmus benötigen. Ich würde auch empfehlen (wie es Grammin getan hat), dies durch einen Debugger laufen zu lassen und zu sehen, was bei jedem Schritt vor sich geht.

Jeder Aufruf hat seinen eigenen Variablenbereich, wie man erwarten würde. Die Komplexität ergibt sich aus der Tatsache, dass die Ausführung der Funktion “unterbrochen” wird, um dieselbe Funktion erneut auszuführen. Dieser Code:

for (root=1; root<=numKeys; root++) {
        left = countTrees(root - 1);
        right = countTrees(numKeys - root);
        // number of possible trees with this root == left*right
        sum += left*right;
    }

Könnte auf diese Weise in Plain C umgeschrieben werden:

 root = 1;
 Loop:
     if ( !( root <= numkeys ) ) {
         goto EndLoop;
     }

     left = countTrees( root -1 );
     right = countTrees ( numkeys - root );
     sum += left * right

     ++root;
     goto Loop;
 EndLoop:
 // more things...

Es wird tatsächlich vom Compiler in so etwas übersetzt, aber in Assembler. Wie Sie sehen können, wird die Schleife durch ein Paar Variablen gesteuert, Zahlen und Wurzelund ihre Werte werden nicht aufgrund der Ausführung eines anderen geändert Beispiel des gleichen Verfahrens. Wenn der Aufgerufene zurückkehrt, setzt der Aufrufer die Ausführung fort, mit den gleichen Werten für alle Werte, die er vor dem rekursiven Aufruf hatte.

IMO, das Schlüsselelement hier ist das Verständnis von Funktionsaufrufrahmen, Aufruflisten und wie sie zusammenarbeiten.

In Ihrem Beispiel haben Sie eine Reihe lokaler Variablen, die beim ersten Aufruf initialisiert, aber nicht abgeschlossen werden. Es ist wichtig, diese lokalen Variablen zu beobachten, um die ganze Idee zu verstehen. Bei jedem Aufruf werden die lokalen Variablen aktualisiert und schließlich rückwärts zurückgegeben (höchstwahrscheinlich werden sie in einem Register gespeichert, bevor jeder Funktionsaufrufrahmen vom Stapel entfernt wird), bis sie zur Summenvariablen des ursprünglichen Funktionsaufrufs hinzugefügt werden.

Die wichtige Unterscheidung hier ist – wohin man zurückkehrt. Wenn Sie wie in Ihrem Beispiel einen kumulierten Summenwert benötigen, können Sie nicht zurückkehren Innerhalb die Funktion, die zu einer vorzeitigen Rückkehr/Beendigung führen würde. Wenn Sie jedoch darauf angewiesen sind, dass sich ein Wert in einem bestimmten Zustand befindet, können Sie überprüfen, ob dieser Zustand innerhalb der for-Schleife erreicht wird, und sofort zurückkehren, ohne ganz nach oben zu gehen.