Rekursion vs. Iteration

[Delphi-Laie]

Zitat:

Zitat von idefix2 (Beitrag 1028134)

Zitat:

Deshalb friemelte ich für alle Klugheitsausscheider mal eben - so auf die Schnelle - ein kleines (natürlich Delphi-)Programm zusammen, das beide Algorithmen bei Fibonacci vergleicht. Ich hoffe, das das Hochladen desselben klappte.

Wie ich in meinem Post 58 geschrieben habe - eine schlechte Implementierung kann für schlechte Performance sorgen, auch bei iterativen Verfahren. Einen untauglich implementierten rekursiven algorithmus mit einem brauchbar implementierten itetrativen Algorithmus zu vergleichen, beweist gar nichts.

In dieser Diskussion finden sich pauschale Äußerungen, daß rekursiv dem Iterativen ebenbürtig ist, und das ist so pauschal eben falsch. Nunmehr wird - von Dir - bei rekursiv zwischen „brauchbar“ und „untauglich implementiert“ unterschieden. Daß der Algorithmus als solcher selbst bzw. an sich ein schlechteres Laufzeitverhalten hat (haben kann), wird auch mit solchen Aussagen umschifft. Wie soll denn ein rekursiver Algorithmus, der auf der Gleichung

fibonacci(n)=fibonacci(n-1)+fibonacci(n-2)

beruht oder aufbaut, „tauglich implementiert“ werden?

[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... :roll:

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:

Zitat von negaH (Beitrag 1028142)

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:

Zitat von negaH (Beitrag 1028083)

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:

Zitat von negaH (Beitrag 1028086)

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

[JasonDX]

Zitat:

Zitat von Delphi-Laie (Beitrag 1028139)

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

Es ist dir bisher nicht gelungen, dies zu begründen. Beide Algorithmen lassen sich sowohl iterativ als auch rekursiv implementieren. Die Schlussfolgerung deines Vergleichs unterliegt aber der Wahl des Algorithmus, nicht der Implementierungsvariante, du ziehst somit die falschen Rückschlüsse daraus.

Zitat:

Zitat von Delphi-Laie (Beitrag 1028139)

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

Du vergleichst also Algorithmen. Wir vergleichen Implementierungen. Du willst uns davon überzeugen, dass ein BMW schneller ist als ein Benz und veranstaltest dafür ein Wettrennen zwischen einem BMW und einem Fahrrad...

Zitat:

Zitat von Delphi-Laie (Beitrag 1028139)

Wie soll denn ein rekursiver Algorithmus, der auf der Gleichung

fibonacci(n)=fibonacci(n-1)+fibonacci(n-2)

„tauglich implementiert“ werden?

Gegenfrage: Wie soll denn ein iterativer Algorithmus, der auf der Gleichung [...] "tauglich implementiert" werden?
Jeder Algorithmus kann iterativ und rekursiv implementiert werden. Und wenn man sich jfheins' rekursive Variante ansieht und die Endrekursion auflöst, kommt man genau auf deine iterative Variante. Sollten bei der Implementierung Performanceunterschiede auftreten, sind diese somit offensichtlich Hardware-bedingt, da die theoretische Äquivalenz beider Implementierungen beweisbar ist.

greetz
Mike

[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

[Khabarakh]

Darf ich mal zusammenfassen, da eine weitere Diskussion wirklich nicht mehr ergiebig scheint :) ?

Besprochen wurden vor allem zwei Algorithmen für die Berechnung der n-ten Fibonacci-Zahl. Der erste leitet sich direkt aus der Definition

Code:

f(n) = f(n-1) + f(n-2); f(0) = 0; f(1) = 1

ab und besitzt eine Laufzeit von Θ(fib(n)) = Θ(1.61...^n) (ja, das Ding hat sich selbst als Laufzeit ;) ). Wenn man an "rekursiver Fibonacci" denkt, dürfte man an dessen Implementierung denken.

Haskell

Code:

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

Da der Algorithmus nicht endrekursiv ist, ist eine iterative Umsetzung nur äußerst umständlich möglich, aber auf jeden Fall machbar und wird genau die gleiche asymptotische Laufzeit ergeben.

Wer aber an "den iterativen Fibonacci" denkt, meint eigentlich einen anderen Algorithmus und eine andere Definition, was auf den letzten Seiten schon mehrmals durch die Birne gesprochen wurde ;) . Beim Namen genannt hat ihn gammatester schon auf Seite 4:

Zitat:

Zitat von gammatester (Beitrag 1027949)

Na Logo, und bei der Gelegenheit kommt man auch sofort auf den viel besseren Algorithmus: [F_{n+1}, F_n] = [[1 1], [1 0]] * [F_n, F_{n-1}]. Es läuft also darauf hinaus, die Potenzen der Matrix A = [[1 1], [1 0]] zu berechnen. Die einfache Iteration berechnet A^n via n-facher Multiplikation und ist O(n), der verbesserte Algo berechnen A^n nach dem binären "Quadriere-und-Multipliziere"-Algorithmus und ist O(log(n)).

Selbst wenn in der fertigen Implementierung keine Matrizen vorkommen, ist der iterative Code viel näher an dieser Definition als an der vorherigen. Und auch wenn sich Iteration wunderbar eignet, um "wiederhole etwas n-mal" umzusetzen, geht das genauso gut rekursiv, wie jfheins gezeigt hat.

Code:

fib n =
   loop n 0 1
   where
      loop 0 x x' = x
      loop n x x' = loop (n-1) x' (x+x')

In imperativen Sprachen sicher weniger üblich, aber besitzt auf jeden Fall ebenso lineare Laufzeit und man spart sich das nervende Variablen-Tauschen ;) . Ein schlauer Compiler wird für beide Implementierungen sowieso genau den gleichen Code erzeugen.

Ich denke, daraus kann man eigentlich nur schlussfolgern, dass beide Vorgehensweisen eine schnelle Implementierung zulassen (wahrscheinlich schnell genug für alle Anwendungen ohne BigInt-Arithmetik, die sowieso andere Laufzeiten erzeugen würde), die Rekursion aber zusätzlich noch ein Verfahren kennt, das mit seiner Laufzeit kaum punkten kann, aber an Einfachheit und Übersichtlichkeit nicht zu schlagen ist.
Und wer mir jetzt noch erzählen will, ich hätte in einer Sprache, die weder Iteration noch Nebeneffekte kennt, nur "teilrekursiven" Code kennt, dem habe ich nichts mehr zu sagen.