Rekursion vs. Iteration

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

[mkinzler]

@Hagen: Ich glaube, wir haben verstanden, was du meinst.
@Delphi-Laie: wenn du beweisen kannst das iterativ immer besser als rekursiv ist, würdest du dafür vielleicht sogar den Nobelpreis bekommen.

[Daniel]

Ich denke, dass eine Meta-Diskussion über die Diskussion nicht zielführend ist -ebensowenig wie die Frage, ob Windows trotz schnellerer Computer nach wie vor langsam sei. Als Randbemerkung möchte ich die Aussage von Markus vielleicht präzisieren: Es geht nicht darum, wer negaH ist,sondern darum, dass er durch das DEC und unzählige wertvolle und inhaltliche hochwertige Beiträge vielfach unter Beweis gestellt hat, sich im Bereich der theoretischen Informatik bestens auszukennen. Damit hat er nicht pauschal Recht - dieses Privileg habe lediglich ich als Admin *g* - aber wir sind weit über den Punkt hinaus, an dem wir überlegen müssen, ob negaH jemals schon einen rekursiven Algorithmus entwickelt hat.

[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