wake-up-neo.com

Warum sollte die Rekursion der Iteration vorgezogen werden?

Iteration ist performanter als Rekursion, oder? Warum meinen manche Leute dann, Rekursion sei besser (in ihren Worten eleganter) als Iteration? Ich verstehe wirklich nicht, warum manche Sprachen wie Haskell keine Iteration zulassen und eine Rekursion fördern? Ist das nicht absurd, etwas zu fördern, das eine schlechte Leistung aufweist (und das auch, wenn eine leistungsfähigere Option, d. H. Eine Rekursion, verfügbar ist)? Bitte beleuchten Sie dies. Vielen Dank.

61
Debashish12

Iteration ist performanter als Rekursion, oder?

Nicht unbedingt. Diese Konzeption stammt aus vielen C-ähnlichen Sprachen, in denen der rekursive oder nicht-rekursive Aufruf einer Funktion einen hohen Aufwand verursachte und für jeden Aufruf ein neues Stackframe erstellte.

Für viele Sprachen ist dies nicht der Fall, und die Rekursion ist mindestens genauso performant wie eine iterative Version. Heutzutage schreiben sogar einige C-Compiler einige rekursive Konstrukte in eine iterative Version um oder verwenden den Stack-Frame für einen rekursiven Tail-Aufruf.

62
nos

Versuchen Sie, die Tiefensuche rekursiv und iterativ zu implementieren, und sagen Sie mir, mit welcher Methode Sie es leichter hatten. Oder sortieren zusammenführen. Bei vielen Problemen kommt es darauf an, Ihren eigenen Stack explizit zu verwalten und Ihre Daten auf dem Funktionsstack zu belassen.

Ich kann nicht mit Haskell sprechen, da ich es nie benutzt habe, aber das ist, um den allgemeineren Teil der in Ihrem Titel gestellten Frage anzusprechen.

36
danben

Haskell lässt keine Iteration zu, da die Iteration einen veränderlichen Zustand (den Index) umfasst.

14
kennytm

Wie andere gesagt haben, ist Rekursion an sich nicht weniger performant. Es gibt einige Sprachen, in denen es langsamer sein wird, aber es ist keine universelle Regel.

Davon abgesehen ist Rekursion für mich ein Werkzeug, das verwendet werden kann, wenn es Sinn macht. Es gibt einige Algorithmen, die besser als Rekursion dargestellt werden (genauso wie einige besser durch Iteration dargestellt werden).

Ein typisches Beispiel:

fib 0 = 0
fib 1 = 1
fib n = fib(n-1) + fib(n-2)

Ich kann mir keine iterative Lösung vorstellen, die möglicherweise die Absicht klarer machen könnte.

9
RHSeeger

Hier einige Informationen zu den Vor- und Nachteilen von Rekursion und Iteration in c:

http://www.stanford.edu/~blp/writings/clc/recursion-vs-iteration.html

Meistens ist Rekursion für mich manchmal leichter zu verstehen als Iteration.

5
John Boker

Iteration ist nur eine spezielle Form der Rekursion.

4
Don Stewart

Verschiedene Dinge:

  1. Die Iteration ist nicht unbedingt schneller
  2. Die Wurzel allen Übels: Etwas zu ermutigen, nur weil es mäßig schneller sein könnte, ist verfrüht; Es gibt noch andere Überlegungen.
  3. Rekursion kommuniziert oft viel prägnanter und klarer Ihre Absicht
  4. Da der veränderbare Zustand im Allgemeinen vermieden wird, lassen sich funktionale Programmiersprachen leichter überlegen und debuggen, und die Rekursion ist ein Beispiel dafür.
  5. Rekursion benötigt mehr Speicher als Iteration.
4
user24359

Rekursion ist eines der Dinge, die in der Theorie elegant oder effizient erscheinen, in der Praxis jedoch im Allgemeinen weniger effizient sind (es sei denn, der Compiler oder der dynamische Rekompiler ändern die Code-Funktionen. Im Allgemeinen ist alles, was unnötige Unterprogrammaufrufe verursacht, langsamer, insbesondere wenn mehr als ein Argument gepusht/gepoppt wird. Alles, was Sie tun können, um Prozessorzyklen zu entfernen, d. H. Anweisungen, auf denen der Prozessor kauen muss, ist faires Spiel. Compiler können heutzutage einen ziemlich guten Job machen, aber es ist immer gut zu wissen, wie man effizienten Code von Hand schreibt.

3
hjorgan

Es fällt mir schwer zu sagen, dass einer die ganze Zeit über besser ist als der andere.

Ich arbeite an einer mobilen App, die Hintergrundarbeiten am Benutzerdateisystem ausführen muss. Einer der Hintergrund-Threads muss von Zeit zu Zeit das gesamte Dateisystem durchsuchen, um aktualisierte Daten für den Benutzer zu erhalten. Aus Angst vor Stack Overflow hatte ich einen iterativen Algorithmus geschrieben. Heute habe ich eine rekursive für den gleichen Job geschrieben. Zu meiner Überraschung ist der iterative Algorithmus schneller: rekursiv -> 37s, iterativ -> 34s (bei genau derselben Dateistruktur).

rekursiv:

private long recursive(File rootFile, long counter) {
            long duration = 0;
            sendScanUpdateSignal(rootFile.getAbsolutePath());
            if(rootFile.isDirectory()) {
                File[] files = getChildren(rootFile, MUSIC_FILE_FILTER);
                for(int i = 0; i < files.length; i++) {
                    duration += recursive(files[i], counter);
                }
                if(duration != 0) {
                    dhm.put(rootFile.getAbsolutePath(), duration);
                    updateDurationInUI(rootFile.getAbsolutePath(), duration);
                }   
            }
            else if(!rootFile.isDirectory() && checkExtension(rootFile.getAbsolutePath())) {
                duration = getDuration(rootFile);
                dhm.put(rootFile.getAbsolutePath(), getDuration(rootFile));
                updateDurationInUI(rootFile.getAbsolutePath(), duration);
            }  
            return counter + duration;
        }

Iterativ: - iterative Tiefensuche mit rekursivem Backtracking

private void traversal(File file) {
            int pointer = 0;
            File[] files;
            boolean hadMusic = false;
            long parentTimeCounter = 0;
            while(file != null) {
                sendScanUpdateSignal(file.getAbsolutePath());
                try {
                    Thread.sleep(Constants.THREADS_SLEEP_CONSTANTS.TRAVERSAL);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }

                files = getChildren(file, MUSIC_FILE_FILTER);

                if(!file.isDirectory() && checkExtension(file.getAbsolutePath())) {
                    hadMusic = true;
                    long duration = getDuration(file);
                    parentTimeCounter = parentTimeCounter + duration;
                    dhm.put(file.getAbsolutePath(), duration);
                    updateDurationInUI(file.getAbsolutePath(), duration);
                }

                if(files != null && pointer < files.length) {
                    file = getChildren(file,MUSIC_FILE_FILTER)[pointer];
                }
                else if(files != null && pointer+1 < files.length) {
                    file = files[pointer+1];
                    pointer++;
                }
                else {
                    pointer=0;
                    file = getNextSybling(file, hadMusic, parentTimeCounter);
                    hadMusic = false;
                    parentTimeCounter = 0;
                }
            }
        }

private File getNextSybling(File file, boolean hadMusic, long timeCounter) {
            File result= null;
            //se o file é /mnt, para
            if(file.getAbsolutePath().compareTo(userSDBasePointer.getParentFile().getAbsolutePath()) == 0) {
                return result;
            }
            File parent = file.getParentFile();
            long parentDuration = 0;
            if(hadMusic) { 
                if(dhm.containsKey(parent.getAbsolutePath())) {
                    long savedValue = dhm.get(parent.getAbsolutePath());
                    parentDuration = savedValue + timeCounter;
                }
                else {
                    parentDuration = timeCounter; 
                }
                dhm.put(parent.getAbsolutePath(), parentDuration);
                updateDurationInUI(parent.getAbsolutePath(), parentDuration);
            }

            //procura irmao seguinte
            File[] syblings = getChildren(parent,MUSIC_FILE_FILTER);
            for(int i = 0; i < syblings.length; i++) {
                if(syblings[i].getAbsolutePath().compareTo(file.getAbsolutePath())==0) {
                    if(i+1 < syblings.length) {
                        result = syblings[i+1];
                    }
                    break;
                }
            }
            //backtracking - adiciona pai, se tiver filhos musica
            if(result == null) {
                result = getNextSybling(parent, hadMusic, parentDuration);
            }
            return result;
        }

Sicher, die Iteration ist nicht elegant, aber obwohl sie derzeit nur unzureichend implementiert ist, ist sie immer noch schneller als die rekursive. Und ich habe eine bessere Kontrolle darüber, da ich nicht möchte, dass es mit voller Geschwindigkeit läuft und der Müllsammler seine Arbeit häufiger erledigen kann.

Wie auch immer, ich nehme nicht an, dass eine Methode besser ist als die andere, und werde andere Algorithmen überprüfen, die derzeit rekursiv sind. Aber zumindest von den beiden obigen Algorithmen ist der iterative derjenige im Endprodukt.

2
jfv

Ich glaube nicht, dass Rekursion an sich weniger performant ist - zumindest nicht abstrakt. Rekursion ist eine spezielle Form der Iteration. Wenn eine Sprache so konzipiert ist, dass sie die Rekursion gut unterstützt, ist es möglich, dass sie genauso gut wie die Iteration funktioniert.

Im Allgemeinen lässt eine Rekursion den Zustand, den Sie in der nächsten Iteration vortragen, explizit erkennen (es sind die Parameter). Dies kann es Sprachprozessoren erleichtern, die Ausführung zu parallelisieren. Zumindest versuchen Sprachdesigner, diese Richtung auszunutzen.

2
Michael Burr

In Java übertreffen rekursive Lösungen im Allgemeinen nicht rekursive. In C ist es eher umgekehrt. Ich denke, dass dies im Allgemeinen für adaptiv kompilierte Sprachen im Vergleich zu vorzeitig kompilierten Sprachen gilt.

Edit: Mit "allgemein" meine ich so etwas wie einen 60/40 Split. Es hängt sehr davon ab, wie effizient die Sprache Methodenaufrufe verarbeitet. Ich denke, dass die JIT-Kompilierung die Rekursion begünstigt, da sie festlegen kann, wie Inlining behandelt und Laufzeitdaten bei der Optimierung verwendet werden. Es ist jedoch sehr abhängig von dem fraglichen Algorithmus und Compiler. Java behandelt Rekursionen immer intelligenter.

Quantitative Studienergebnisse mit Java (PDF link) . Beachten Sie, dass es sich hauptsächlich um Sortieralgorithmen handelt und dass ältere Java= Virtual verwendet werden Computer (1.5.x, wenn ich richtig gelesen habe). Durch die Verwendung der rekursiven Implementierung erzielen sie manchmal eine Leistungsverbesserung von 2: 1 oder 4: 1, und selten ist die Rekursion erheblich langsamer. Nach meiner persönlichen Erfahrung ist der Unterschied nicht oft so ausgeprägt, aber eine 50% ige Verbesserung ist häufig, wenn ich die Rekursion vernünftig verwende.

2
BobMcGee

Ich würde Rekursion mit einem Sprengstoff vergleichen: Sie können in kürzester Zeit ein großes Ergebnis erzielen. Wenn Sie es jedoch ohne Vorsicht verwenden, kann das katastrophale Folgen haben.

Es hat mich sehr beeindruckt, wie komplex die Rekursion ist, mit der Fibonacci-Zahlen berechnet werden hier . In diesem Fall hat die Rekursion die Komplexität O ((3/2) ^ n), während die Iteration nur O (n) ist. Die Berechnung von n = 46 mit Rekursion auf c # dauert eine halbe Minute! Beeindruckend...

IMHO-Rekursion sollte nur verwendet werden, wenn die Art der Entitäten für die Rekursion gut geeignet ist (Bäume, Syntaxanalyse, ...) und niemals aus ästhetischen Gründen. Die Leistung und der Ressourcenverbrauch von "göttlichem" rekursivem Code müssen überprüft werden.

1
ivan_d

Ich denke, es würde helfen, ein Verständnis dafür zu bekommen, worum es bei der Leistung wirklich geht. Dieser Link zeigt, wie viel Optimierungsspielraum eine perfekt vernünftig codierte App tatsächlich bietet - und zwar um den Faktor 43! Nichts davon hatte etwas mit Iteration oder Rekursion zu tun.

Wenn eine App so weit optimiert wurde , wird der Punkt erreicht, an dem die durch die Iteration gespeicherten Zyklen im Gegensatz zur Rekursion tatsächlich einen Unterschied bewirken können.

1
Mike Dunlavey

Als Low Level befasst sich ITERATION mit der CX-Registrierung, um Schleifen und natürlich Datenregister zu zählen. RECURSION behandelt nicht nur das, sondern fügt auch Verweise auf den Stapelzeiger hinzu, um Verweise auf die vorherigen Aufrufe zu speichern und dann zurückzugehen.-

Mein Universitätslehrer sagte mir, dass alles, was Sie mit Rekursion machen, mit Iterationen und Umkehrungen gemacht werden kann. Manchmal ist es jedoch einfacher, es durch Rekursion zu machen als mit Iteration (eleganter), aber auf einem Leistungsniveau ist es besser, Iterationen zu benutzen.

1
MRFerocius

Rekursion ist die typische Implementierung von Iteration. Es ist nur eine niedrigere Abstraktionsebene (zumindest in Python):

class iterator(object):
    def __init__(self, max):
        self.count = 0
        self.max = max

    def __iter__(self):
        return self

    # I believe this changes to __next__ in Python 3000
    def next(self):
        if self.count == self.max:
            raise StopIteration
        else:
            self.count += 1
            return self.count - 1

# At this level, iteration is the name of the game, but
# in the implementation, recursion is clearly what's happening.
for i in iterator(50):
    print(i)
1
orokusaki

"Iteration ist performanter als Rekursion" ist wirklich sprach- und/oder compilerspezifisch. Der Fall, der in den Sinn kommt, ist, wenn der Compiler eine Schleife abwickelt. Wenn Sie in diesem Fall eine rekursive Lösung implementiert haben, wird diese etwas langsamer.

Hier lohnt es sich, Wissenschaftler zu sein (Hypothesen testen) und Ihre Werkzeuge zu kennen ...

0
Austin Salonen

Iteration ist performanter als Rekursion, oder?

Ja.

Wenn Sie ein Problem haben, das einer rekursiven Datenstruktur perfekt zugeordnet ist, ist die bessere Lösung immer rekursiv.

Wenn Sie so tun, als würden Sie das Problem mit Iterationen lösen, werden Sie den Stapel am Ende neu erfinden und einen chaotischeren und hässlicheren erstellen Code, verglichen mit der elegant rekursiven Version des Codes.

Das heißt, Iteration wird immer schneller sein als Rekursion . (in einer Von Neumann-Architektur). Wenn Sie also immer eine Rekursion verwenden, selbst wenn eine Schleife ausreicht, zahlen Sie eine Leistungsstrafe.

Ist Rekursion jemals schneller als Schleifen?

0
Lucio M. Tato