Kann eine rekursive Funktion Iterationen / Schleifen enthalten?

Ich habe mich mit rekursiven Funktionen befasst und anscheinend mit Funktionen, die sich selbst aufrufen und keine Iterationen / Schleifen verwenden (sonst wäre es keine rekursive Funktion).

Beim Surfen im Internet für Beispiele (das 8-Königinnen-rekursive Problem) fand ich jedoch diese Funktion:

private boolean placeQueen(int rows, int queens, int n) {
    boolean result = false;
    if (row < n) {
        while ((queens[row] < n - 1) && !result) {
            queens[row]++;
            if (verify(row,queens,n)) {
                ok = placeQueen(row + 1,queens,n);
            }
        }
        if (!result) {
            queens[row] = -1;
        }
    }else{
        result = true;
    }
    return result;
}

Es ist eine whileSchleife beteiligt.

... also bin ich jetzt ein bisschen verloren. Kann ich Schleifen verwenden oder nicht?

Sie haben die Rekursion falsch verstanden: Sie kann zwar als Ersatz für die Iteration verwendet werden, es ist jedoch absolut nicht erforderlich, dass die rekursive Funktion keine internen Iterationen enthält.

Die einzige Voraussetzung, um eine Funktion als rekursiv zu betrachten, ist die Existenz eines Codepfades, über den sie sich direkt oder indirekt selbst aufruft. Alle korrekten rekursiven Funktionen haben auch eine Art Bedingung, die verhindert, dass sie für immer "rekursiv" werden.

Ihre rekursive Funktion ist ideal, um die Struktur der rekursiven Suche mit Backtracking zu veranschaulichen. Es beginnt mit der Überprüfung der Austrittsbedingung row < nund fährt fort, Suchentscheidungen auf der Ebene der Rekursion zu treffen (dh eine mögliche Position für die Königinnummer auszuwählen row). Nach jeder Iteration wird ein rekursiver Aufruf ausgeführt, um auf der Konfiguration aufzubauen, die die Funktion bisher gefunden hat. schließlich, es „aufsitzt“ , wenn rowLauf nin dem rekursiven Aufruf , das ist nEbene tief.

Die allgemeine Struktur einer rekursiven Funktion sieht ungefähr so ​​aus:

myRecursiveFunction(inputValue)
begin
   if evaluateBaseCaseCondition(inputValue)=true then
       return baseCaseValue;
   else
       /*
       Recursive processing
       */
       recursiveResult = myRecursiveFunction(nextRecursiveValue); //nextRecursiveValue could be as simple as inputValue-1
       return recursiveResult;
   end if
end

Der Text, den ich als markiert habe, /*recursive processing*/könnte alles sein. Es könnte eine Schleife enthalten, falls das zu lösende Problem dies erfordert, und es könnte auch rekursive Aufrufe von enthalten myRecursiveFunction.

Sie können Schleifen sicherlich in einer rekursiven Funktion verwenden. Was eine Funktion rekursiv macht, ist nur die Tatsache, dass die Funktion sich an einem bestimmten Punkt in ihrem Ausführungspfad selbst aufruft. Sie sollten jedoch eine Bedingung haben, um unendliche Rekursionsaufrufe zu verhindern, von denen Ihre Funktion nicht zurückkehren kann.

Rekursive Aufrufe und Schleifen sind nur zwei Möglichkeiten / Konstrukte zur Implementierung einer iterativen Berechnung.

Eine whileSchleife entspricht einem endrekursiven Aufruf (siehe z. B. hier ), dh einer Iteration, bei der Sie keine Zwischenergebnisse zwischen zwei Iterationen speichern müssen (alle Ergebnisse eines Zyklus sind bereit, wenn Sie in den nächsten Zyklus eintreten). Wenn Sie Zwischenergebnisse speichern müssen, die Sie später erneut verwenden können, können Sie entweder eine whileSchleife zusammen mit einem Stapel (siehe hier ) oder einen nicht rekursiven (dh willkürlichen) rekursiven Aufruf verwenden.

In vielen Sprachen können Sie beide Mechanismen verwenden, und Sie können den für Sie am besten geeigneten auswählen und diese sogar in Ihrem Code mischen. In imperativen Sprachen wie C, C ++, Java usw. verwenden Sie normalerweise eine whileoder for-Schleife, wenn Sie keinen Stapel benötigen, und Sie verwenden rekursive Aufrufe, wenn Sie einen Stapel benötigen (Sie verwenden implizit den Laufzeitstapel). Haskell (eine funktionale Sprache) bietet keine Iterationskontrollstruktur, sodass Sie nur rekursive Aufrufe verwenden können, um die Iteration durchzuführen.

In deinem Beispiel (siehe meine Kommentare):

// queens should have type int [] , not int.
private boolean placeQueen(int row, int [] queens, int n)
{
    boolean result = false;
    if (row < n)
    {
        // Iterate with queens[row] = 1 to n - 1.
        // After each iteration, you either have a result
        // in queens, or you have to try the next column for
        // the current row: no intermediate result.
        while ((queens[row] < n - 1) && !result)
        {
            queens[row]++;
            if (verify(row,queens,n))
            {
                // I think you have 'result' here, not 'ok'.
                // This is another loop (iterate on row).
                // The loop is implemented as a recursive call
                // and the previous values of row are stored on
                // the stack so that we can resume with the previous
                // value if the current attempt finds no solution.
                result = placeQueen(row + 1,queens,n);
            }
        }
        if (!result) {
            queens[row] = -1;
        }
    }else{
        result = true;
    }
    return result;
}

Sie glauben zu Recht, dass es einen Zusammenhang zwischen Rekursion und Iteration oder Schleifenbildung gibt. Rekursive Algorithmen werden häufig manuell oder sogar automatisch mithilfe der Tail-Call-Optimierung in iterative Lösungen konvertiert.

In acht Königinnen bezieht sich der rekursive Teil auf das Speichern von Daten, die für die Rückverfolgung benötigt werden. Wenn Sie an eine Rekursion denken, ist es hilfreich, darüber nachzudenken, was auf dem Stapel abgelegt wird. Der Stack kann Pass-by-Value-Parameter und lokale Variablen enthalten, die eine Schlüsselrolle im Algorithmus spielen, oder auch Dinge, die nicht so augenscheinlich relevant sind wie die Absenderadresse oder in diesem Fall einen übergebenen Wert mit der Anzahl der verwendeten Königinnen wird vom Algorithmus nicht verändert.

Die Aktion, die in acht Königinnen stattfindet, besteht darin, dass wir im Wesentlichen eine Teillösung für eine bestimmte Anzahl von Königinnen in den ersten Spalten erhalten, aus der wir iterativ die bisher gültigen Auswahlen in der aktuellen Spalte bestimmen, die wir rekursiv übergeben, um sie für die auszuwerten verbleibende Spalten. Vor Ort verfolgen acht Königinnen, welche Zeile versucht wird, und wenn die Rückverfolgung stattfindet, ist sie bereit, die verbleibenden Zeilen zu durchlaufen oder die Rückverfolgung durch einfaches Zurückkehren fortzusetzen, wenn keine andere Zeile gefunden wird, die funktionieren könnte.

Der Teil "Eine kleinere Version des Problems erstellen" kann Schleifen aufweisen. Solange sich die Methode selbst aufruft und als Parameter die kleinere Version des Problems übergibt, ist die Methode rekursiv. Natürlich muss eine Beendigungsbedingung angegeben werden, wenn die kleinstmögliche Version des Problems gelöst ist und die Methode einen Wert zurückgibt, um eine Stapelüberlaufbedingung zu vermeiden.

Die Methode in Ihrer Frage ist rekursiv.

Rekursion ruft Ihre Funktion im Grunde genommen erneut auf und der Hauptvorteil der Rekursion besteht darin, Speicherplatz zu sparen. Rekursion kann Schleifen enthalten, mit denen eine andere Operation ausgeführt wird.