Rekursion vs. Iteration

[Delphi-Laie]

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.

Ganz bestimmt nicht. Die Komplexität bzw. Effizienz von Algorithmen hat zunächst einmal überhaupt nichts mit ihrer Umsetzung zu tun.

Außerdem wurde mit der rekursiven Berechnung irgendeines Gliedes der Fibonacci-Folge diese pauschale Lobhudelei der Rekursion bereits widerlegt, denn dort wird jeder Zwischenwert doppelt, dreimal oder noch (viel) häufiger berechnet.

[negaH]

Zitat von Delphi-Laie:

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.

Ganz bestimmt nicht. Die Komplexität bzw. Effizienz von Algorithmen hat zunächst einmal überhaupt nichts mit ihrer Umsetzung zu tun.

Korrekt, du verstehst langsam. Aus dieser Sichweise heraus kann man also den Algo. iterativ wie auch rekursiv aufbauen (wenn es eine rekursive Version dafür gibt) ohne das es einen Untrschied in desen Komplexität gibt.

Erst wenn man anfängt diesen Algo. zu implementieren auf einer jeweiligen Hardware wird es nur und ausschließlich nur auf Grund dieser Hardware leichte Unterschiede zu Gunsten der iterativen Lösung geben.

Damit untermauert deine Aussage ja meine

Zitat von Delphi-Laie:

Außerdem wurde mit der rekursiven Berechnung irgendeines Gliedes der Fibonacci-Folge diese pauschale Lobhudelei der Rekursion bereits widerlegt, denn dort wird jeder Zwischenwert doppelt, dreimal oder noch (viel) häufiger berechnet.

Eben nicht. Wo ist da ein Beweis ? wenn man Äpfel mit Birnen vergleicht. Ich warte schon auf dein Argument das ja Windows auf Grund dessen das man dort alles rekursiv gelöst hat immer schlechter wird und jedes denkbare HW-System massiv ausbremst. Kannst du mir sagen woher du eigentlich weißt das die Entwickler bei MS rekursive statt iterative Implementierungen bevorzugen ?

Ich setze dagegen und behaupte das ich Fibonacci zb. auf einem FPGA sowohl iterativ wie rekursiv implementieren könnte und am Ende beides absolut identisch sein muß ! Und dabei bin ich sogar noch so fair und benutze in beiden Fällen als algortihmische Basis auch den gleichen Algorithmus und nicht Äpfel und Birnen, nicht ASIC vs. FPGA usw.

Gruß Hagen

[negaH]

Zitat:

bei dem die Rekursion hinsichtlich Komplexität die überlegene Lösung darstellt. Ich bin gespannt darauf.

Na endlich kommen wir weiter. 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.

Aber in der Verständlichkeit, Wartbarkeit, Definierbarkeit eines Bweweise für dessen Korrektheit gibt es gewaltige Unterschiede.

Gruß Hagen

[negaH]

Es gäbe da ein "Argument" pro Iterativ:

Nämlich das es bestimmte Problemstellung gibt die man nicht rekusiv formulieren kann. Aber das ist am Thema vorbei, da wir davon ausgehen können das ein Vergleich rekursiv vs. iterativ nur dann Sinn macht wenn auch auch vom Problem her beide Möglichkeiten gibt.

Gruß Hagen

[Delphi-Laie]

Zitat von negaH:

Zitat von Delphi-Laie:

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.

Ganz bestimmt nicht. Die Komplexität bzw. Effizienz von Algorithmen hat zunächst einmal überhaupt nichts mit ihrer Umsetzung zu tun.

Korrekt, du verstehst langsam. Aus dieser Sichweise heraus kann man also den Algo. iterativ wie auch rekursiv aufbauen (wenn es eine rekursive Version dafür gibt) ohne das es einen Untrschied in desen Komplexität gibt.

Erst wenn man anfängt diesen Algo. zu implementieren auf einer jeweiligen Hardware wird es nur und ausschließlich nur auf Grund dieser Hardware leichte Unterschiede zu Gunsten der iterativen Lösung geben.

Damit untermauert deine Aussage ja meine

Wenn einer 'was nicht sehen will.... Letzlich wiederholtest Du nur Deine Aussage und besitzt sogar noch die Stirn zu behaupten, ich hätte Deine Aussage untermauert, bleibst den Nachweis dieser abenteuerlichen Behauptung jedoch schuldig. Wenn iterativ und rekursiv wirklich nie einen Unterschied ausmachen, dann kann es an der Hardware ja erst recht kaum liegen.

Zitat von negaH:

Zitat von Delphi-Laie:

Außerdem wurde mit der rekursiven Berechnung irgendeines Gliedes der Fibonacci-Folge diese pauschale Lobhudelei der Rekursion bereits widerlegt, denn dort wird jeder Zwischenwert doppelt, dreimal oder noch (viel) häufiger berechnet.

Eben nicht. Wo ist da ein Beweis ? wenn man Äpfel mit Birnen vergleicht. Ich warte schon auf dein Argument das ja Windows auf Grund dessen das man dort alles rekursiv gelöst hat immer schlechter wird und jedes denkbare HW-System massiv ausbremst.

Diese abgedroschene Floskel, rhetorisch jedoch leere Phrase mit den Äpfeln und den Birnen. Man kann alles und jeden miteinander vergleichen. Wenn man Äpfel mit Birnen vergleicht, was wird man wohl feststellen? Gemeinsamkeiten und Unterschiede!

Allein, daß die Rekursion bei Fibonacci wiederholt (!) Zwischenwerte generiert, was die iterative Variante eben nicht tut, macht sie mir suspekt. Du warst es, der Rekursion vs. Iteration im wesentlichen auf Hardware reduziertest. Nun, dann frage ich mich, warum Windows trotz immer schnellerer Computer weiterhin dauerlahmt.

Zitat von negaH:

Kannst du mir sagen woher du eigentlich weißt das die Entwickler bei MS rekursive statt iterative Implementierungen bevorzugen ?

Sicher nicht, weil Du mir etwas in den Mund zu legen beabsichtigst. Du darfst gern den Versuch antreten, mir nachzuweisen, daß ich das irgendwo behauptet hätte.

Zitat von negaH:

Ich setze dagegen und behaupte das ich Fibonacci zb. auf einem FPGA sowohl iterativ wie rekursiv implementieren könnte und am Ende beides absolut identisch sein muß !

Nun, das kann ich Dir nicht widerlegen, noch kann ich meine Ansicht beweisen. Ich kann nur ein (kleines) Testprogramm schreiben (was ich bereits tue) und dann messen. Vielleicht kannst Du ja Deine Behauptung beweisen?!

[JasonDX]

Zitat von Delphi-Laie:

Außerdem wurde mit der rekursiven Berechnung irgendeines Gliedes der Fibonacci-Folge diese pauschale Lobhudelei der Rekursion bereits widerlegt, denn dort wird jeder Zwischenwert doppelt, dreimal oder noch (viel) häufiger berechnet.

Um Hagens Worte konkreter zu formulieren: 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.

Zitat von negaH:

Es gäbe da ein "Argument" pro Iterativ:
Nämlich das es bestimmte Problemstellung gibt die man nicht rekusiv formulieren kann.

Es könnte schwierig werden, solche Problemstellungen zu finden. Lambda-Ausdrücke sind gleichmächtig wie TMs, somit kann alles, was iterativ berechenbar ist, auch rekursiv beschrieben werden.

greetz
Mike

[negaH]

Zitat:

Es könnte schwierig werden, solche Problemstellungen zu finden. Lambda-Ausdrücke sind gleichmächtig wie TMs, somit kann alles, was iterativ berechenbar ist, auch rekursiv beschrieben werden.

vorsicht, jetzt begibts du dich auf Glatteis. Es gibt einen mathematischen Beweis das es solche Probleme geben muß. Leider finde ich jetzt nicht auf die Schnelle bei Wikipedia die richtige Seite.

Solche Probleme gibt es also wirklich. War irgenwas mit einer Ameisensimulation oä.

Gruß Hagen

[idefix2]

Zitat:

Außerdem wurde mit der rekursiven Berechnung irgendeines Gliedes der Fibonacci-Folge diese pauschale Lobhudelei der Rekursion bereits widerlegt

Widerlegt wurde nichts dergleichen, sondern es wurde nur bewiesen, dass eine schlechte Implementierung eines Algorithmus katastrophale Folgen auf die Performance haben kann - und das gilt für rekursive ebenso wie für iterative Verfahren.

Ich habe die Fibonacci-Folge rekursiv und iterativ für die Zahlen 10,20... bis 90 berechnet und ausgegeben (92 ist die grösste Zahl, für die die Fibonacci-Funtion noch in ein int64 passt).

i rec(10*i)
--- --------
1: 55
2: 6765
3: 832040
4: 102334155
5: 12586269025
6: 1548008755920
7: 190392490709135
8: 23416728348467685
9: 2880067194370816120
Zeit: 00:00:00
i iter(10*i)
--- --------
1: 55
2: 6765
3: 832040
4: 102334155
5: 12586269025
6: 1548008755920
7: 190392490709135
8: 23416728348467685
9: 2880067194370816120
Zeit: 00:00:00

Die Zeit, die die beiden Verfahren brauchen, ist vernachlässigbar.
Natürlich, wenn man jedes Zwischenergebnis unzählige Male neu berechnet, geht die Performance in den Keller, aber das hat nicht mit Iteration vs. Rekursion zu tun, sondern nur mit Unfug programmieren.

Delphi-Quellcode:

var
Feld: array [0..92] of int64;

procedure initfeld;
var i: integer;
begin
feld[0] := 0;
feld[1] := 1;
for i := 2 to 92 do
  feld[i] := -1; // noch nicht berechnet
end;

function iter(n: Integer): Int64;
var
  h: Integer;
begin
  if  feld[n] < 0
  then for h := 2 to n do
         if feld[h]<0 then feld [h] := feld[h-1]+feld[h-2];
  result := feld[n];
end;

function rec (n: integer): int64;
begin
  if feld[n]<0
  then feld[n] := rec(n-1)+rec(n-2);
  rec := feld[n];
end;

procedure TMainForm.Button2Click(Sender: TObject);

var
  i: Integer;
  t: TDatetime;
begin
  Memo1.Lines.Clear;
  Memo1.Lines.Add('i   rec(10*i) ');
  Memo1.Lines.Add('--- -------- ');
  initfeld;
  t := now;
  for i := 1 to 9 do
    Memo1.Lines.Add(Format('%2d: %8d ', [i, rec(10*i)]));
  Memo1.Lines.Add('Zeit: '+TimeToStr(now-t));

  Memo1.Lines.Add('i   iter(10*i) ');
  Memo1.Lines.Add('--- --------');
  initfeld;
  t := now;
  for i := 1 to 9 do
    Memo1.Lines.Add(Format('%2d: %8d ', [i, iter(10*i)]));
  Memo1.Lines.Add('Zeit: '+TimeToStr(now-t));
end;

[jfheins]

Ich hätte auch noch eine rekursive Version auf Lager, die ohne das zusätzliche Feld auskommt:

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);
        }

Berechnet keine Ergebnisse doppelt, und sollte von der Laufzeit her mit einer iterativen Version mithalten können.

[Delphi-Laie]

Mit Tatsachen läßt sich bekanntlich am schlechtesten diskutieren - nämlich gar nicht.

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.

Bei größeren Eingabewerten steigt die Berechnungszeit bei der Rekusrsion spürbar gegenüber der Iteration. Ich vermute mithin exponentielle Komplexität (ohne Gewähr) gegenüber linearer.

Daß daran nur die Hardware schuld sein soll, lasse ich mir von niemanden aufbinden.

@mkinzler: Ich weiß nicht, über wen Du herzogst, anscheinend über mich. Es ist schäbig, öffentlich in der dritten Person über jemanden sich abfällig zu äußern. Besonders unwürdig ist es bei einem Moderator und einer Person Deiner Bildung. Ich hoffe nicht, daß auch in diesem Forum irgendwann einmal Delphi-Treff-Verhältnisse einziehen werden.