Rekursion vs. Iteration

[negaH]

Zitat:

Auch wenn die Rekursion vielleicht sogar in den meisten Fällen eine kurze und elegante Problem(lösungs)beschreibung liefert, so kann dennoch die Algorithmenoptimierung durchaus in einer Beseitigung der Rekursion zu suchen bzw. zu finden sein.

Ja, aber von der Priorität her erst als allerletztes Mittel (Ausnahmen bestätigen die Regel).
Und wie ich vorherig schon beschrieb gibt es nicht nur die schmale Sichtweise auf die ASICs, sondern die Frage "iterativ vs. rekursiv" lässt sich für jede Hardware stellen, zb. auch auf Papier, FPGAs uvm.

Gruß Hagen

[jfheins]

Also was Geschwindigkeitsoptimiereung angeht halte ich mich an diese Rangliste:
(absteigend nach Wichtigkeit)
1. verwendeter Algorithmus
2. Art der Implementierung
3. Programmierspache

=> Wenn man den richtigen Algorithmus wählt, ist die Frage rekursiv/iterativ untergeordnet, solange man es vernüftig macht.

[negaH]

Zitat:

=> Wenn man den richtigen Algorithmus wählt, ist die Frage rekursiv/iterativ untergeordnet...

Aus Sicht der Performance-/Speicherunterschiede. Aber meiner Meinung nach eben nicht aus Sicht der Verständlichkeit und Wartbarkeit.

Gruß Hagen

[gammatester]

Zitat von jfheins:

Wenn man den richtigen Algorithmus wählt, ist die Frage rekursiv/iterativ untergeordnet, solange man es vernüftig macht.

Das ist mM eine leere Ausssage, denn der Algorithmus enthält eine Beschreibung der Lösungsschritte und da steht natürlich drin, ob das ganze rekursiv oder iterativ ist. Wenn dem nicht so wäre, hättest Du eine unvollständige Beschreibung mithin gar keinen keinen Algorithmus.

[jfheins]

Zitat von gammatester:

Zitat von jfheins:

Wenn man den richtigen Algorithmus wählt, ist die Frage rekursiv/iterativ untergeordnet, solange man es vernüftig macht.

Das ist mM eine leere Ausssage, denn der Algorithmus enthält eine Beschreibung der Lösungsschritte und da steht natürlich drin, ob das ganze rekursiv oder iterativ ist. Wenn dem nicht so wäre, hättest Du eine unvollständige Beschreibung mithin gar keinen keinen Algorithmus.

Zitat von Delphi-Laie:

Die Wahl des „richtigen“ (was ist damit konkret gemeint?) Algorithmus besteht doch oft genug in der Entscheidung, ob rekursiv oder iterativ.

Ihr habt mich missverstanden.

Bubblesort kann man Rekursiv oder Iterativ implementieren. (Standardvorgehensweise ist zwar iterativ, aber die äußere Schleife kann man ja auch als rekursion implementieren)
Wenn einem jetzt das Sortieren zu langsam geht, kann man natürlich die Implementierung anpassen, rekursion gegen Iteration testen und gucken was schneller läuft.
Viel mehr Gewinn macht man allerdings, wenn man stattdessen Quicksort, Mergesort, oder sowas hernimmt - ein anderer Algorithmus, der die gleiche Aufgabe in der Regel schneller erledigt.
Die Entscheidung rekursiv vs. iterativ ist für mich noch nicht beim Algorithmus festgelegt. Der sagt vielmehr aus, was wann wie mit welchen daten gemacht wird. Bei Quicksort z.B. "Wähle ein Pivotelement, erstelle zwei Listen mit Einträgen die größer/kleiner sind, sortiere diese Listen ebenfalls und füge am Schluss alles zusammen"

Zitat:

Ich schlage mal folgendes vor: Vergleiche mal die Determinantenberechnung mit Rekursion (nach dem Laplaceschen Entwicklungssatz) mit ihren iterativen Pendants (der schnellste mir bekannte ist der von Le Verrier). Die Komplexität unterscheidet sich zwischen beiden um astronomischen Größenordnungen!

Anderer Algorithmus, anderes Laufzeitverhalten. Das ist so wie wenn ich sage
"Vergleiche mal sie Sortierung einer diskreten Menge per iterativem Bucketsort mit rekursiven Slowsort - Die Komplexität unterscheidet sich zwischen beiden um astronomischen Größenordnungen!"

Zitat:

All' die, dier hier der Rekursion das Wort reden, konnte ich, sofern beide Alternativen (als Rekursion und Iteration oder sogar simpleres) zur Lösung eines Problemes verfügbar sind, noch keine einzigen Fall nennen hören, bei dem die Rekursion hinsichtlich Komplexität die überlegene Lösung darstellt. Ich bin gespannt darauf.

Rekursiver Quicksort ist wesentlich einfacher zu implementieren als die iterative Variante. Damit meine ich nicht das letzte Quäntchen Performance sondern Lesbarkeit und Wartbarkeit.
Oder wenn du einen binären Baum in den verschiedenen Modi (pre-order, in-order, post-order) ausgeben lassen willst.

[negaH]

Zitat:

Meine rekursive Implementierung der Fibonacci-Folge berechnet auch jeden Wert nur einmal. Ich gehe mal davon aus, dass du dich mit Rekursion und funktionaler Programmierung kaum außeinandergesetzt hast, da man schon in den Anfängen über die Konzepte des Tuplings stößt - was zur rekursiven Implementierung von Fibonacci in O(n) führt.

Wenn eine rekursive Variante eine Algos. Werte mehrfach berechnet im Vergleich zur iterative Variante dann existiert ein Unterschied in der Komplexität beider Implementierungen. Ein Unterschied in der Komplexität bedeutet das es unterscheidliche nicht mehr vergleichbare Algorithmen sind. Ergo: Äpfel und Birnen und damit nichts aussagend für den Vergleich "rekursiv vs. iteratv".

Also ganz unabhängig von "funktionaler Programmierung" und "Tupeling".

Gruß Hagen

[mkinzler]

@Hagen, er scheint nicht zu wissen, wer du bist und auch für deine Argumente wenig zugänglich

[negaH]

Und ? Ich poste ja nicht für Ihn sondern für Alle.

PS: mal davon abgesehen bin ich immer für sachliche Gegenargumente offen, denn keiner kann sich jemals 100% sicher sein das sein Wissen vollständig ist. Vielleicht kommt ja ein Experte für Quantencomputer hier vorbei und berichtet von den neusten Erkenntnissen der Mathematik/Informatik und zeigt uns eine neue Sichtweise die unser Wissen vervollständigt.

[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 von gammatester:

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.

[JasonDX]

Zitat von negaH:

Werte mehrfach berechnet im Vergleich zur iterative Variante dann existiert ein Unterschied in der Komplexität beider Implementierungen. Ein Unterschied in der Komplexität bedeutet das es unterscheidliche nicht mehr vergleichbare Algorithmen sind. Ergo: Äpfel und Birnen und damit nichts aussagend für den Vergleich "rekursiv vs. iteratv".

Ja, deshalb habe ich auch den Apfel auf eine Birne abgebildet - nämlich aus der stupiden rekursiven Implementierung, bei der Werte mehrfach berechnet werden, eine Variante, bei der jeder Wert nur einmal berechnet wird. Dieser Algorithmus hat dann rekursiv implementiert die selbe Laufzeit wie DLs iterative Schleife. Ich wollte damit seiner Behauptung, die iterative Implementierung sei besser als die rekursive, begründet widersprechen. Tupling habe ich erwähnt, weil das ein Prinzip ist, mit dem rekursive Funktionen relativ einfach optimiert werden können; Eben bspw. um nicht Werte mehrfach zu berechnen, oder auch um eine endrekursive (keine Ahnung wie das auf Deutsch heißt, tailrecursive jedenfalls ) Berechnung zu bauen.

greetz
Mike