Kann eine rekursive Funktion Iterationen / Schleifen enthalten?

12

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?

Omega
quelle
5
Kompiliert es. Ja. Warum also fragen?
Thomas Eding
6
Die gesamte Definition der Rekursion lautet, dass die Funktion zu einem bestimmten Zeitpunkt im Rahmen ihrer eigenen Ausführung erneut aufgerufen werden kann, bevor sie zurückkehrt (unabhängig davon, ob sie von sich selbst oder von einer anderen aufgerufenen Funktion erneut aufgerufen wird). Nichts an dieser Definition schließt die Möglichkeit der Schleifenbildung aus.
CHAO
Als Ergänzung zu cHaos Kommentar wird eine rekursive Funktion eine einfachere Version von sich selbst erneut aufrufen (andernfalls würde sie eine Endlosschleife bilden). Um Orbling zu zitieren (aus dem Klartext: Was ist Rekursion? ): "Rekursive Programmierung ist der Prozess, ein Problem schrittweise zu reduzieren, um Versionen von sich selbst leichter zu lösen." In diesem Fall ist die härteste Version von placeQueen"place 8 queens" und die einfachere Version von placeQueen"place 7 queens" (dann place 6, etc.)
Brian
Sie können alles verwenden, was Omega funktioniert. Sehr selten geben Software-Spezifikationen an, welchen Programmierstil Sie verwenden sollen - es sei denn, Sie sind in der Schule und Ihre Aufgabe sagt dies aus.
Apoorv Khurasia
@ThomasEding: Ja, natürlich kompiliert und funktioniert es. Im Moment studiere ich jedoch nur Ingenieurwissenschaften. An dieser Stelle geht es mir um das strikte Konzept / die strenge Definition und nicht darum, wie Programmierer es heutzutage anwenden. Also frage ich mich, ob das Konzept, das ich habe, richtig ist (was anscheinend nicht stimmt).
Omega

Antworten:

41

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.

dasblinkenlight
quelle
1
+1 für "richtige" rekursive Funktionen haben eine bedingte, viele falsche da draußen, die nicht heh
Jimmy Hoffa
6
+1 "wiederkehrende" für immer `Turtle () {Turtle ();}
Mr.Mindor
1
@ Mr.Mindor Ich liebe das Zitat "Es ist Schildkröten ganz unten" :)
dasblinkenlight
Das hat mich zum Lächeln gebracht :-)
Martijn Verburg
2
"Alle korrekten rekursiven Funktionen haben auch eine Art Bedingung, die verhindert, dass sie für immer" rekursiv "werden." trifft bei nicht strenger Bewertung nicht zu.
Pubby
12

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.

FrustratedWithFormsDesigner
quelle
1
Das ist irreführend, weil es nur einen rekursiven Aufruf gibt und Fälle, in denen der rekursive Aufruf sich selbst in einer Schleife befindet (z. B. B-Tree-Traversal), so gut wie ausgeschlossen sind.
Peter Taylor
@ PeterTaylor: Ja, ich habe versucht, es einfach zu halten.
FrustratedWithFormsDesigner
Oder sogar mehrere Aufrufe ohne Schleife, z. B. das Durchlaufen eines einfachen Binärbaums, bei dem Sie zwei Aufrufe haben, weil jeder Knoten zwei untergeordnete Knoten hat.
Izkata
6

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.

Marco-Fiset
quelle
1

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;
}
Giorgio
quelle
1

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.

DeveloperDon
quelle
0

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.

Tulains Córdova
quelle
0

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.

Akshay
quelle
Bitten Sie, sich zu unterscheiden. Viele Algorithmen können rekursiv oder iterativ sein, und die rekursive Lösung ist häufig sehr viel speicherintensiver, wenn Sie Rücksprungadressen, Parameter und lokale Variablen zählen, die auf dem Stapel abgelegt werden müssen. Einige Sprachen erkennen und optimieren die Schwanzrekursion oder die Schwanzanrufoptimierung, dies ist jedoch manchmal sprach- oder codespezifisch.
DeveloperDon