Rekursion oder Iteration?

StackOverflow https://stackoverflow.com/questions/72209

Frage

Gibt es eine Leistung getroffen, wenn wir eine Schleife anstelle von Rekursion oder umgekehrt in Algorithmen verwenden, in denen beide den gleichen Zweck dienen können? ZB: Überprüfen Sie, ob der angegebene String ein Palindrom ist. Ich habe viele Programmierer gesehen als Mittel Rekursion zu zeigen, wenn eine einfache Iteration-Algorithmus die Rechnung passen. Hat der Compiler eine entscheidende Rolle spielt bei der Entscheidung, was zu verwenden?

War es hilfreich?

Lösung

Es ist möglich, dass Rekursion teurer sein wird, je nachdem, ob die rekursive Funktion ist Schwanz rekursive (die letzte Zeile ist rekursiven Aufruf). Endrekursion sollte durch den Compiler und optimierte sein iteratives Gegenstück erkannt werden (unter Beibehaltung des prägnanten, klaren Umsetzungs Sie in Ihrem Code haben).

Ich würde den Algorithmus in der Art und Weise schreiben, die am meisten Sinn macht und am deutlichsten für die Armen Sauger (sei es selbst oder jemand anderes), die den Code in ein paar Monaten oder Jahren zu halten hat. Wenn Sie in die Performance-Probleme laufen, dann wird Ihr Code profilieren, und dann und nur dann in die Optimierung suchen, indem auf eine iterative Implementierung bewegt über. Sie können schauen wollen memoization und dynamische Programmierung .

Andere Tipps

Loops kann eine Leistungssteigerung für Ihr Programm erreichen. Rekursion kann eine Leistungssteigerung für Ihren Programmierer erreichen. Wählen Sie, welche ist wichtiger in Ihrer Situation!

Rekursion Iteration Vergleich ist wie ein Kreuzschlitzschraubendreher mit einem flachen Schraubendreher zu vergleichen. Zum größten Teil Sie könnte entfernen Sie alle Kreuzschlitzschraube mit einem flachen Kopf, aber es wäre nur einfacher, wenn Sie den Schraubenzieher für die Schraube richtig ausgelegt verwendet?

Einige Algorithmen nur sich selbst wegen der Art und Weise zu Rekursion verleihen sie dazu bestimmt sind (Fibonacci-Sequenzen, ein Baum wie Struktur durchqueren, etc.). Rekursion macht den Algorithmus prägnante und leichter zu verstehen (also gemeinsam nutzbare und wiederverwendbar).

Auch einige rekursive Algorithmen verwenden „Lazy Evaluation“, die sie effizienter als ihre iterativen Brüder machen. Das bedeutet, dass sie nur zu dem Zeitpunkt der teueren Berechnungen sie benötigt werden, anstatt jedes Mal, wenn die Schleife ausgeführt wird.

Das sollte ausreichen, um Sie zu erhalten begonnen. Ich werde auch einige Artikel und Beispiele für Sie graben.

Link 1: Haskel vs PHP (Rekursion vs Iteration)

Hier ist ein Beispiel, wo der Programmierer eine große Datenmenge mit PHP zu verarbeiten hatte. Er zeigt, wie leicht es wäre mit in Haskel zu behandeln gewesen Rekursion, aber da PHP keine einfache Art und Weise hatte 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-Auswertung-mit-php.html

Link 2: Mastering Rekursion

Die meisten schlechten Ruf Rekursion kommt von den hohen Kosten und Ineffizienz in imperativen Sprachen. Der Autor dieses Artikels spricht darüber, wie rekursive Algorithmen optimieren sie schneller und effizienter zu machen. Er geht auch darüber, wie eine traditionelle Schleife in eine rekursive Funktion zu konvertieren und die Vorteile der Verwendung Schwanz-End-Rekursion. Seine letzten Worte wirklich einige meiner wichtigsten Punkte zusammengefasst denke ich:

  

"rekursive Programmierung gibt dem Programmierer eine bessere Art und Weise zu organisieren,   Code in einer Weise, die sowohl wartbar und logisch konsistent ist. "

     

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

Link 3: Ist Rekursion immer schneller als Looping? (Antwort)

Hier ist ein Link zu einer Antwort für eine Stackoverflow Frage, die ähnlich wie bei Ihnen ist. Der Autor weist darauf hin, dass viele der Benchmarks mit entweder zugehörigen recursing oder Looping sind sehr sprachspezifisch. Imperative Sprachen sind in der Regel schneller mit einer Schleife und langsamer mit Rekursion und umgekehrt für die funktionalen Sprachen. Ich denke, der wichtigste Punkt von diesem Link zu nehmen ist, dass es sehr schwierig ist, die Frage in einer Sprache Agnostiker / Situation blinden Sinne zu beantworten.

  

Ist Rekursion immer schneller als Looping?

Rekursion ist teurer im Speicher, da jeder rekursive Aufruf im Allgemeinen eine Speicheradresse benötigt, um den Stapel geschoben werden - so dass später das Programm zu diesem Punkt zurückkehren konnte.

Dennoch gibt es viele Fälle, in denen Rekursion viel natürliche und lesbar als Schleife ist - wie wenn sie mit Bäumen arbeiten. In diesen Fällen würde ich das Festhalten an Rekursion empfehlen.

Normalerweise würde man die Leistungseinbuße erwartet in der anderen Richtung liegen. Rekursive Anrufe können auf den Bau von zusätzlichen Stapelrahmen führen; die Strafe für diese variiert. Auch in einigen Sprachen wie Python (genauer gesagt, in einigen Implementierungen einiger Sprachen ...), können Sie in den Stack Grenzen laufen ziemlich leicht für Aufgaben, die Sie rekursiv angeben können, wie zum Beispiel den Maximalwert in einer Baumdatenstruktur zu finden. In diesen Fällen sollten Sie wirklich mit Schleifen halten.

gute rekursiven Funktionen Schreiben können die Leistungseinbuße etwas reduzieren, vorausgesetzt, Sie einen Compiler, der Schwanz Rekursion optimiert usw. (auch überprüfen, um sicherzustellen, dass die Funktion wirklich Schwanz rekursiv ist --- es ist eines dieser Dinge, die viele Menschen machen Fehler auf.)

Neben „Kante“ Fälle (High Performance Computing, sehr große Rekursionstiefe, etc.), ist es vorzuziehen, den Ansatz zu verfolgen, die am deutlichsten Ihre Absicht zum Ausdruck bringt, ist gut entwickelt und ist wartbar. Optimieren Sie nur nach Bedarf zu identifizieren.

Rekursion ist besser als Iteration für Probleme, die in nach unten gebrochen werden können mehr , kleinere Stücke.

Um zum Beispiel einen rekursiven Fibonnaci Algorithmus zu machen, Sie fib brechen (n) in fib (n-1) und fib (n-2) und beiden Teile berechnen. Iteration können Sie nur eine einzige Funktion immer und immer wieder wiederholen.

Allerdings Fibonacci ist eigentlich ein gebrochenes Beispiel und ich denke, 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 berechnet zweimal!

Ein besseres Beispiel ist ein rekursive Algorithmus für einen Baum. Das Problem der übergeordnete Knoten Analyse kann die Analyse jedes Kind-Knoten nach unten in mehr kleinere Probleme gebrochen werden. Im Gegensatz zu dem Fibonacci-Beispiel sind die kleineren Probleme unabhängig voneinander ist.

Also ja - Rekursion ist besser als Iteration für Probleme, die mehrere, kleinere, unabhängige, ähnliche Probleme aufgeschlüsselt nach werden kann

.

Ihre Leistung verschlechtert sich, wenn die Rekursion verwenden, da der Aufruf einer Methode, in jeder Sprache schon sagt, eine Menge Vorbereitung: die Telefonvorwahl bucht eine Rücksprungadresse, Aufrufparameter, einige andere Kontextinformationen wie Prozessorregister irgendwo gespeichert werden könnten, und Rückkehr Zeit, um die aufgerufene Methode entsendet einen Rückgabewert, der dann vom Anrufer abgerufen wird, und Kontextinformationen, die zuvor gespeichert wurde gestellt. die Leistung diff zwischen einem iterativen und rekursiven einem Ansatz liegt in der Zeit, diese Operationen nehmen.

Von einer Umsetzung Sicht beginnen Sie wirklich den Unterschied bemerken, wenn die Zeit es den anrufenden Kontext zu behandeln braucht, um die Zeit vergleichbar ist, dauert es für Ihre Methode auszuführen. Wenn Ihre rekursive Methode mehr dem Aufruf Kontextmanagement Teil auszuführen nimmt dann geht die rekursive Art und Weise, wie der Code im Allgemeinen besser lesbar und leicht zu verstehen ist und Sie den Performance-Verlust nicht bemerken. Ansonsten geht iterative aus Effizienzgründen.

Ich glaube, Endrekursion in Java ist derzeit nicht optimiert. Die Details werden im gesamten diese Diskussion über LTU und die dazugehörigen Links bestreut. Es kann sein ein Feature in der kommenden Version 7, aber anscheinend stellt es gewisse Schwierigkeiten, wenn sie mit Stapel Inspektion kombiniert, da bestimmte Frames fehlen würde. Stapel Inspektion verwendet worden, da Java 2 ihr feinmaschiges Sicherheitsmodell zu implementieren.

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

Es gibt viele Fälle, in denen es eine viel elegantere Lösung über das iterative Verfahren gibt, das gemeinsame Beispiel Traversal eines binären Baum zu sein, so dass es nicht notwendigerweise schwieriger zu halten. Im Allgemeinen sind iterative Versionen in der Regel etwas schneller (und bei der Optimierung auch eine rekursive Version ersetzen kann), aber rekursive Versionen sind einfacher zu verstehen und richtig umzusetzen.

Rekursion sehr nützlich ist, ist einige Situationen. Zum Beispiel für das Finden des Fakultäts des Code betrachtet 

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

Nun betrachten es durch die rekursive Funktion mit 

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

Durch diese beiden zu beobachten, können wir sehen, dass Rekursion leicht zu verstehen ist. Aber wenn es nicht mit Sorgfalt verwendet wird, kann es so viel Fehler zu neigen. Angenommen, wenn wir if (input == 0) verfehlen, dann wird der Code für einige Zeit ausgeführt werden und endet mit in der Regel einem Stapelüberlauf.

In vielen Fällen Rekursion ist schneller, weil der Cache, das die Leistung verbessert. Zum Beispiel, hier ist eine iterative Version von Mergesort die traditionellen merge-Routine. Es läuft langsamer als die rekursive Implementierung wegen Caching verbessert Performance.

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 ist, was von Professor Kevin Wayne (Princeton University) auf dem Kurs auf Algorithmen, die auf Coursera vorgestellt wurde gesagt,

.

Rekursion verwendet, werden Sie die Kosten für einen Funktionsaufruf mit jeder „Iteration“ entstehen, während bei einer Schleife, das einzige, was Sie zahlen in der Regel ist eine Zunahme / Abnahme. Also, wenn der Code für die Schleife nicht viel komplizierter ist als der Code für die rekursive Lösung, wird Schleife in der Regel überlegen sein Rekursion.

Rekursion und Iteration hängt von der Business-Logik, die Sie allerdings implementieren möchten, in den meisten Fällen können sie austauschbar verwendet werden. Die meisten Entwickler gehen für Rekursion, weil es einfacher ist, zu verstehen.

Es hängt von der Sprache. In Java sollten Sie Loops verwenden. Funktionale Sprachen optimieren Rekursion.

Wenn Sie nur eine Liste iterieren, dann sicher, iterieren weg.

Ein paar andere Antworten haben erwähnt (depth-first) Baumdurchlauf. Es ist wirklich so ein gutes Beispiel, weil es eine sehr gewöhnliche Sache ist auf eine sehr häufige Datenstruktur zu tun. Rekursion ist extrem intuitiv für dieses Problem.

Schauen Sie sich die „finden“ Methoden hier: http://penguin.ewu.edu/cscd300/Topic/BSTintro/index.html

Rekursion ist einfacher (und damit - grundsätzlichere) als jede mögliche Definition einer Iteration. Sie können mit nur einem Paar combinators (ja, auch eine Rekursion selbst ein Turing-complete-System definieren ist ein Derivat Begriff ein solches System in). Lambda Kalkül ein ebenso leistungsfähiges grundlegendes System ist, mit rekursiven Funktionen. Aber wenn Sie eine Iteration richtig definieren möchten, würden Sie viel mehr Primitive müssen mit beginnen.

Wie für die Code - nein, das ist rekursiven Code in der Tat viel einfacher zu verstehen und als ein rein iterativ zu halten, da die meisten Datenstrukturen rekursiv sind. Natürlich ist es in Ordnung zu bringen Recht würde man eine Sprache mit einer Unterstützung für hohe Auftrag Funktionen und Verschlüsse muß, zumindest - alles in einem ordentlichen Weg, um die Standard-Kombinatoren und Iteratoren zu bekommen. In C ++, natürlich können komplizierte rekursive Lösungen ein bisschen hässlich aussehen, wenn Sie ein Hardcore-Nutzer von

Ich würde denken, in (nicht Schwanz) Rekursion würde es einen neuen Stapel eine Leistung getroffen werden usw. für die Zuweisung der Funktion jedes Mal (abhängig von der Sprache natürlich) genannt wird.

es hängt davon ab, „Rekursionstiefe“. es hängt davon ab, wie viel der Overhead-Funktionsaufruf wird die gesamte Ausführungszeit beeinflussen.

Zum Beispiel in einer rekursiven Weise die klassischen faktorielle Berechnung ist sehr ineffizient durch: - Risiko von Datenüberlauf - Risiko von Stapelüberlauf - Funktionsaufruf besetzt Overhead 80% der Ausführungszeit

, während ein Min-Max-Algorithmus zur Positionsanalyse im Schachspiel zu entwickeln, die nachfolgende N bewegt analysieren kann in Rekursion über die „Analyse Tiefe“ implementiert wird (wie ich tue ^ _ ^)

In C ++, wenn die rekursive Funktion ein Templat-eines ist, dann hat der Compiler mehr Chance, es zu optimieren, da alle vom Typ Abzug und Funktion instantiations in der Kompilierung auftritt. Moderne Compiler können die Funktion auch, wenn möglich, Inline. Also, wenn ein Optimierungs-Flags wie -O3 oder -O2 in g++ verwendet, dann kann Rekursion hat die Chance, schneller zu sein als Iterationen. In iterativem Codes erhält der Compiler weniger Chance, es zu optimieren, wie es bereits in dem mehr oder weniger optimalen Zustand (wenn sie gut genug geschrieben).

In meinem Fall, ich habe versucht Matrix Potenzierung zu implementieren durch Quadrierung Armadillo Matrix Objekte verwenden, sowohl rekursive und iterative Art und Weise. Der Algorithmus kann hier ... https://en.wikipedia.org/wiki/Exponentiation_by_squaring. Meine Funktionen wurden als Templat, und ich habe 1,000,000 berechnet 12x12 Matrizen an den Strom 10 erhöht. Ich habe folgendes Ergebnis: 

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 unter Verwendung von gcc-4.8 mit c erhalten ++ 11-Flag (-std=c++11) und Armadillo 6.1 mit Intel MKL. Intel Compiler zeigt ähnliche Ergebnisse.

Mike ist richtig. Endrekursion ist nicht durch die Java-Compiler oder die JVM optimiert werden. Sie werden immer einen Stapelüberlauf mit etwas wie diese: 

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

Sie müssen bedenken, dass zu tief Rekursion verwendet man in Stack-Überlauf laufen wird, auf den erlaubten Stapelgröße abhängig. Um dies zu verhindern genügend Basisfall zu schaffen, die endet Sie Rekursion.

Rekursion hat den Nachteil, dass der Algorithmus, die Sie Rekursion O (n) Speicherkomplexität mit Schreib hat. Während iterativer aproach eine Speicherkomplexität von O (1) hat .Diese ist die advantange Iteration über Rekursion zu verwenden. Warum verwenden wir Rekursion?

Siehe unten.

Manchmal ist es einfacher, einen Algorithmus mit Rekursion zu schreiben, während es etwas härter ist, den gleichen Algorithmus, diesen Fall mit iteration.In zu schreiben, wenn Sie sich entscheiden, der Iteration Ansatz zu folgen, würden Sie sich selbst behandeln müssen stapeln.

Soweit ich weiß, Perl optimiert nicht tail-rekursive Aufrufe, aber man kann fälschen. 

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

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

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

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

  }
}

Wenn es zuerst genannt Platz auf dem Stapel zuteilen wird. Dann wird er seine Argumente ändern, und das Unterprogramm neu starten, ohne etwas mehr auf den Stapel zu legen. Es wird daher behaupten, dass es nie seine Selbst genannt, es in einen iterativen Prozess zu verändern.

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

Mit nur Chrome 45.0.2454.85 m, scheint Rekursion eine nette 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 für Schleife unter Verwendung von Standard

100x für Schleifendurchlauf. Benötigte Zeit: 7.683ms

// 100 läuft mit Hilfe der funktionellen rekursive Ansatz w / Endrekursion

100x Rekursion laufen. Benötigte Zeit: 4.841ms

In der Abbildung unten Rekursion gewinnt erneut durch einen größeren Spielraum, wenn sie bei 300 Zyklen pro Testlauf

Wenn die Iterationen Atom und Größenordnungen teurer sind, als einen neuen Stapelrahmen schieben und einen neuen Thread zu schaffen und Sie haben mehrere Kerne und Ihre Laufzeitumgebung können alle von ihnen verwenden, dann eine rekursive Ansatz könnte eine enorme Leistungssteigerung ergeben, wenn sie mit Multithreading kombiniert. Wenn die durchschnittliche Anzahl von Iterationen nicht vorhersehbar ist, dann könnte es eine gute Idee sein, einen Thread-Pool zu verwenden, die Thread Zuweisung steuern und Ihren Prozess verhindert, dass zu viele Threads erstellen und das System hogging.

Zum Beispiel, in einigen Sprachen gibt es rekursive multithreaded Mergesort-Implementierungen.

Aber auch hier Multithreading mit Looping statt Rekursion verwendet werden, so wie gut diese Kombination hängt von mehreren Faktoren ab, einschließlich der OS und der Thread Allokationsmechanismus funktioniert.

Ich werde Ihre Frage beantworten, indem Sie eine Haskell-Datenstruktur durch „Induktion“ entwerfen, die eine Art „dual“ zu Rekursion ist. Und dann werde ich zeigen, wie diese Dualität zu schönen Dingen führt.

Wir stellen einen Typ für einen einfachen Baum: 

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

Wir können diese Definition lesen mit den Worten „Ein Baum ein Zweig ist (enthält zwei Bäume) oder ein Blatt ist (die einen Datenwert enthält)“. So ist das Blatt eine Art Minimalfall. Wenn ein Baum kein Blatt ist, dann muss es eine Verbindung Baum mit zwei Bäumen sein. Dies sind die einzigen Fälle.

Lassen Sie uns einen Baum machen: 

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

Nun, nehmen wir an, wir 1 zu jedem Wert in dem Baum hinzufügen möchten. Wir können dies tun durch den Aufruf: 

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 in der Tat ist eine rekursive Definition. Es nimmt die Daten Bauer Zweig und Blatt als Fälle (und seit Blatt minimal ist und diese sind die einzigen möglichen Fälle), sind wir sicher, dass die Funktion beendet wird.

Was würde es dauern ADDone in einem iterativen Stil zu schreiben? Was wird in eine beliebige Anzahl von Zweigen Looping aus?

Auch kann diese Art von Rekursion oft im Sinne eines „Funktor“ herausgerechnet wird. Wir können Bäume in Funktoren machen durch die Definition: 

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 Rekursion Schemata ausklammern, wie die catamorphism (oder falten) für einen algebraischen Datentyp. Mit Hilfe eines catamorphism, können wir schreiben: 

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

Stack-Überlauf tritt nur dann auf, wenn Sie in einer Sprache sind die Programmierung, die im eingebauten Speicherverwaltung nicht über .... Ansonsten stellen Sie sicher, etwas in Ihrer Funktion (oder einen Funktionsaufruf, STDLbs, etc). Ohne Rekursion sein, es wäre einfach nicht möglich, Dinge zu haben, wie ... Google oder SQL, oder an jedem Ort muss man effizient sortieren durch große Datenstrukturen (Klassen) oder Datenbanken.

Rekursion ist der Weg zu gehen, wenn Sie durch die Dateien zu durchlaufen wollen, ziemlich sicher, das ist, wie ‚gefunden * | ? Grep *‘funktioniert. Kinda Dual Rekursion, vor allem mit dem Rohr (aber nicht über ein Bündel von syscalls tun, wie so viele tun, wenn es alles, was Sie da draußen ablegen werden, für andere zu verwenden).

Höhere Sprachen und sogar Klirren / CPP kann es das gleiche im Hintergrund implementieren.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top