Rekursion vs. Iteration

[negaH]

Zitat:

In dieser Diskussion finden sich pauschale Äußerungen, daß rekursiv dem Iterativen ebenbürtig ist, und das ist so pauschal eben falsch.

Dann beweise das bitte. Ich behaupte das es da keinen Unterschied geben darf und wird aus Sicht des Resultates wenn man einen fairen Vergleich anstellt.

Es unterscheidet sich ausschließlich nur die Schreibweise im Quelltext. Es verbleiben nur noch konstruktiv die Argumente, was ist verständlicher und damit wartbarer.

Gruß Hagen

[Mithrandir]

Leude...

Meint ihr nicht, ihr habts langsam? Ich dreht euch dauernd im Kreis, seit mindestens 6 Seiten. Wenn ihr Bock darauf habt, tausch euch per PN aus und postet das Resultat hier. So kommt ihr jedenfalls kein Stückchen weiter.

[Delphi-Laie]

Zitat von negaH:

Zitat:

In dieser Diskussion finden sich pauschale Äußerungen, daß rekursiv dem Iterativen ebenbürtig ist, und das ist so pauschal eben falsch.

Dann beweise das bitte. Ich behaupte das es da keinen Unterschied geben darf und wird aus Sicht des Resultates wenn man einen fairen Vergleich anstellt.

Gern, und zwar ohne daß ich Sätze mehr verstümmele, als diese zu zitieren:

Zitat von negaH:

Der einzige Grund warum eine rekursive Lösung unter Umständen einen leichten Performance-/Speicheroverhead hat liegt
in der Rechnerarchitektur begründet, ansonsten wird es zwischen beiden keinen Unterschied geben.

Zitat von negaH:

Es gibt keinen Überlegenen, iterativ vs. rekursiv sind identisch und erst die Fähigkeiten der Hardware macht einen Unterschied. Aber dieser ist eben oft nur marginal im Speicher wie Performancebereich, ansonsten bleibt die Komplexität des Algos. erhalten, egal ob rekursiv/iterativ. Alle weiteren Tricks lassen sich dann rekursiv wie auch iterativ anwenden da es Tricks zur Verbesserung der Komplexität des Algos. sind.

[negaH]

Und wo siehst Du jetzt eine Diskrepanz ?

Gruß Hagen

[hitzi]

Delphi-Laie, vielleicht hilft dir ein bildlicher Vergleich deinen Fehler zu erkennen.

Rekursion = vorwärts laufen
Iteration = rückwärts laufen

Aufgabe: Laufe von A nach B

Vorwärts, wie auch rückwärts ist die Strecke bei idealen Bedingungen in gleicher Zeit zu schaffen. Nur die verwendete Hardware (zu Fuss, mit dem Auto, was auch immer) kann einen zeitlichen Unterschied ausmachen.

Bei deinen Vergleichen läufst du vorwärts(rekursiv) von A nach B, aber rückwärts nimmst du eine Abkürzung (andere Algorithmus) und bist eben rückwärts(iterativ) schneller am Ziel.

[idefix2]

Zitat:

Allerdings ist dieser Algorithmus - im Vergleich zur „vollrekursiven“ Variante - teilweise „entrekursiviert“

Was soll das heissen? rekursiv bedeutet doch nicht, dass man bereits vorhandene Ergebnisse ignorieren und bereits erfolgte Rechenschritte jedesmal von neuem machen muss.
Die Berechnung erfolgt in der rekursiven Variante 100% rekursiv, aber selbstverständlich wird eine vernünftige Implementierung JEDES Algorithmus auf bereits vorhandene Ergebnisse zurückgreifen und die nicht neuerlich berechnen, und das gilt natürlich genauso für iterative Verfahren.

Zitat:

Die originale rekursive Definition der Fibonaccigliederberechnung findet sich dort jedenfalls nicht mehr.

Die findet sich bei der Initialisierung des Feldes: Feld[0] := 0. Feld[1] := 1. Damit werden die Anfangswerte sowohl für das iterative als auch für das rekursive Verfahren gesetzt, und ich erspare mir in beiden Funktionen die Abfrage auf Sonderwerte.

Zitat:

Nunmehr wird - von Dir - bei rekursiv zwischen „brauchbar“ und „untauglich implementiert“ unterschieden. Wie soll denn ein rekursiver Algorithmus, der auf der Gleichung
fibonacci(n)=fibonacci(n-1)+fibonacci(n-2)
beruht oder aufbaut, „tauglich implementiert“ werden?

Das Ergebnis (stark ansteigende Laufzeit) beweist eben, dass die Implementierung untauglich ist. Wenn Du die berechneten Zwischenergebnisse speicherst, und direkt abrufst, falls es sie schon gibt, hast Du aus der untauglichen Implementierung eine taugliche Implementierung des GENAU GLEICHEN Algorithmus gemacht. Diese taugliche Implementierung ist dann im wesentlichen gleich schnell wie ein tauglich implementiertes iteratives Verfahren, und sicher viel schneller, als wennn Du in das iterative Verfahren irgend einen unnötigen Unfug einbaust, der die Laufzeit hinaufschnellen lässt.

Zitat:

Daß der Algorithmus als solcher selbst bzw. an sich ein schlechteres Laufzeitverhalten hat (haben kann), wird auch mit solchen Aussagen umschifft.

Nicht der Algorithmus hat das schlechtere Laufzeitverhalten, sondern eben Deine Implementierung. Sobald der Designfehler bei der Implementierung korrigiert ist, ist das Laufzeitverhalten gleich gut.

[negaH]

Zitat:

Du vergleichst also Algorithmen. Wir vergleichen Implementierungen.

Noch nichtmal das, wir vergleichen erstmal nur unterschiedliche Schreibweisen ein und der selben Sache.

Gruß Hagen