Rekursion vs. Iteration

[alzaimar]

Ich verstehe die kleinliche Rechthaberdiskussion nicht, bei der man die Integrität von Diskussionsteilnehmern in Frage stellt.

Mein Bauch sagt mir zwar, das man so ziemlich jedes Verfahren sowohl rekursiv als auch iterativ formulieren kann. Aber wenn nicht: WTF.

Ich bin und bleibe Anhänger der Rekursion und setze sie immer ein, wobei ich Tail-Recursion und hohe Verschachtelungstiefen vermeide. Natürlich schaue ich mir jede Lösung hinsichtlich ihres Big-Oh-Verhaltens kritisch an, und würde daher z.B. eine unsinnige Fibionacci-Implementierung, wie vom Gammatester süffisant vorgetragen, vermeiden.

Wenn ich mir die rekursiven Lösungen zum Türme-Von-Hanoi-Problem anschaue, oder die Ermittlung von Permutationen, oder eine Lösung des N-Damen-Problems, dann verstehe ich nicht, wie man iterative Lösungen per se bevorzugen kann.

Und wenn ich eine iterative Berechnung der Fakultät oder der Fibionacci-Folge sehe, verstehe ich auch nicht, wie man rekursive Lösungen per se bevorzugen kann.

[Delphi-Laie]

Zitat von alzaimar:

eine unsinnige Fibionacci-Implementierung, wie vom Gammatester süffisant vorgetragen, vermeiden.

Warum unsinnig? Sie orientiert sich lediglich an der rekursiven mathematischen Definition und dürfte wohl all' das, was zugunsten der Rekursion hier ins Felde geführt wurde, wie Übersichtlichkeit und Einfachheit und womöglich einen mathematischen Exaktheitsbeweis im Nacken, in vollem Umfange aufweisen.

Zitat von alzaimar:

Und wenn ich eine iterative Berechnung der Fakultät oder der Fibionacci-Folge sehe, verstehe ich auch nicht, wie man rekursive Lösungen per se bevorzugen kann.

Interessant ist - obwohl ich sie nicht gern zitiere - daß in der Wikipedia für die Endrekursion auch das Synonym „iterativ rekursiv“ benutzt wird. Sie scheint ein merkwürdiges Hybrid-/Übergangswesen zwischen der „klassischen“ / „echten“ Rekursion und der Iteration zu sein. Wer das eine will, muß das andere mögen. Rekursion (teilweise) abzuspecken, führt letztlich (teilweise) wieder zu der hier anscheinend von vielen verpönten Iteration. Doch taugt eine „Rekursion light“ keinesfalls als Nachweis dafür, daß sie vom Laufzeitverhalten her generell mit der Iteration mithalten kann.

Der - auch von mir nicht bezweifelte - tendenzielle Vorteil der Rekursion hinsichtlich Übersichtlichkeit und Wartbarkeit sehe ich bei solchen Quelltexten, die anscheinend die endrekursive Variante verkörpern, wie

Code:

private uint fib(uint n)
        {
            if (n == 0)
                return 0;
            else
                return fib(n, 1, 0);
        }

        private uint fib(uint n, uint x, uint y)
        {
            if (n == 1)
                return x;
            else
                return fib(n - 1, x + y, x);
        }

oder

Code:

function Fibonacci_Rekursiv2(Index : Integer) : Int64;
  function Fibonacci_Rekursiv_Help(f1,f2,n: Integer): Integer;
    begin
      if n = 0 then
        Result:=f1
      else 
        Result:=Fibonacci_Rekursiv_Help(f2,f1+f2,n-1);
    end;
begin
  case Index of
    1, 2 : Result := 1;
    else Result := Fibonacci_Rekursiv_Help(0,1,Index);
  end;
end

leider nicht mehr gegeben: Da sich hier nicht an der rekursiven mathematischen Definition vollumfänglich orientiert wird, muß man sich in so etwas - egal, ob als ursprünglicher Programmierer oder später als Sichter des Quelltextes - auch erst einmal genau wie bei Iterationen hineindenken.

[alzaimar]

Zitat von Delphi-Laie:

Doch taugt eine „Rekursion light“ keinesfalls als Nachweis dafür, daß sie vom Laufzeitverhalten her generell mit der Iteration mithalten kann.

Deine Gedankengänge sind für mich nicht nachvollziehbar. Du stehst zudem in deinem Bestreben, Äpfel generell über Birnen zu stellen, ziemlich allein. Erstens gibt es Birnenliebhaber und zweites faule Äpfel. Das haut also nicht hin.

Die Tailrecursion ist Rekursion. Punkt. Sie sollte aber durch eine Schleife ersetzt werden, weil das einfach einfacher zu verstehen ist. Punkt. Das das nebenbei auch noch performanter ist, liegt an der Tatsache, das eine Schleife nun mal schneller ist. Hier ist naturgemäß eine Umformung in eine Iteration die richtige Wahl.

Eine andere Technik der Umformung (rekursiv => iterativ), Bookkeeping eines Stacks vs. rekursivem Aufruf und Stack ist dagegen nicht notwendigerweise performanter.

Ich habe vor einiger Zeit mal wieder ein iterstives mit einem rekursiven Quicksort verglichen: Da gibt es einfach keine relevanten Unterschiede mehr.

Wer allerdings einen Floodfill rekursiv implementiert, muss sich nicht wundern, wenn die Performance in den Keller geht.

Man muss einfach, wie bei allen Implementierungen, seinen gesunden Menschenverstand einsetzen, um die richtige Lösung zu finden. Dogmen á la "rekursiv ist eh zu langsam" sind hier nicht zielführend, übrigens genauso wenig wie "Eleganz ist alles".

Vor lauter Performancegeilheit darf man auch nicht vergessen, das es fast immer völlig egal ist, ob eine Anwendung 5 oder 5.02 Minuten benötigt. Viel wichtiger ist es mittlerweile, das der Code klar und lesbar ist. Lesbarer Code ist wartbar. Wartbarer Code ist zukunftssicher. Und zukunftssicherer Code sichert das Geschäft. So einfach ist das. Jedenfalls für mich.

Ich kann mit Aussagen, wie "Rekursion ist per se langsamer als Iteration" nichts anfangen. Denn es ist Quatsch.

[Delphi-Laie]

Zitat von alzaimar:

Ich kann mit Aussagen, wie "Rekursion ist per se langsamer als Iteration" nichts anfangen. Denn es ist Quatsch.

Natürlich. So pauschal eine solche Aussage ist, so falsch ist sie auch.

Mich würde in diesem Zusammenhang allerdings einmal interessieren, ob bei Problemlösungen, die sowohl iterativ als auch rekursiv möglich sind, es auch Fälle gibt, in denen die Rekursion hinsichtlich des Laufzeitverhaltens der Iteration substantiell (also vom Komplexitätsverhalten her) überlegen ist. Nachzuweisen, daß eine iterative einer (bestimmten) rekursiven Lösung überlegen ist, bedurfte es ja nur einer Folge, die schon seit dem späten Hochmittelalter (oder frühen Spätmittelalter) bekannt ist.

[jfheins]

Zitat von Delphi-Laie:

Mich würde in diesem Zusammenhang allerdings einmal interessieren, ob bei Problemlösungen, die sowohl iterativ als auch rekursiv möglich sind, es auch Fälle gibt, in denen die Rekursion hinsichtlich des Laufzeitverhaltens der Iteration substantiell (also vom Komplexitätsverhalten her) überlegen ist.

Ist unmöglich, da das Komplexitätsverhalten vom Algorithmus (also der Art der Problemlösung) und nicht von der Implementierung des Algorithmus (rekursiv/iterativ) abhängt. Du meinst schon das mit der Groß-O-Notation, oder? Denn ein rekursiver Quicksort und ein iterativer Quicksort haben beide eine Laufzeit von n*log(n) im Schnitt.

Zitat:

Nachzuweisen, daß eine iterative einer (bestimmten) rekursiven Lösung überlegen ist, bedurfte es ja nur einer Folge, die schon seit dem späten Hochmittelalter (oder frühen Spätmittelalter) bekannt ist.

Das "nachzuweisen" ist trivial.

Als Gegenbeispiel führe ich mal die Türme von Hanoi an: http://de.wikipedia.org/wiki/Türme_v...er_Algorithmus
Die rekursive Implementierung ist deutlich besser verständlich als die iterative. Beide haben natürlich das gleiche exponentielle Laufzeitverhalten.

Noch ein bereits genanntes Gegenbeispiel: Rekursiver Quicksort vs. iterativer Bubblesort. Sind ja beides Lösungen für das Sortierproblem - aber die rekursive Implementierung der Lösung ist deutlich schneller im Average Case

[Delphi-Laie]

Zitat von jfheins:

Zitat von Delphi-Laie:

Mich würde in diesem Zusammenhang allerdings einmal interessieren, ob bei Problemlösungen, die sowohl iterativ als auch rekursiv möglich sind, es auch Fälle gibt, in denen die Rekursion hinsichtlich des Laufzeitverhaltens der Iteration substantiell (also vom Komplexitätsverhalten her) überlegen ist.

Ist unmöglich, da das Komplexitätsverhalten vom Algorithmus (also der Art der Problemlösung) und nicht von der Implementierung des Algorithmus (rekursiv/iterativ) abhängt. Du meinst schon das mit der Groß-O-Notation, oder?

Ja.

Zitat von jfheins:

Zitat von Delphi-Laie:

Nachzuweisen, daß eine iterative einer (bestimmten) rekursiven Lösung überlegen ist, bedurfte es ja nur einer Folge, die schon seit dem späten Hochmittelalter (oder frühen Spätmittelalter) bekannt ist.

Das "nachzuweisen" ist trivial.

Als Gegenbeispiel führe ich mal die Türme von Hanoi an: http://de.wikipedia.org/wiki/Türme_v...er_Algorithmus
Die rekursive Implementierung ist deutlich besser verständlich als die iterative. Beide haben natürlich das gleiche exponentielle Laufzeitverhalten.

Ich meinte doch ausdrücklich, ob es eine schnellere rekursive Lösung gibt. Die Verständlichkeit ist unberührt.

Zitat von jfheins:

Noch ein bereits genanntes Gegenbeispiel: Rekursiver Quicksort vs. iterativer Bubblesort. Sind ja beides Lösungen für das Sortierproblem - aber die rekursive Implementierung der Lösung ist deutlich schneller im Average Case

Der Vergleich hinkt m.E. etwas. Es lassen sich zum einen auch rekursive (und auch iterative) Algorithmen finden, die langsamer als Bubblesort sind (Trippelsort, Slowsort), zum anderen gibt es auch iterative Sortieralgorithmen, die von der Geschwindigkeit her dem Quicksort wahrscheinlich mindestens ebenbürtig sind.

[xZise]

Moin,

Zitat von Delphi-Laie:

[...]Der Vergleich hinkt m.E. etwas. Es lassen sich zum einen auch rekursive (und auch iterative) Algorithmen finden, die langsamer als Bubblesort sind (Trippelsort, Slowsort), zum anderen gibt es auch iterative Sortieralgorithmen, die von der Geschwindigkeit her dem Quicksort wahrscheinlich mindestens ebenbürtig sind.

Dann fass dich bitte selber an die Nase: Du kannst einen schlechten rekursiv implementierten Algorithmus für die Fibonacci-Folge nicht mit einen optimierten iterativen Algorithmus vergleichen.

Das fib(n) := fib(n - 1) + fib(n - 2) nicht das beste Laufzeitverhalten hat, das hast du ja demonstriert, aber es gibt rekursive Implementierungen die sind so gut wie die iterativen. Ob das nun die ursprüngliche mathematische Definition ist, ist doch irrelevant, ob die rekursive Implementierung gut ist.

Und warum muss der rekursive Algorithmus unbedingt schneller sein? Solange sie gleich schnell sind passt das doch? Weil dann ist eine rekursive Implementierung meistens besser lesbar.

MfG
Fabian

[jfheins]

Zitat von Delphi-Laie:

Ich meinte doch ausdrücklich, ob es eine schnellere rekursive Lösung gibt. Die Verständlichkeit ist unberührt.

Wir drehen uns im Kreis

Bei Fibonacci habe ich dir eine rekursive Implementierung mit gleicher Komplexität gezeigt, die du wegen der verringerten Verständlichkeit (zu recht) abgelehnt hast. (Fibonacci ist eben ein Problem, dass man am besten per iteration löst)
Bei den Türmen von Hanoi habe ich dir gezeigt, dass rekursive Implementierungen bei gleicher Komplexität übersichtlicher sein können. Und du bestehst auf einer schnelleren Lösung ... schon die Entwicklung der iterativen Lösung die du jetzt nur auf Wikipedia angeguckt hast, hat wahrscheinlich Tage wenn nicht gar Wochen gebraucht, während die rekursive Variante schnell hingeschrieben ist.

[mkinzler]

Zitat:

Wir drehen uns im Kreis

Wir sind sozusagen Derwische

[Mithrandir]

Zitat von jfheins:

Wir drehen uns im Kreis

Das hab ich euch schon vor 15 Beiträgen versucht klar zu machen...