it-swarm-eu.dev

Rekursion oder Iteration?

Gibt es einen Leistungseinbruch, wenn wir in Algorithmen, bei 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 zum Vorführen eines einfachen Iterationsalgorithmus verwendeten. Spielt der Compiler eine wichtige Rolle bei der Entscheidung, was verwendet werden soll?

210
Omnipotent

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

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 schauen Sie sich erst dann die Optimierung an, indem Sie zu einer iterativen Implementierung übergehen. Vielleicht möchten Sie sich mit Memoisierung und dynamische Programmierung befassen.

176
Paul Osborne

Durch Schleifen wird möglicherweise ein Leistungsgewinn für Ihr Programm erzielt. Rekursion kann einen Leistungsgewinn für Ihren Programmierer erzielen. Wählen Sie, was in Ihrer Situation wichtiger ist!

309
Leigh Caldwell

Das Vergleichen der Rekursion mit der Iteration entspricht dem Vergleichen eines Kreuzschlitzschraubendrehers mit einem Schlitzschraubendreher. Zum größten Teil könnte entfernen Sie alle Kreuzschlitzschrauben mit einem flachen Kopf, aber es wäre einfacher, wenn Sie den für diese Schraube vorgesehenen Schraubendreher verwenden würden, oder?

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

Einige rekursive Algorithmen verwenden auch "Lazy Evaluation", wodurch sie effizienter sind als ihre iterativen Brüder. Dies bedeutet, dass sie die teuren Berechnungen nur zu dem Zeitpunkt durchführen, zu dem sie benötigt werden, und nicht bei jedem Durchlauf der Schleife.

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, mit Haskel mithilfe von Rekursion umzugehen, aber da PHP hatte keine einfache Möglichkeit, die gleiche 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 der Rekursion resultiert aus den hohen Kosten und der Ineffizienz in imperativen Sprachen. Der Autor dieses Artikels spricht darüber, wie man rekursive Algorithmen optimiert, um sie schneller und effizienter zu machen. Er geht auch darauf ein, wie man eine traditionelle Schleife in eine rekursive Funktion umwandelt und welche Vorteile die Verwendung der Endrekursion bietet. Seine abschließenden Worte fassten einige meiner wichtigsten Punkte, die ich denke, wirklich zusammen:

"Durch rekursives Programmieren kann der Programmierer den Code auf eine Weise 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? (Antwort)

Hier ist ein Link zu einer Antwort auf eine Stapelüberlauf-Frage, die Ihrer ähnlich ist. Der Autor weist darauf hin, dass viele der Benchmarks, die entweder mit einer Wiederholung oder einer Schleife 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 wichtigste Punkt, den Sie aus diesem Link ziehen sollten, ist, dass es sehr schwierig ist, die Frage in einem sprachunabhängigen/situationsblinden Sinn zu beantworten.

Ist die Rekursion jemals schneller als eine Schleife?

76
Swift

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

Trotzdem 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.

16
Doron Yaacoby

Typischerweise würde man erwarten, dass der Leistungsnachteil in die andere Richtung geht. Rekursive Aufrufe können zur Erstellung 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 für Aufgaben, die Sie möglicherweise rekursiv angeben, wie z Maximalwert in einer Baumdatenstruktur In diesen Fällen möchten Sie sich wirklich an Schleifen halten.

Wenn Sie gute rekursive Funktionen schreiben, kann dies die Leistung etwas beeinträchtigen, vorausgesetzt, Sie haben einen Compiler, der die Schwanzrekursionen usw. optimiert auf.)

Abgesehen von "Edge" -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 ermittelt haben.

11
zweiterlinde

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. Durch Iteration können Sie nur eine einzelne Funktion immer wieder wiederholen.

Allerdings ist Fibonacci tatsächlich ein gebrochenes Beispiel und ich denke, dass die Iteration tatsächlich effizienter ist. 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 des Analysierens des Elternknotens kann in mehrere kleinere Probleme des Analysierens jedes Kindknotens 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.

8
Ben

Ihre Leistung verschlechtert sich, wenn Sie die Rekursion verwenden, da der Aufruf einer Methode in einer beliebigen Sprache eine Menge Vorbereitung erfordert: Der aufrufende Code sendet eine Rücksprungadresse, Aufrufparameter, einige andere Kontextinformationen wie z Die aufgerufene Methode sendet einen Rückgabewert, der 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 erst dann, wenn die Zeit für die Verarbeitung des aufrufenden Kontexts mit der Zeit für die Ausführung Ihrer Methode vergleichbar ist. Wenn die Ausführung Ihrer rekursiven Methode länger dauert als die Ausführung des aufrufenden Kontextverwaltungsteils, verwenden Sie die rekursive Methode, da der Code im Allgemeinen besser lesbar und leicht verständlich ist und Sie den Leistungsverlust nicht bemerken. Andernfalls wird aus Effizienzgründen iterativ vorgegangen.

7
entzik

Ich glaube, Schwanzrekursion in Java ist derzeit nicht optimiert. Die Details sind in this Diskussion über LtU und die zugehörigen Links gestreut. Es kann ein Feature in der kommenden Version 7 sein, stellt aber anscheinend in Kombination mit Stack Inspection gewisse Schwierigkeiten dar, da bestimmte Frames fehlen würden. Stack Inspection wurde verwendet, um deren feinkörnige Sicherheit zu implementieren Modell seit Java 2.

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

6
Mike Edwards

In vielen Fällen ist die Rekursion aufgrund des Cachings schneller, was die Leistung verbessert. Hier ist zum Beispiel eine iterative Version der Zusammenführungssortierung unter Verwendung der herkömmlichen Zusammenführungsroutine. Es wird langsamer als die rekursive Implementierung ausgeführt, da die Leistung durch Zwischenspeichern verbessert wird.

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) zum Kurs über Algorithmen, der auf Coursera vorgestellt wurde.

5
Nikunj Banka

Es gibt viele Fälle, in denen die iterative Methode eine viel elegantere Lösung bietet. Das häufigste Beispiel hierfür ist das Durchlaufen eines Binärbaums. Daher ist die Wartung nicht unbedingt schwieriger. Im Allgemeinen sind iterative Versionen in der Regel etwas schneller (und ersetzen bei der Optimierung möglicherweise eine rekursive Version), rekursive Versionen sind jedoch einfacher zu verstehen und korrekt zu implementieren.

5
Felix

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

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

Betrachten Sie es jetzt 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 Sorgfalt verwendet wird, kann es auch sehr fehleranfällig sein. Angenommen, wenn wir if (input == 0) verpassen, wird der Code für einige Zeit ausgeführt und endet normalerweise mit einem Stapelüberlauf.

5
Harikrishnan

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

4
mc

Bei Verwendung der Rekursion fallen bei jeder "Iteration" die Kosten für einen Funktionsaufruf an, während bei einer Schleife normalerweise nur ein Inkrement/Dekrement gezahlt wird. 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.

4
MovEaxEsp

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 einfacher zu verstehen ist.

4
Warrior

Rekursion ist einfacher (und damit grundlegender) als jede mögliche Definition einer Iteration. Sie können ein Turing-vollständiges System nur mit einem Kombinatorpaar definieren (ja, auch eine Rekursion selbst ist in einem solchen System ein abgeleiteter Begriff). Lambda Kalkül ist ein ebenso mächtiges 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 warten als ein rein iterativer Code, da die meisten Datenstrukturen rekursiv sind. Um es richtig zu machen, braucht man natürlich eine Sprache mit einer Unterstützung für Funktionen und Abschlüsse höherer Ordnung - um alle Standardkombinatoren und -iteratoren auf übersichtliche 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 ähnlich.

3
SK-logic

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

Einige andere Antworten haben die (Tiefen-) Baumdurchquerung erwähnt. Es ist wirklich ein großartiges Beispiel, weil es eine sehr häufige Aufgabe ist, eine sehr häufige Datenstruktur zu bearbeiten. Die Rekursion ist für dieses Problem äußerst intuitiv.

Schauen Sie sich die "find" -Methoden hier an: http://penguin.ewu.edu/cscd300/Topic/BSTintro/index.html

3
Joe Cheng

Ich würde in (non tail) Rekursion denken, dass es bei jedem Aufruf der Funktion einen Performance-Hit für die Zuweisung eines neuen Stacks usw. geben würde (natürlich abhängig von der Sprache).

2
metadave

Wenn es sich bei der rekursiven Funktion in C++ um eine Vorlage handelt, hat der Compiler mehr Chancen, sie zu optimieren, da alle Typherabsetzungen und Funktionsinstanziierungen in der Kompilierungszeit erfolgen. Moderne Compiler können die Funktion nach Möglichkeit auch inline stellen. Wenn man Optimierungsflags wie -O3 Oder -O2 In g++ Verwendet, besteht die Möglichkeit, dass Rekursionen schneller sind als Iterationen. In iterativen Codes hat der Compiler weniger Chancen, sie zu optimieren, da sie sich bereits im mehr oder weniger optimalen Zustand befinden (sofern sie gut genug geschrieben sind).

In meinem Fall habe ich versucht, die Matrixexponentiation durch Quadrieren mit Armadillo-Matrixobjekten sowohl auf rekursive als auch auf iterative Weise zu implementieren. Den Algorithmus finden Sie hier ... https://en.wikipedia.org/wiki/Exponentiation_by_squaring . Meine Funktionen wurden als Templat erstellt und ich habe 1,000,00012x12 Matrizen 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.

2
Titas Chanda

Rekursion? Wo soll ich anfangen? Das Wiki sagt dir, dass es sich um das Wiederholen von Elementen auf ähnliche Weise handelt.

Damals, als ich C machte, war die C++ - Rekursion ein Glücksfall, 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 eine Verwendung nicht sofort oder häufig, aber es gibt ein Problem, bei dem Sie froh sind, dass sie verfügbar ist.

2
Nickz

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

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

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

2
ugasoft

Mike ist richtig. Die Schwanzrekursion wird nicht durch den Java) - Compiler oder die JVM optimiert. Sie werden immer einen Stapelüberlauf mit so etwas bekommen:

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

Rekursion hat den Nachteil, dass der Algorithmus, den Sie mit Rekursion schreiben, O(n) Raumkomplexität hat. Während iterativer Ansatz eine Raumkomplexität von O (1) hat. Dies ist der Vorteil der Verwendung von Iteration gegenüber rekursion Warum verwenden wir dann die Rekursion?

Siehe unten.

Manchmal ist es einfacher, einen Algorithmus mithilfe von Rekursion zu schreiben, während es etwas schwieriger ist, denselben Algorithmus mithilfe von Iteration zu schreiben.

1

Beachten Sie, 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 angeben, der Ihre Rekursion beendet.

1
Grigori A.

Soweit ich weiß, optimiert Perl keine tail-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 würde es sich niemals selbst nennen und es in einen iterativen Prozess verwandeln.

Beachten Sie, dass es kein "my @_;" oder "local @_; ", wenn du es tun würdest, würde es nicht mehr funktionieren.

0
Brad Gilbert

Wenn die Iterationen atomar und um Größenordnungen teurer sind als das Verschieben eines neuen Stapelrahmens nd Erstellen eines neuen Threads nd Sie haben mehrere Kerne nd Ihre Laufzeitumgebung kann alle von ihnen verwenden, dann könnte ein rekursiver Ansatz in Kombination mit Multithreading zu einer enormen Leistungssteigerung führen. Wenn die durchschnittliche Anzahl der Iterationen nicht vorhersehbar ist, empfiehlt es sich möglicherweise, 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 Mergesort-Implementierungen mit mehreren Threads.

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

0
ccpizza

Mit nur Chrome 45.0.2454.85 m scheint die Rekursion um einiges 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 wird mit der Standard-for-Schleife ausgeführt

100x für Schleifenlauf. Zeit zu vervollständigen: 7.683ms

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

100x Rekursionslauf. Zeit bis zum Abschluss: 4.841ms

In der Abbildung unten gewinnt die Rekursion erneut um ein Vielfaches, wenn sie mit 300 Zyklen pro Test ausgeführt wird.

Recursion wins again!

0
Alpha G33k