Rekursion vs. Iteration

[gammatester]

Vielleicht sollten wir uns erst einmal einigen, was unter Algorithmus zu verstehen ist. Es geistern hier "Algorithmus", "Algorithmen-Basis", "Problem-Stellung" usw durcheinander.

Und natürlich ist es sinnvoll, den "Apfel"-Algorithmus mit exponentieller Laufzeit mit dem "Birnen"-Algorithmus mit logaritmischer Laufzeit zu vergleichen, uns sei's nur darum, umherauszufinden welcher ein bestimmtes Problem "besser" löst.

"Besser" kann situationsabhängig sein: Wenn ich schnell ein Problem lösen muß bis n=10, ist es ev. "besser" einen quick-und-dirty O(2^n)-rekurven Algorithmus in 5 min zu implementieren, als einen hochoptimierten O(log(n)) iterativen, der aber erst ab n>1000 schneller ist und nach 5 Tagen fertig ist.

[Delphi-Laie]

Zitat:

Zitat von negaH (Beitrag 1028083)

Zitat:

Zitat von Delphi-Laie (Beitrag 1028069)

Zitat:

Zitat von negaH (Beitrag 1028044)

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:

Zitat von negaH (Beitrag 1028083)

Zitat:

Zitat von Delphi-Laie (Beitrag 1028069)

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:

Zitat von negaH (Beitrag 1028083)

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:

Zitat von negaH (Beitrag 1028083)

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?!

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

[JasonDX]

Zitat:

Zitat von negaH (Beitrag 1028102)

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

[negaH]

Zitat:

Zitat von gammatester (Beitrag 1028108)

Vielleicht sollten wir uns erst einmal einigen, was unter Algorithmus zu verstehen ist. Es geistern hier "Algorithmus", "Algorithmen-Basis", "Problem-Stellung" usw durcheinander.

Und natürlich ist es sinnvoll, den "Apfel"-Algorithmus mit exponentieller Laufzeit mit dem "Birnen"-Algorithmus mit logaritmischer Laufzeit zu vergleichen, uns sei's nur darum, umherauszufinden welcher ein bestimmtes Problem "besser" löst.

"Besser" kann situationsabhängig sein: Wenn ich schnell ein Problem lösen muß bis n=10, ist es ev. "besser" einen quick-und-dirty O(2^n)-rekurven Algorithmus in 5 min zu implementieren, als einen hochoptimierten O(log(n)) iterativen, der aber erst ab n>1000 schneller ist und nach 5 Tagen fertig ist.

Naja, aber für einen fairen Vergleich "iterativ vs. rekursiv" sollte man schon sich auf ein und den selben Algorithmus beziehen.

Problemstellung -> Formel/Algortihmus -> Implementierung auf jeweiliger HW mit spezifischer SW -> rekursiv vs. iterativ

Das wäre mein Vorschlag.

Das Aufwand-Nutzen-Verhältnis sollten wir aussen vor lassen.

Gruß Hagen

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

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

[negaH]

Zitat:

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:

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.

Na dann schau dir mal dieses Zitat an.

... warum Windows... lahmlegt.

Dir ist schon bewusst das wir hier "iterativ vs. rekursiv" diskutieren ? Und du führst als Agrumentation Windows oder Assembler an. Jeder geht dann davon aus, besonders weil du pro "iterativ" argumentierst, das somit Windows langsammer wurde weil es rekursive Implementierungen bevorzugt.

Zitat:

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.

Dann lese das entsprechende Posting nochmal. Und ja wenn es Unterschiede final gibt dann kann das nur an der HW liegen. Sprich zusätzlicher CALL + Einrichten des Stacks und damit mehr Speicher bei rekursiven Impl. im Vergleich zur iterativen.

Gruß Hagen