Gibt es einen Leistungseinbruch, wenn wir in Algorithmen, in denen beide denselben Zweck erfüllen können, eine Schleife anstelle einer Rekursion verwenden oder umgekehrt? Beispiel: Überprüfen Sie, ob die angegebene Zeichenfolge ein Palindrom ist. Ich habe viele Programmierer gesehen, die Rekursion als Mittel verwendeten, um zu zeigen, wann ein einfacher Iterationsalgorithmus in die Rechnung passen kann. Spielt der Compiler eine wichtige Rolle bei der Entscheidung, was verwendet werden soll?

Es ist möglich, dass die Rekursion teurer ist, abhängig davon, ob die rekursive Funktion schwanzrekursiv ist (die letzte Zeile ist ein rekursiver Aufruf). Die Schwanzrekursion sollte vom Compiler erkannt und auf sein iteratives Gegenstück optimiert werden (unter Beibehaltung der präzisen und klaren Implementierung, die Sie in Ihrem Code haben).

Ich würde den Algorithmus so schreiben, wie es am sinnvollsten und am klarsten für den armen Trottel ist (sei es Sie selbst oder jemand anderes), der den Code in ein paar Monaten oder Jahren warten muss. Wenn Sie auf Leistungsprobleme stoßen, profilieren Sie Ihren Code und prüfen Sie dann und erst dann die Optimierung, indem Sie zu einer iterativen Implementierung übergehen. Vielleicht möchten Sie sich mit Memoisierung und dynamischer Programmierung befassen .

Schleifen können einen Leistungsgewinn für Ihr Programm erzielen. Durch die Rekursion kann Ihr Programmierer einen Leistungsgewinn erzielen. Wählen Sie, was in Ihrer Situation wichtiger ist!

Das Vergleichen der Rekursion mit der Iteration ist wie das Vergleichen eines Kreuzschlitzschraubendrehers mit einem Flachkopfschraubendreher. Zum größten Teil könnten Sie jede Kreuzschlitzschraube mit einem flachen Kopf entfernen, aber es wäre einfacher, wenn Sie den für diese Schraube entwickelten Schraubendreher verwenden würden, oder?

Einige Algorithmen eignen sich aufgrund ihrer Gestaltung nur zur Rekursion (Fibonacci-Sequenzen, Durchlaufen einer baumartigen Struktur usw.). Durch die Rekursion wird der Algorithmus prägnanter und verständlicher (daher gemeinsam nutzbar und wiederverwendbar).

Einige rekursive Algorithmen verwenden außerdem "Lazy Evaluation", wodurch sie effizienter sind als ihre iterativen Brüder. Dies bedeutet, dass sie die teuren Berechnungen nur zum gewünschten Zeitpunkt durchführen und nicht jedes Mal, wenn die Schleife ausgeführt wird.

Das sollte ausreichen, um Ihnen den Einstieg zu erleichtern. Ich werde auch einige Artikel und Beispiele für Sie ausgraben.

Link 1: Haskel vs PHP (Rekursion vs Iteration)

Hier ist ein Beispiel, in dem der Programmierer einen großen Datensatz mit PHP verarbeiten musste. Er zeigt, wie einfach es gewesen wäre, in Haskel mit Rekursion umzugehen, aber da PHP keine einfache Möglichkeit hatte, dieselbe Methode zu erreichen, war er gezwungen, Iteration zu verwenden, um das Ergebnis zu erhalten.

http://blog.webspecies.co.uk/2011-05-31/lazy-evaluation-with-php.html

Link 2: Rekursion meistern

Der größte Teil des schlechten Rufs von Rekursion beruht auf den hohen Kosten und der Ineffizienz in imperativen Sprachen. Der Autor dieses Artikels spricht darüber, wie rekursive Algorithmen optimiert werden können, um sie schneller und effizienter zu machen. Er geht auch auf die Umwandlung einer herkömmlichen Schleife in eine rekursive Funktion und die Vorteile der Verwendung der Tail-End-Rekursion ein. Seine abschließenden Worte fassten einige meiner wichtigsten Punkte zusammen, die ich denke:

"Rekursive Programmierung bietet dem Programmierer eine bessere Möglichkeit, Code auf eine Weise zu organisieren, die sowohl wartbar als auch logisch konsistent ist."

https://developer.ibm.com/articles/l-recurs/

Link 3: Ist die Rekursion jemals schneller als eine Schleife? (Antworten)

Hier ist ein Link zu einer Antwort auf eine Stapelüberlauffrage, die Ihrer ähnlich ist. Der Autor weist darauf hin, dass viele der Benchmarks, die entweder mit Rekursion oder Looping verbunden sind, sehr sprachspezifisch sind. Imperative Sprachen sind in der Regel schneller mit einer Schleife und langsamer mit Rekursion und umgekehrt für funktionale Sprachen. Ich denke, der Hauptpunkt dieses Links ist, dass es sehr schwierig ist, die Frage in einem sprachunabhängigen / situationsblinden Sinne zu beantworten.

Ist die Rekursion jemals schneller als eine Schleife?

Rekursion ist im Speicher teurer, da für jeden rekursiven Aufruf im Allgemeinen eine Speicheradresse auf den Stapel verschoben werden muss, damit das Programm später zu diesem Punkt zurückkehren kann.

Dennoch gibt es viele Fälle, in denen die Rekursion viel natürlicher und lesbarer ist als Schleifen - wie bei der Arbeit mit Bäumen. In diesen Fällen würde ich empfehlen, an der Rekursion festzuhalten.

Typischerweise würde man erwarten, dass die Leistungsstrafe in die andere Richtung liegt. Rekursive Aufrufe können zum Aufbau zusätzlicher Stapelrahmen führen. Die Strafe dafür variiert. In einigen Sprachen wie Python (genauer gesagt in einigen Implementierungen einiger Sprachen ...) können Sie bei Aufgaben, die Sie möglicherweise rekursiv angeben, wie z. B. dem Ermitteln des Maximalwerts in einer Baumdatenstruktur, ziemlich leicht auf Stapelbeschränkungen stoßen. In diesen Fällen möchten Sie wirklich bei Schleifen bleiben.

Das Schreiben guter rekursiver Funktionen kann die Leistungseinbußen etwas verringern, vorausgesetzt, Sie haben einen Compiler, der die Tail-Rekursionen usw. optimiert. (Überprüfen Sie außerdem, ob die Funktion wirklich Tail-rekursiv ist - dies ist eines der Dinge, bei denen viele Leute Fehler machen auf.)

Abgesehen von "Rand" -Fällen (Hochleistungsrechnen, sehr große Rekursionstiefe usw.) ist es vorzuziehen, den Ansatz zu wählen, der Ihre Absicht am deutlichsten zum Ausdruck bringt, gut gestaltet und wartbar ist. Optimieren Sie erst, nachdem Sie einen Bedarf identifiziert haben.

Rekursion ist besser als Iteration für Probleme, die in mehrere kleinere Teile zerlegt werden können .

Um beispielsweise einen rekursiven Fibonnaci-Algorithmus zu erstellen, zerlegen Sie fib (n) in fib (n-1) und fib (n-2) und berechnen beide Teile. Mit Iteration können Sie nur eine einzelne Funktion immer wieder wiederholen.

Fibonacci ist jedoch tatsächlich ein kaputtes Beispiel, und ich denke, die Iteration ist tatsächlich effizienter. Beachten Sie, dass fib (n) = fib (n-1) + fib (n-2) und fib (n-1) = fib (n-2) + fib (n-3). fib (n-1) wird zweimal berechnet!

Ein besseres Beispiel ist ein rekursiver Algorithmus für einen Baum. Das Problem der Analyse des übergeordneten Knotens kann in mehrere kleinere Probleme der Analyse jedes untergeordneten Knotens unterteilt werden. Im Gegensatz zum Fibonacci-Beispiel sind die kleineren Probleme unabhängig voneinander.

Also ja - Rekursion ist besser als Iteration für Probleme, die in mehrere, kleinere, unabhängige, ähnliche Probleme unterteilt werden können.

Ihre Leistung verschlechtert sich bei Verwendung der Rekursion, da das Aufrufen einer Methode in einer beliebigen Sprache eine Menge Vorbereitung erfordert: Der aufrufende Code gibt eine Rücksprungadresse, Aufrufparameter, einige andere Kontextinformationen wie Prozessorregister werden möglicherweise irgendwo gespeichert, und zur Rückgabezeit Die aufgerufene Methode gibt einen Rückgabewert aus, der dann vom Aufrufer abgerufen wird, und alle zuvor gespeicherten Kontextinformationen werden wiederhergestellt. Der Leistungsunterschied zwischen einem iterativen und einem rekursiven Ansatz liegt in der Zeit, die diese Operationen benötigen.

Aus Sicht der Implementierung bemerken Sie den Unterschied wirklich, wenn die Zeit, die für die Bearbeitung des aufrufenden Kontexts benötigt wird, mit der Zeit vergleichbar ist, die Ihre Methode für die Ausführung benötigt. Wenn die Ausführung Ihrer rekursiven Methode länger dauert als der aufrufende Kontextverwaltungsteil, gehen Sie rekursiv vor, da der Code im Allgemeinen besser lesbar und leicht zu verstehen ist und Sie den Leistungsverlust nicht bemerken. Andernfalls wird aus Effizienzgründen iterativ vorgegangen.

Ich glaube, dass die Schwanzrekursion in Java derzeit nicht optimiert ist. Die Details werden in dieser Diskussion über LtU und die zugehörigen Links verteilt. Es mag eine Funktion in der kommenden Version 7 sein, aber anscheinend bringt es in Kombination mit Stack Inspection gewisse Schwierigkeiten mit sich, da bestimmte Frames fehlen würden. Stack Inspection wird seit Java 2 zur Implementierung des detaillierten Sicherheitsmodells verwendet.

http://lambda-the-ultimate.org/node/1333

Es gibt viele Fälle, in denen die iterative Methode eine viel elegantere Lösung bietet. Das häufigste Beispiel ist das Durchlaufen eines Binärbaums, sodass die Wartung nicht unbedingt schwieriger ist. Im Allgemeinen sind iterative Versionen normalerweise etwas schneller (und können während der Optimierung durchaus eine rekursive Version ersetzen), aber rekursive Versionen sind einfacher zu verstehen und korrekt zu implementieren.

Rekursion ist in einigen Situationen sehr nützlich. Betrachten Sie zum Beispiel den Code zum Finden der Fakultät

int factorial ( int input )
{
  int x, fact = 1;
  for ( x = input; x > 1; x--)
     fact *= x;
  return fact;
}

Betrachten Sie es nun mit der rekursiven Funktion

int factorial ( int input )
{
  if (input == 0)
  {
     return 1;
  }
  return input * factorial(input - 1);
}

Wenn wir diese beiden beobachten, können wir sehen, dass die Rekursion leicht zu verstehen ist. Aber wenn es nicht mit Vorsicht verwendet wird, kann es auch so fehleranfällig sein. Angenommen, wenn wir etwas verpassen if (input == 0), wird der Code für einige Zeit ausgeführt und endet normalerweise mit einem Stapelüberlauf.

In vielen Fällen ist die Rekursion aufgrund des Caching schneller, was die Leistung verbessert. Hier ist beispielsweise eine iterative Version der Zusammenführungssortierung unter Verwendung der traditionellen Zusammenführungsroutine. Es wird langsamer als die rekursive Implementierung ausgeführt, da verbesserte Leistungen zwischengespeichert werden.

Iterative Implementierung

public static void sort(Comparable[] a)
{
    int N = a.length;
    aux = new Comparable[N];
    for (int sz = 1; sz < N; sz = sz+sz)
        for (int lo = 0; lo < N-sz; lo += sz+sz)
            merge(a, lo, lo+sz-1, Math.min(lo+sz+sz-1, N-1));
}

Rekursive Implementierung

private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi)
{
    if (hi <= lo) return;
    int mid = lo + (hi - lo) / 2;
    sort(a, aux, lo, mid);
    sort(a, aux, mid+1, hi);
    merge(a, aux, lo, mid, hi);
}

PS - das sagte Professor Kevin Wayne (Princeton University) zu dem auf Coursera vorgestellten Kurs über Algorithmen.

Bei Verwendung der Rekursion fallen bei jeder "Iteration" die Kosten für einen Funktionsaufruf an, während Sie bei einer Schleife normalerweise nur ein Inkrement / Dekrement bezahlen. Wenn der Code für die Schleife nicht viel komplizierter ist als der Code für die rekursive Lösung, ist die Schleife normalerweise der Rekursion überlegen.

Rekursion und Iteration hängen von der Geschäftslogik ab, die Sie implementieren möchten. In den meisten Fällen kann sie jedoch austauschbar verwendet werden. Die meisten Entwickler entscheiden sich für eine Rekursion, da diese leichter zu verstehen ist.

Das hängt von der Sprache ab. In Java sollten Sie Schleifen verwenden. Funktionssprachen optimieren die Rekursion.

Wenn Sie nur über eine Liste iterieren, iterieren Sie sicher weg.

In einigen anderen Antworten wurde die Baumdurchquerung (Tiefe zuerst) erwähnt. Es ist wirklich ein großartiges Beispiel, weil es sehr häufig vorkommt, dass eine sehr häufige Datenstruktur verwendet wird. Die Rekursion ist für dieses Problem äußerst intuitiv.

Überprüfen Sie die "find" -Methoden hier: http://penguin.ewu.edu/cscd300/Topic/BSTintro/index.html

Die Rekursion ist einfacher (und damit grundlegender) als jede mögliche Definition einer Iteration. Sie können ein Turing-vollständiges System mit nur zwei Kombinatoren definieren (ja, sogar eine Rekursion selbst ist in einem solchen System ein abgeleiteter Begriff). Die Lambda- Rechnung ist ein ebenso leistungsfähiges Grundsystem mit rekursiven Funktionen. Wenn Sie jedoch eine Iteration richtig definieren möchten, benötigen Sie zunächst viel mehr Grundelemente.

Was den Code betrifft - nein, rekursiver Code ist in der Tat viel einfacher zu verstehen und zu pflegen als ein rein iterativer, da die meisten Datenstrukturen rekursiv sind. Um es richtig zu machen, würde man natürlich eine Sprache brauchen, die Funktionen und Abschlüsse höherer Ordnung unterstützt - um alle Standardkombinatoren und -iteratoren auf eine ordentliche Weise zu erhalten. In C ++ können komplizierte rekursive Lösungen natürlich etwas hässlich aussehen, es sei denn, Sie sind ein Hardcore-Benutzer von FC ++ und dergleichen.

Ich würde denken, dass bei einer (nicht schwanzförmigen) Rekursion bei jedem Aufruf der Funktion ein Leistungseinbruch für die Zuweisung eines neuen Stapels usw. auftreten würde (natürlich abhängig von der Sprache).

es hängt von der "Rekursionstiefe" ab. Dies hängt davon ab, inwieweit der Funktionsaufruf-Overhead die Gesamtausführungszeit beeinflusst.

Beispielsweise ist die rekursive Berechnung der klassischen Fakultät sehr ineffizient, weil: - das Risiko eines Datenüberlaufs - das Risiko eines Stapelüberlaufs - der Funktionsaufruf-Overhead 80% der Ausführungszeit beansprucht

während die Entwicklung eines Min-Max-Algorithmus für die Positionsanalyse im Schachspiel, der nachfolgende N Züge analysiert, kann in Rekursion über die "Analysetiefe" implementiert werden (wie ich es tue ^ _ ^)

Rekursion? Wo fange ich an? Das Wiki wird Ihnen sagen, dass es sich um das Wiederholen von Elementen auf selbstähnliche Weise handelt.

Damals, als ich C machte, war die C ++ - Rekursion ein Geschenk Gottes, so etwas wie "Schwanzrekursion". Sie werden auch feststellen, dass viele Sortieralgorithmen die Rekursion verwenden. Beispiel für eine schnelle Sortierung: http://alienryderflex.com/quicksort/

Rekursion ist wie jeder andere Algorithmus, der für ein bestimmtes Problem nützlich ist. Vielleicht finden Sie nicht sofort oder häufig eine Verwendung, aber es wird ein Problem geben, bei dem Sie froh sind, dass es verfügbar ist.

Wenn es sich bei der rekursiven Funktion in C ++ um eine Vorlagenfunktion handelt, hat der Compiler eine größere Chance, sie zu optimieren, da alle Typabzüge und Funktionsinstanziierungen in der Kompilierungszeit erfolgen. Moderne Compiler können die Funktion nach Möglichkeit auch inline setzen. Wenn man also Optimierungsflags wie -O3oder -O2in verwendet g++, haben Rekursionen möglicherweise die Chance, schneller als Iterationen zu sein. In iterativen Codes hat der Compiler weniger Chancen, ihn zu optimieren, da er sich bereits im mehr oder weniger optimalen Zustand befindet (wenn er gut genug geschrieben ist).

In meinem Fall habe ich versucht, die Matrixexponentiation durch Quadrieren mit Armadillo-Matrixobjekten sowohl rekursiv als auch iterativ zu implementieren. Den Algorithmus finden Sie hier ... https://en.wikipedia.org/wiki/Exponentiation_by_squaring . Meine Funktionen wurden mit Vorlagen versehen und ich habe 1,000,000 12x12Matrizen berechnet, die zur Potenz erhoben wurden 10. Ich habe folgendes Ergebnis erhalten:

iterative + optimisation flag -O3 -> 2.79.. sec
recursive + optimisation flag -O3 -> 1.32.. sec

iterative + No-optimisation flag  -> 2.83.. sec
recursive + No-optimisation flag  -> 4.15.. sec

Diese Ergebnisse wurden mit gcc-4.8 mit c ++ 11 flag ( -std=c++11) und Armadillo 6.1 mit Intel mkl erzielt. Intel Compiler zeigt auch ähnliche Ergebnisse.

Mike ist richtig. Die Schwanzrekursion wird weder vom Java-Compiler noch von der JVM optimiert. Sie werden immer einen Stapelüberlauf mit so etwas bekommen:

int count(int i) {
  return i >= 100000000 ? i : count(i+1);
}

Sie müssen bedenken, dass bei Verwendung einer zu tiefen Rekursion je nach zulässiger Stapelgröße ein Stapelüberlauf auftritt. Um dies zu verhindern, stellen Sie sicher, dass Sie einen Basisfall bereitstellen, der Ihre Rekursion beendet.

Die Rekursion hat den Nachteil, dass der Algorithmus, den Sie mit der Rekursion schreiben, eine O (n) -Raumkomplexität aufweist. Während iterative Ansätze eine Raumkomplexität von O (1) haben. Dies ist der Vorteil der Verwendung von Iteration gegenüber Rekursion. Warum verwenden wir dann Rekursion?

Siehe unten.

Manchmal ist es einfacher, einen Algorithmus mithilfe der Rekursion zu schreiben, während es etwas schwieriger ist, denselben Algorithmus mithilfe der Iteration zu schreiben. In diesem Fall müssten Sie den Stapel selbst handhaben, wenn Sie sich für den Iterationsansatz entscheiden.

Wenn die Iterationen atomar und um Größenordnungen teurer sind als das Verschieben eines neuen Stapelrahmens und das Erstellen eines neuen Threads und Sie mehrere Kerne haben und Ihre Laufzeitumgebung alle verwenden kann, kann ein rekursiver Ansatz in Kombination mit einem enormen Leistungsschub führen Multithreading. Wenn die durchschnittliche Anzahl von Iterationen nicht vorhersehbar ist, ist es möglicherweise eine gute Idee, einen Thread-Pool zu verwenden, der die Thread-Zuordnung steuert und verhindert, dass Ihr Prozess zu viele Threads erstellt und das System überlastet.

In einigen Sprachen gibt es beispielsweise rekursive Multithread-Zusammenführungssortierungsimplementierungen.

Aber auch hier kann Multithreading eher mit Schleifen als mit Rekursion verwendet werden. Wie gut diese Kombination funktioniert, hängt also von mehr Faktoren ab, einschließlich des Betriebssystems und seines Thread-Zuweisungsmechanismus.

Soweit ich weiß, optimiert Perl keine rekursiven Aufrufe, aber Sie können es vortäuschen.

sub f{
  my($l,$r) = @_;

  if( $l >= $r ){
    return $l;
  } else {

    # return f( $l+1, $r );

    @_ = ( $l+1, $r );
    goto &f;

  }
}

Beim ersten Aufruf wird Speicherplatz auf dem Stapel zugewiesen. Dann ändert es seine Argumente und startet die Unterroutine neu, ohne dem Stapel etwas mehr hinzuzufügen. Es wird daher so tun, als hätte es sich nie selbst genannt und es in einen iterativen Prozess verwandelt.

Beachten Sie, dass es kein " my @_;" oder " local @_;" gibt. Andernfalls würde es nicht mehr funktionieren.

Mit nur Chrome 45.0.2454.85 m scheint die Rekursion eine schöne Menge schneller zu sein.

Hier ist der Code:

(function recursionVsForLoop(global) {
    "use strict";

    // Perf test
    function perfTest() {}

    perfTest.prototype.do = function(ns, fn) {
        console.time(ns);
        fn();
        console.timeEnd(ns);
    };

    // Recursion method
    (function recur() {
        var count = 0;
        global.recurFn = function recurFn(fn, cycles) {
            fn();
            count = count + 1;
            if (count !== cycles) recurFn(fn, cycles);
        };
    })();

    // Looped method
    function loopFn(fn, cycles) {
        for (var i = 0; i < cycles; i++) {
            fn();
        }
    }

    // Tests
    var curTest = new perfTest(),
        testsToRun = 100;

    curTest.do('recursion', function() {
        recurFn(function() {
            console.log('a recur run.');
        }, testsToRun);
    });

    curTest.do('loop', function() {
        loopFn(function() {
            console.log('a loop run.');
        }, testsToRun);
    });

})(window);

ERGEBNISSE

// 100 Läufe mit Standard for Schleife

100x für Schleifenlauf. Zeit bis zur Fertigstellung: 7,683 ms

// 100 Läufe unter Verwendung eines funktionalen rekursiven Ansatzes mit Schwanzrekursion

100x Rekursionslauf. Zeit bis zur Fertigstellung: 4.841ms

Im folgenden Screenshot gewinnt die Rekursion erneut mit einem größeren Vorsprung, wenn sie mit 300 Zyklen pro Test ausgeführt wird

Ich fand einen weiteren Unterschied zwischen diesen Ansätzen. Es sieht einfach und unwichtig aus, spielt aber eine sehr wichtige Rolle, während Sie sich auf Interviews vorbereiten und dieses Thema auftaucht. Schauen Sie also genau hin.

Kurz gesagt: 1) Das iterative Durchlaufen nach der Bestellung ist nicht einfach - das macht die DFT komplexer. 2) Die Überprüfung der Zyklen wird durch Rekursion einfacher

Einzelheiten:

Im rekursiven Fall ist es einfach, Vor- und Nachdurchläufe zu erstellen:

Stellen Sie sich eine ziemlich normale Frage vor: "Drucken Sie alle Aufgaben aus, die ausgeführt werden sollen, um die Aufgabe 5 auszuführen, wenn Aufgaben von anderen Aufgaben abhängen."

Beispiel:

    //key-task, value-list of tasks the key task depends on
    //"adjacency map":
    Map<Integer, List<Integer>> tasksMap = new HashMap<>();
    tasksMap.put(0, new ArrayList<>());
    tasksMap.put(1, new ArrayList<>());

    List<Integer> t2 = new ArrayList<>();
    t2.add(0);
    t2.add(1);
    tasksMap.put(2, t2);

    List<Integer> t3 = new ArrayList<>();
    t3.add(2);
    t3.add(10);
    tasksMap.put(3, t3);

    List<Integer> t4 = new ArrayList<>();
    t4.add(3);
    tasksMap.put(4, t4);

    List<Integer> t5 = new ArrayList<>();
    t5.add(3);
    tasksMap.put(5, t5);

    tasksMap.put(6, new ArrayList<>());
    tasksMap.put(7, new ArrayList<>());

    List<Integer> t8 = new ArrayList<>();
    t8.add(5);
    tasksMap.put(8, t8);

    List<Integer> t9 = new ArrayList<>();
    t9.add(4);
    tasksMap.put(9, t9);

    tasksMap.put(10, new ArrayList<>());

    //task to analyze:
    int task = 5;


    List<Integer> res11 = getTasksInOrderDftReqPostOrder(tasksMap, task);
    System.out.println(res11);**//note, no reverse required**

    List<Integer> res12 = getTasksInOrderDftReqPreOrder(tasksMap, task);
    Collections.reverse(res12);//note reverse!
    System.out.println(res12);

    private static List<Integer> getTasksInOrderDftReqPreOrder(Map<Integer, List<Integer>> tasksMap, int task) {
         List<Integer> result = new ArrayList<>();
         Set<Integer> visited = new HashSet<>();
         reqPreOrder(tasksMap,task,result, visited);
         return result;
    }

private static void reqPreOrder(Map<Integer, List<Integer>> tasksMap, int task, List<Integer> result, Set<Integer> visited) {

    if(!visited.contains(task)) {
        visited.add(task);
        result.add(task);//pre order!
        List<Integer> children = tasksMap.get(task);
        if (children != null && children.size() > 0) {
            for (Integer child : children) {
                reqPreOrder(tasksMap,child,result, visited);
            }
        }
    }
}

private static List<Integer> getTasksInOrderDftReqPostOrder(Map<Integer, List<Integer>> tasksMap, int task) {
    List<Integer> result = new ArrayList<>();
    Set<Integer> visited = new HashSet<>();
    reqPostOrder(tasksMap,task,result, visited);
    return result;
}

private static void reqPostOrder(Map<Integer, List<Integer>> tasksMap, int task, List<Integer> result, Set<Integer> visited) {
    if(!visited.contains(task)) {
        visited.add(task);
        List<Integer> children = tasksMap.get(task);
        if (children != null && children.size() > 0) {
            for (Integer child : children) {
                reqPostOrder(tasksMap,child,result, visited);
            }
        }
        result.add(task);//post order!
    }
}

Beachten Sie, dass für die rekursive Nachbestellungsdurchquerung keine spätere Umkehrung des Ergebnisses erforderlich ist. Kinder zuerst gedruckt und Ihre Aufgabe in der Frage zuletzt gedruckt. Alles ist gut. Sie können eine rekursive Vorbestellungsdurchquerung durchführen (siehe auch oben), für die eine Umkehrung der Ergebnisliste erforderlich ist.

Nicht so einfach mit iterativem Ansatz! Beim iterativen Ansatz (mit einem Stapel) können Sie nur eine Vorbestellungsdurchquerung durchführen, sodass Sie das Ergebnisarray am Ende umkehren müssen:

    List<Integer> res1 = getTasksInOrderDftStack(tasksMap, task);
    Collections.reverse(res1);//note reverse!
    System.out.println(res1);

    private static List<Integer> getTasksInOrderDftStack(Map<Integer, List<Integer>> tasksMap, int task) {
    List<Integer> result = new ArrayList<>();
    Set<Integer> visited = new HashSet<>();
    Stack<Integer> st = new Stack<>();


    st.add(task);
    visited.add(task);

    while(!st.isEmpty()){
        Integer node = st.pop();
        List<Integer> children = tasksMap.get(node);
        result.add(node);
        if(children!=null && children.size() > 0){
            for(Integer child:children){
                if(!visited.contains(child)){
                    st.add(child);
                    visited.add(child);
                }
            }
        }
        //If you put it here - it does not matter - it is anyway a pre-order
        //result.add(node);
    }
    return result;
}

Sieht einfach aus, nein?

Aber es ist eine Falle in einigen Interviews.

Dies bedeutet Folgendes: Mit dem rekursiven Ansatz können Sie Depth First Traversal implementieren und dann auswählen, welche Reihenfolge Sie vor oder nach dem Vorgang benötigen (indem Sie einfach die Position des "Drucks" ändern, in unserem Fall "Hinzufügen zur Ergebnisliste"). ). Mit dem iterativen Ansatz (ein Stapel) können Sie problemlos nur das Durchlaufen vorbestellen. In Situationen, in denen Kinder zuerst gedruckt werden müssen (so ziemlich alle Situationen, in denen Sie mit dem Drucken von den unteren Knoten nach oben beginnen müssen), befinden Sie sich in die Schwierigkeiten. Wenn Sie diese Probleme haben, können Sie sie später rückgängig machen, dies ist jedoch eine Ergänzung Ihres Algorithmus. Und wenn ein Interviewer auf seine Uhr schaut, kann dies ein Problem für Sie sein. Es gibt komplexe Möglichkeiten, eine iterative Nachbestellungsdurchquerung durchzuführen. Sie existieren, sind jedoch nicht einfach . Beispiel:https://www.geeksforgeeks.org/iterative-postorder-traversal-using-stack/

Fazit: Ich würde bei Interviews Rekursion verwenden, es ist einfacher zu verwalten und zu erklären. In dringenden Fällen haben Sie einen einfachen Weg von der Durchquerung vor und nach der Bestellung. Mit iterativ sind Sie nicht so flexibel.

Ich würde die Rekursion verwenden und dann sagen: "Ok, aber iterativ kann mir eine direktere Kontrolle über den verwendeten Speicher ermöglichen. Ich kann die Stapelgröße leicht messen und einen gefährlichen Überlauf verbieten."

Ein weiteres Plus der Rekursion: Es ist einfacher, Zyklen in einem Diagramm zu vermeiden / zu bemerken.

Beispiel (Preudocode):

dft(n){
    mark(n)
    for(child: n.children){
        if(marked(child)) 
            explode - cycle found!!!
        dft(child)
    }
    unmark(n)
}

Es kann Spaß machen, es als Rekursion oder als Übung zu schreiben.

Wenn der Code jedoch in der Produktion verwendet werden soll, müssen Sie die Möglichkeit eines Stapelüberlaufs berücksichtigen.

Durch die Optimierung der Schwanzrekursion kann ein Stapelüberlauf vermieden werden. Sie möchten sich jedoch die Mühe machen, dies zu tun, und Sie müssen wissen, dass Sie sich darauf verlassen können, dass die Optimierung in Ihrer Umgebung erfolgt.

Jedes Mal, wenn der Algorithmus erneut ausgeführt wird, wie groß ist die Datengröße oder n verringert verringert?

Wenn Sie die Datengröße nbei jedem erneuten Vorgang um die Hälfte reduzieren, müssen Sie sich im Allgemeinen keine Gedanken über den Stapelüberlauf machen. Angenommen, es muss 4.000 Ebenen tief oder 10.000 Ebenen tief sein, damit das Programm einen Überlauf stapelt, dann muss Ihre Datengröße ungefähr 2 ^{4000 betragen,} damit Ihr Programm einen Überlauf stapelt. Um das ins rechte Licht zu rücken: Ein größtes Speichergerät kann in letzter Zeit 2 ⁶¹ Byte aufnehmen, und wenn Sie 2 ⁶¹ solcher Geräte haben, haben Sie es nur mit 2 ¹²² Daten zu tun . Wenn Sie alle Atome im Universum betrachten, wird geschätzt, dass es weniger als 2 sein kann ^{84 sein kann} . Wenn Sie alle Daten im Universum und ihre Zustände für jede Millisekunde seit der Geburt des Universums, die auf 14 Milliarden Jahre geschätzt wurde, verarbeiten müssen, sind es möglicherweise nur 2 ¹⁵³ . Also, wenn Ihr Programm 2 ^{4000 verarbeiten kann}Dateneinheiten oder n, Sie können alle Daten im Universum verarbeiten und das Programm stapelt keinen Überlauf. Wenn Sie sich nicht mit Zahlen befassen müssen, die so groß wie 2 ^{4000 sind} (eine 4000-Bit-Ganzzahl) sind, müssen Sie sich im Allgemeinen keine Gedanken über den Stapelüberlauf machen.

Wenn Sie jedoch die Datengröße nbei jeder Wiederholung um einen konstanten Betrag reduzieren, kann es zu einem Stapelüberlauf kommen, wenn Ihr Programm gut läuft, wenn dies der Fall nist, 1000aber in bestimmten Situationen nnur dann20000 .

Wenn Sie also die Möglichkeit eines Stapelüberlaufs haben, versuchen Sie, eine iterative Lösung daraus zu machen.

Ich werde Ihre Frage beantworten, indem ich eine Haskell-Datenstruktur durch "Induktion" entwerfe, was eine Art "Dual" für die Rekursion darstellt. Und dann werde ich zeigen, wie diese Dualität zu schönen Dingen führt.

Wir führen einen Typ für einen einfachen Baum ein:

data Tree a = Branch (Tree a) (Tree a)
            | Leaf a
            deriving (Eq)

Wir können diese Definition so lesen, dass sie sagt: "Ein Baum ist ein Zweig (der zwei Bäume enthält) oder ein Blatt (der einen Datenwert enthält)". Das Blatt ist also eine Art Minimalfall. Wenn ein Baum kein Blatt ist, muss es ein zusammengesetzter Baum sein, der zwei Bäume enthält. Dies sind die einzigen Fälle.

Machen wir einen Baum:

example :: Tree Int
example = Branch (Leaf 1) 
                 (Branch (Leaf 2) 
                         (Leaf 3))

Nehmen wir nun an, wir möchten jedem Wert im Baum 1 hinzufügen. Wir können dies tun, indem wir anrufen:

addOne :: Tree Int -> Tree Int
addOne (Branch a b) = Branch (addOne a) (addOne b)
addOne (Leaf a)     = Leaf (a + 1)

Beachten Sie zunächst, dass dies tatsächlich eine rekursive Definition ist. Es werden die Datenkonstruktoren Branch und Leaf als Fälle verwendet (und da Leaf minimal ist und dies die einzig möglichen Fälle sind), sind wir sicher, dass die Funktion beendet wird.

Was würde es brauchen, um addOne iterativ zu schreiben? Wie sieht das Schleifen in eine beliebige Anzahl von Zweigen aus?

Auch diese Art der Rekursion kann oft als "Funktor" herausgerechnet werden. Wir können Bäume zu Funktoren machen, indem wir definieren:

instance Functor Tree where fmap f (Leaf a)     = Leaf (f a)
                            fmap f (Branch a b) = Branch (fmap f a) (fmap f b)

und definieren:

addOne' = fmap (+1)

Wir können andere Rekursionsschemata wie den Katamorphismus (oder die Faltung) für einen algebraischen Datentyp herausrechnen. Mit einem Katamorphismus können wir schreiben:

addOne'' = cata go where
           go (Leaf a) = Leaf (a + 1)
           go (Branch a b) = Branch a b

Ein Stapelüberlauf tritt nur auf, wenn Sie in einer Sprache programmieren, in der keine Speicherverwaltung integriert ist. Andernfalls stellen Sie sicher, dass Ihre Funktion etwas enthält (oder einen Funktionsaufruf, STDLbs usw.). Ohne Rekursion wäre es einfach nicht möglich, Dinge wie ... Google oder SQL oder einen Ort zu haben, an dem große Datenstrukturen (Klassen) oder Datenbanken effizient sortiert werden müssen.

Rekursion ist der richtige Weg, wenn Sie Dateien durchlaufen möchten. Sie sind sich ziemlich sicher, dass 'find * | so ist grep * 'funktioniert. Eine Art doppelte Rekursion, besonders mit der Pipe (aber machen Sie nicht so viele Systemaufrufe wie so viele, wenn Sie etwas herausbringen möchten, das andere verwenden können).

Höhere Sprachen und sogar clang / cpp können es im Hintergrund gleich implementieren.