wake-up-neo.com

Rekursion gegen Schleifen

Ich stehe vor einem Problem, bei dem sowohl die Rekursion als auch die Verwendung einer Schleife wie natürliche Lösungen erscheinen. Gibt es eine Konvention oder "bevorzugte Methode" für solche Fälle? (Offensichtlich ist es nicht ganz so einfach wie unten)

Rekursion

Item Search(string desired, Scope scope) {
    foreach(Item item in scope.items)
        if(item.name == desired)
            return item;

    return scope.Parent ? Search(desired, scope.Parent) : null;
}

Loop

Item Search(string desired, Scope scope) {
    for(Scope cur = scope; cur != null; cur = cur.Parent)
        foreach(Item item in cur.items)
            if(item.name == desired)
                return item;

    return null;
}
46
zildjohn01

Ich bevorzuge rekursive Lösungen, wenn:

  • Die Implementierung der Rekursion ist viel einfacher als die iterative Lösung, da sie normalerweise einen strukturellen Aspekt des Problems auf eine Weise ausnutzt, die der iterative Ansatz nicht kann

  • Ich kann mit ziemlicher Sicherheit davon ausgehen, dass die Tiefe der Rekursion keinen Stapelüberlauf verursacht, vorausgesetzt, es handelt sich um eine Sprache, die die Rekursion auf diese Weise implementiert

Bedingung 1 scheint hier nicht der Fall zu sein. Die iterative Lösung ist ungefähr gleich komplex, ich bleibe also bei der iterativen Route.

55
John Feminella

Wenn es auf die Leistung ankommt, vergleichen Sie beide und wählen Sie rational. Wenn nicht, wählen Sie basierend auf der Komplexität und unter Berücksichtigung eines möglichen Stapelüberlaufs.

Es gibt eine Richtlinie aus dem klassischen Buch Die Elemente des Programmierstils (von Kernighan und Plauger), dass der Algorithmus der Datenstruktur folgen sollte. Das heißt, rekursive Strukturen werden häufig mit rekursiven Algorithmen klarer verarbeitet.

27
RBerteig

Rekursion wird verwendet, um einen Algorithmus auszudrücken, der von Natur aus rekursiv ist und eine leicht verständliche Form aufweist. Ein "natürlich rekursiver" Algorithmus ist ein Algorithmus, bei dem die Antwort aus den Antworten auf kleinere Unterprobleme aufgebaut wird, die wiederum aus den Antworten auf noch kleinere Unterprobleme usw. aufgebaut sind. Beispielsweise wird eine Fakultät berechnet.

In einer Programmiersprache, die nicht funktionsfähig ist, ist ein iterativer Ansatz fast immer schneller und effizienter als ein rekursiver Ansatz. Daher ist der Grund für die Verwendung der Rekursion Klarheit, nicht Geschwindigkeit. Wenn eine rekursive Implementierung weniger klar ist als eine iterative Implementierung, dann vermeiden Sie es auf jeden Fall.

In diesem speziellen Fall würde ich die iterative Implementierung als klarer beurteilen.

18
Tyler McHenry

Wenn Sie eine funktionale Sprache verwenden (scheint nicht so zu sein), fahren Sie mit der Rekursion fort. Wenn nicht, wird die Schleife wahrscheinlich von allen anderen, die an dem Projekt arbeiten, besser verstanden. Natürlich sind einige Aufgaben (wie das rekursive Durchsuchen eines Verzeichnisses) besser für die Rekursion geeignet als andere.

Wenn der Code nicht für die End-Rekursion optimiert werden kann, ist die Schleife außerdem sicherer.

9
Ed S.

Benutze die Schleife. Es ist einfacher zu lesen und zu verstehen (das Lesen von Code ist immer viel schwieriger als das Schreiben) und im Allgemeinen viel schneller.

7
Emil H

Es ist nachweisbar, dass alle rekursiven Algorithmen in eine Schleife entrollt werden können und umgekehrt. Im Allgemeinen ist eine rekursive Implementierung eines rekursiven Algorithmus für den Programmierer klarer als die Schleifenimplementierung und auch einfacher zu debuggen. Im Allgemeinen ist die reale Leistung der Schleifenimplementierung auch schneller, da eine Verzweigung/ein Sprung in einer Schleife in der Regel schneller ausgeführt werden kann als das Verschieben und Platzieren eines Stapelrahmens.

Ich persönlich bevorzuge für rekursive Algorithmen die rekursive Implementierung in allen Situationen mit Ausnahme der leistungsintensivsten.

4
Not Sure

Ich bevorzuge Schleifen als

  • Rekursion ist fehleranfällig
  • Der gesamte Code verbleibt in einer Funktion/Methode
  • Speicher- und Geschwindigkeitsersparnis

Ich benutze Stacks (LIFO-Schema), damit die Schleifen funktionieren

In Java werden Stacks mit der Deque-Schnittstelle abgedeckt

// Get all the writable folders under one folder
// Java-like pseudocode
void searchWritableDirs(Folder rootFolder){
    List<Folder> response = new List<Folder>(); // Results
    Deque<Folder> folderDeque = new Deque<Folder>(); // Stack with elements to inspect
    folderDeque.add(rootFolder);
    while( ! folderDeque.isEmpty()){
        Folder actual = folder.pop(); // Get last element
        if (actual.isWritable()) response.add(actual); // Add to response
        for(Folder actualSubfolder: actual.getSubFolder()) { 
            // Here we iterate subfolders, with this recursion is not needed
            folderDeque.Push(actualSubfolder);
        } 
    } 
    log("Folders " + response.size());
 }

Weniger kompliziert, kompakter als

// Get all the writable folders under one folder
// Java-like pseudocode
void searchWritableDirs(Folder rootFolder){
    List<Folder> response = new List<Folder>(); // Results
    rec_searchWritableDirs(actualSubFolder,response);
    log("Folders " + response.size());
}

private void rec_searchWritableDirs(Folder actual,List<Folder> response) {
   if (actual.isWritable()) response.add(actual); // Add to response
   for(Folder actualSubfolder: actual.getSubFolder()) {
       // Here we iterate subfolders, recursion is needed
       rec_searchWritableDirs(actualSubFolder,response);
   }                
}

Letzteres hat weniger Code, aber zwei Funktionen und es ist schwieriger, Code zu verstehen, IMHO.

4
user898384

Ich würde sagen, die Rekursionsversion ist verständlicher, aber nur mit Kommentaren:

Item Search(string desired, Scope scope) {
    // search local items
    foreach(Item item in scope.items)
        if(item.name == desired)
            return item;

    // also search parent
    return scope.Parent ? Search(desired, scope.Parent) : null;
}

Es ist viel einfacher, diese Version zu erklären. Versuchen Sie, einen schönen Kommentar zur Loop-Version zu schreiben, und Sie werden sehen.

3
ypnos

Ich finde die Rekursion natürlicher, aber Sie können gezwungen sein, die Schleife zu verwenden, wenn Ihr Compiler keine Tail-Call-Optimierung durchführt und Ihre Struktur/Liste für die Stack-Größe zu tief ist.

2
Svante

Normalerweise bevorzuge ich die Verwendung von Schleifen. Die meisten guten OOP -Designs ermöglichen es Ihnen, Schleifen zu verwenden, ohne dass Sie eine Rekursion verwenden müssen (und verhindern so, dass das Programm all diese unangenehmen Parameter und Adressen auf den Stack überträgt).

Es wird eher im prozeduralen Code verwendet, wo es logischer erscheint, rekursiv zu denken (aufgrund der Tatsache, dass Sie es nicht einfach speichern können Zustand oder Metadaten (Informationen?) und somit schaffen Sie mehr Situationen, die es wert wären, verwendet zu werden.

Rekursion ist gut, um eine Funktion zu prototypisieren und/oder eine Basis zu schreiben. Wenn Sie jedoch wissen, dass der Code funktioniert und Sie während der Optimierungsphase darauf zurückgreifen, versuchen Sie, ihn durch eine Schleife zu ersetzen.

Auch dies ist alles meinungsbildend. Entscheiden Sie sich für das, was für Sie am besten funktioniert.

1
user865927

Nun, ich habe Unmengen von Antworten gesehen und sogar Antworten akzeptiert, aber nie die richtigen gesehen und mir überlegt, warum ...

Um es kurz zu machen :

Vermeiden Sie immer Rekursionen, wenn Sie dieselbe Einheit durch Schleifen erzeugen lassen können !

Wie funktioniert die Rekursion?

• Der Frame im Stapelspeicher wird einem einzelnen Funktionsaufruf zugewiesen

• Der Frame enthält Verweise auf die aktuelle Methode

• Wenn die Methode Objekte enthält, werden die Objekte in den Heap-Speicher verschoben, und Frame enthält Verweise auf diese Objekte im Heap-Speicher.

• Diese Schritte werden für jeden einzelnen Methodenaufruf ausgeführt!

Risiken:

• StackOverFlow, wenn der Stack keinen Speicher für neue rekursive Methoden hat.

• OutOfMemory, wenn der Heap keinen Speicher für rekursiv gespeicherte Objekte hat.

Wie funktioniert die Schleife?

• Alle vorhergehenden Schritte, außer dass die Ausführung von wiederholtem Code innerhalb der Schleife keine weiteren Daten verbraucht, wenn sie bereits verbraucht sind.

Risiken:

• Ein einzelnes Risiko liegt in der while-Schleife, wenn Ihr Zustand einfach nie existiert ... Nun, das führt nicht zu Abstürzen oder etwas anderem. Wenn Sie naiv while(true) :) ausführen, wird die Schleife einfach nicht beendet.

Test:

Führen Sie als Nächstes in Ihrer Software Folgendes aus:

private Integer someFunction(){

return someFunction();
}

Sie werden in einer Sekunde eine StackOverFlow Ausnahme bekommen und vielleicht auch OutOfMemory

Zweitens tun:

while(true){

}

Die Software friert nur ein und es kommt zu keinem Absturz:

Last but not least - for Schleifen:

Gehen Sie immer mit for Schleifen, weil diese oder jene Schleife Sie etwas zwingt, die Sollbruchstelle anzugeben, über die die Schleife nicht hinausgeht. Sicherlich können Sie sehr wütend sein und nur einen Weg finden, for loop nie aufhören, aber ich rate Ihnen, immer Schleifen anstelle von Rekursionen zu verwenden, um den Speicher zu verwalten und die Produktivität Ihrer Software zu verbessern, was heutzutage ein großes Problem darstellt.

Referenzen:

stapelbasierte Speicherzuordnung

1

Sie können die Schleife auch in einem besser lesbaren Format schreiben. Cs for(init;while;increment) weist einige Lesbarkeitsnachteile auf, da der increment -Befehl zu Beginn erwähnt, aber am Ende der Schleife ausgeführt wird.

Auch IHRE ZWEI PROBEN SIND NICHT GLEICHWERTIG . Das rekursive Beispiel schlägt fehl und die Schleife nicht, wenn Sie es wie folgt aufrufen: Search(null,null). Das macht die Loop-Version für mich besser.

Hier sind die Beispiele modifiziert (und unter der Annahme, dass null falsch ist)

Rekursion (fix und Tail-Call optimierbar)

Item Search(string desired, Scope scope) {

    if (!scope) return null

    foreach(Item item in scope.items)
        if(item.name == desired)
            return item;

    //search parent (recursive)
    return Search(desired, scope.Parent);
}

Loop

Item Search(string desired, Scope scope) {
    // start
    Scope cur = scope;

    while(cur) {
        foreach(Item item in cur.items)
            if(item.name == desired)
                return item;

        //search parent
        cur = cur.Parent;

    } //loop

    return null;
}
0
Lucio M. Tato

Wenn Ihr Code kompiliert ist, wird es wahrscheinlich kaum einen Unterschied machen. Testen Sie, wie viel Speicher verwendet wird und wie schnell er ausgeführt wird.

0
Jay

Wenn das System, an dem Sie arbeiten, über einen kleinen Stapel verfügt (eingebettete Systeme), ist die Rekursionstiefe begrenzt. Daher ist die Auswahl des schleifenbasierten Algorithmus wünschenswert.

0
switchmode