Rekursion gegen Iteration

Ist es korrekt zu sagen, dass überall, wo recursion wird, eine For-Schleife verwendet werden könnte? Und wenn die Rekursion normalerweise langsamer ist, was ist der technische Grund dafür, sie jemals für die Iteration zu verwenden?

Und wenn es immer möglich ist, eine Rekursion in eine for-Schleife umzuwandeln, gibt es eine Faustregel dafür?

Solutions Collecting From Web of "Rekursion gegen Iteration"

Rekursion ist normalerweise viel langsamer, da alle functionsaufrufe in einem Stapel gespeichert werden müssen, um die Rückkehr zu den functionen des Aufrufers zu ermöglichen. In vielen Fällen muss Speicher zugewiesen und kopiert werden, um die Bereichsisolation zu implementieren.

Einige Optimierungen, wie die Optimierung von Endanrufen , machen Rekursionen schneller, sind jedoch nicht immer möglich und sind nicht in allen Sprachen implementiert.

Die Hauptgründe für Rekursion sind

  • dass es in vielen Fällen intuitiver ist, wenn es unseren Ansatz des Problems nachahmt
  • dass einige Datenstrukturen wie Bäume einfacher durch Rekursion erkundet werden können (oder in jedem Fall Stapel benötigen)

Natürlich kann jede Rekursion als eine Art Schleife modelliert werden: das wird die CPU letztendlich tun. Und die Rekursion selbst bedeutet direkter, die functionsaufrufe und Bereiche in einen Stapel zu setzen. Wenn Sie jedoch Ihren rekursiven Algorithmus in einen Looping-process umwandeln, könnte dies viel Arbeit erfordern und Ihren Code weniger wartbar machen: Wie bei jeder Optimierung sollte der Versuch nur dann unternommen werden, wenn ein Profiling oder eine Evidenz gezeigt hat, dass dies notwendig ist.

Ist es korrekt zu sagen, dass überall, wo Rekursion verwendet wird, eine For-Schleife verwendet werden könnte?

Ja, weil die Rekursion in den meisten CPUs mit Schleifen und einer Stack-Datenstruktur modelliert wird.

Und wenn die Rekursion normalerweise langsamer ist, was ist der technische Grund dafür?

Es ist nicht “in der Regel langsamer”: Es ist die Rekursion, die falsch angewendet wird, die langsamer ist. Darüber hinaus sind moderne Compiler in der Lage, einige Rekursionen in Schleifen umzuwandeln, ohne sie zu fragen.

Und wenn es immer möglich ist, eine Rekursion in eine for-Schleife umzuwandeln, gibt es eine Faustregel dafür?

Schreibe iterative Programme für Algorithmen, die am besten verstanden werden, wenn sie iterativ erklärt werden; Schreibe rekursive Programme für Algorithmen, die am besten rekursiv erklärt werden.

Beispielsweise wird das Durchsuchen von Binärbäumen, das Ausführen von Quicksort und das Analysieren von Ausdrücken in vielen Programmiersprachen häufig rekursiv erläutert. Diese werden am besten rekursiv codiert. Auf der anderen Seite sind Rechenfaktoren und die Berechnung von Fibonacci-Zahlen viel einfacher in Bezug auf Iterationen zu erklären. Rekursion für sie ist wie Fliegen mit einem Vorschlaghammer schwingen: Es ist keine gute Idee, auch wenn der Vorschlaghammer macht einen wirklich guten Job bei + .


+ Ich entlehnte die Vorschlaghammer-Analogie aus Dijkstras “Discipline of Programming”.

Frage:

Und wenn die Rekursion normalerweise langsamer ist, was ist der technische Grund dafür, sie jemals für die Iteration zu verwenden?

Antworten :

Weil es in einigen Algorithmen schwierig ist, es iterativ zu lösen. Versuchen Sie, die Tiefensuche sowohl rekursiv als auch iterativ zu lösen. Sie werden die Idee bekommen, dass es schwierig ist, DFS mit Iteration zu lösen.

Eine weitere gute Sache, um es auszuprobieren: Versuchen Sie Merge iterativ zu schreiben. Es wird einige Zeit dauern.

Frage:

Ist es korrekt zu sagen, dass überall, wo Rekursion verwendet wird, eine For-Schleife verwendet werden könnte?

Antworten :

Ja. Dieser Thread hat dafür eine sehr gute Antwort.

Frage:

Und wenn es immer möglich ist, eine Rekursion in eine for-Schleife umzuwandeln, gibt es eine Faustregel dafür?

Antworten :

Vertrau mir. Versuchen Sie, Ihre eigene Version zu schreiben, um die Tiefensuche iterativ zu lösen. Sie werden feststellen, dass einige Probleme einfacher rekursiv getriggers werden können.

Hinweis: Rekursion ist gut, wenn Sie ein Problem lösen, das durch die Divide-and-Conquer- Technik getriggers werden kann.

Abgesehen davon, dass die Rekursion langsamer ist, kann sie auch Stapelüberlauferrors verursachen, je nachdem wie tief sie geht.

Um eine äquivalente Methode mit Iteration zu schreiben, müssen wir explizit einen Stack verwenden. Die Tatsache, dass die iterative Version einen Stack für ihre Lösung benötigt, zeigt an, dass das Problem so schwierig ist, dass es von der Rekursion profitieren kann. Als eine allgemeine Regel ist Rekursion am besten für Probleme geeignet, die nicht mit einer festen Menge an Speicher getriggers werden können und folglich einen Stapel benötigen, wenn sie iterativ getriggers werden. Allerdings können Rekursion und Iteration das gleiche Ergebnis zeigen, während sie einem anderen Muster folgen. Um zu entscheiden, welche Methode besser funktioniert, ist von Fall zu Fall und Best Practice zu wählen, basierend auf dem Muster, dem das Problem folgt.

Zum Beispiel, um die n-te Dreieckszahl der Dreiecksfolge zu finden: 1 3 6 10 15 … Ein Programm, das einen iterativen Algorithmus verwendet, um die n-te Dreieckszahl zu finden:

Verwenden eines iterativen Algorithmus:

 //Triangular.java import java.util.*; class Triangular { public static int iterativeTriangular(int n) { int sum = 0; for (int i = 1; i < = n; i ++) sum += i; return sum; } public static void main(String args[]) { Scanner stdin = new Scanner(System.in); System.out.print("Please enter a number: "); int n = stdin.nextInt(); System.out.println("The " + n + "-th triangular number is: " + iterativeTriangular(n)); } }//enter code here 

Verwenden eines rekursiven Algorithmus:

 //Triangular.java import java.util.*; class Triangular { public static int recursiveTriangular(int n) { if (n == 1) return 1; return recursiveTriangular(n-1) + n; } public static void main(String args[]) { Scanner stdin = new Scanner(System.in); System.out.print("Please enter a number: "); int n = stdin.nextInt(); System.out.println("The " + n + "-th triangular number is: " + recursiveTriangular(n)); } } 

Die meisten Antworten scheinen das iterative = for loop anzunehmen. Wenn Ihre for-Schleife unbeschränkt ist ( a la C, können Sie mit Ihrem Loop-Zähler alles machen, was Sie wollen), dann ist das korrekt. Wenn es sich um eine echte for Schleife handelt (wie in Python oder den meisten funktionalen Sprachen, in denen Sie den Schleifenzähler nicht manuell ändern können), ist das nicht korrekt.

Alle (berechenbaren) functionen können sowohl rekursiv als auch mit while Schleifen (oder konditionellen Sprüngen, die im Grunde die gleiche Sache sind) implementiert werden. Wenn Sie sich wirklich auf for loops , erhalten Sie nur eine Teilmenge dieser functionen (die primitiven rekursiven, wenn Ihre elementaren Operationen sinnvoll sind). Zugegeben, es ist eine ziemlich große Teilmenge, die zufällig jede einzelne function enthält, die Sie wahrscheinlich in der Praxis finden werden.

Was viel wichtiger ist, ist, dass viele functionen sehr einfach rekursiv zu implementieren sind und iterativ schwer zu implementieren sind (manuelle Verwaltung Ihrer Call-Stacks zählt nicht).

Ich erinnere mich, dass mein Informatikprofessor damals sagte, dass alle Probleme, die rekursive Lösungen haben, auch iterative Lösungen haben. Er sagt, dass eine rekursive Lösung in der Regel langsamer ist, aber sie wird häufig verwendet, wenn sie einfacher zu rezeptieren und zu programmieren sind als iterative Lösungen.

Im Falle von fortgeschritteneren rekursiven Lösungen glaube ich jedoch nicht, dass es immer in der Lage sein wird, sie unter Verwendung einer einfachen for Schleife zu implementieren.

Ja, wie von Thanakron Tandavas gesagt ,

Rekursion ist gut, wenn Sie ein Problem lösen, das durch Divide and Conquer-Technik getriggers werden kann.

Zum Beispiel: Türme von Hanoi

  1. N-Ringe in zunehmender Größe
  2. 3 Stangen
  3. Die Ringe beginnen auf der Pole 1 gestapelt. Ziel ist es, Ringe zu bewegen, so dass sie auf der Pole 3 gestapelt sind … Aber
    • Kann nur jeweils einen Ring bewegen.
    • Kann keinen größeren Ring auf kleinere setzen.
  4. Iterative Lösung ist “mächtig, aber hässlich”; rekursive Lösung ist “elegant”.

Rekursion + Memorisierung könnte zu einer effizienteren Lösung im Vergleich zu einem reinen iterativen Ansatz führen, z. B. dies überprüfen: http://jsperf.com/fibonacci-memoized-v–iterative-for-large-n

Kurze Antwort: Der Kompromiss besteht darin, dass Rekursion schneller ist und For-Schleifen in fast allen Fällen weniger Speicher belegen. Es gibt jedoch normalerweise Möglichkeiten, die for-Schleife oder Rekursion zu ändern, damit sie schneller ausgeführt wird