Rekursion vs. Iteration

[gammatester]

Zitat:

Zitat von jfheins (Beitrag 1028062)

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.

[Delphi-Laie]

Zitat:

Zitat von jfheins (Beitrag 1028062)

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

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

Ich schlage mal folgendes vor: Vergleiche mal die Berechnung der Koeffizienten eines charakteristischen Polynoms einer quadratischen Matrix mit Rekursion (nach der Determinantenberechnung 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!

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.

[negaH]

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

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

[JasonDX]

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.

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:

Zitat von negaH (Beitrag 1028088)

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

[jfheins]

Zitat:

Zitat von gammatester (Beitrag 1028074)

Zitat:

Zitat von jfheins (Beitrag 1028062)

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:

Zitat von Delphi-Laie (Beitrag 1028080)

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

[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

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

[negaH]

Zitat:

Zitat von Delphi-Laie (Beitrag 1028125)

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

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.

Tja, Glashaus und Porzelanladen. Schade eigentlich. Bin somit weg.

Gruß Hagen

[Delphi-Laie]

Zitat:

Zitat von negaH (Beitrag 1028124)

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.

Nun mal halblang. Du kannst mich dafür verantwortlich machen, daß Du in meine Aussagen etwas hineindichtest und sie damit fehlinterpretierst. Erst recht steht es Dir nicht zu, für alle zu sprechen. Ich weiß genau, was ich schrieb und krame es extra noch mal für Dich hervor:

„Manchmal habe ich sogar den Verdacht, daß absichtlich Bremsschleifen dorthinein implementiert wurden.“

Dort steht etwas von Schleifen (das sind Iterationen!), nicht jedoch von Rekursion. Also, wenn man schon jemanden zitiert, sollte man dabei auch redlich und sorgfältig vorgehen und nicht versuchen, jemanden daraus einen Strick zu drehen.

[Daniel]

Schön, dann können wir ja jetzt wieder zu den fachlichen Aspekten der Frage übergehen.

[idefix2]

@ jfheins:

Jetzt erinnere ich mich, über die Transformation bin ich in meinem Studium auch einmal gestolpert, habs in der Zwischenzeit wieder vergessen. Ist ein sehr eleganter rekursiver Ansatz.

Fairerweise muss man aber sagen, dass es doch ein ganz anderer Algorithmus ist, als der in der iterativen Variante verwendete. Vor allem aber erfordert er sehr langes Nachdenken, um dahinterzukommen, wie das Ding funktioniert, ich habe das damals gemacht und WILL es eigentlich gar nicht mehr nachvollziehen - was aber der Intention, lesbare und leicht verständliche Programme zu erstellen, eigentlich diametral entgegengesetzt ist.

[jfheins]

Zitat:

Zitat von Delphi-Laie (Beitrag 1028125)

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

Keine Angst, die Hardware ist nicht schuld. Du bist schuld.
Das rekursive ist ein schlechterer Algorithmus, und damit klar unterlegen. Das hat nichts mit rekursion vs. iteration zu tun, sondern mit guter vs. schlechter Algorithmus.
Benutze einen Algorithmus aus Post #59 oder Post #59 und es sollte schneller laufen.

Genausogut kann ich einen rekursiven Quicksort gegen einen iterativen Bubblesort vergleichen. Und OMG OMG iteration ist ja TOTAL lahm, wenn man ein paar mehr Elemente nimmt :shock: :shock: :shock: :shock:


Es gibt Algorithmen, die sich besser so und besser so implementieren lassen. Fibonacci ist für mich etwas, was sich rekursiv sehr einfach schreiben lässt, dann aber unperformant wird, und daher die iterative Variante vorzuziehen ist. (Weil da weniger Lesbarkeit verloren geht gegenüber der performanten Rekursion)

[JasonDX]

Zitat:

Zitat von Delphi-Laie (Beitrag 1028125)

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.

Du hast es richtig erfasst: Du vergleichst Algorithmen, nicht Implementierungen. Vergleiche doch mal eine rekursive und eine iterative Implementierung des selben Algorithmus. Dann wirst du merken, dass dort kaum ein Unterschied vernehmbar ist.
Andernfalls... Ich friemle mal für dich (deine Worte) Klugheitsausscheider mal ein kleines Programm zusammen, das eine Liste von Zahlen sortiert. Ich verwende die rekursive Implementierung von Quicksort, und eine iterative Implementierung von BogoSort. Das Ergebnis kannst du dir denken...
Du magst vielleicht Äpfel und Birnen vergleichen können - aber daraus kannst du keine Rückschlüsse auf Rind- und Schweinefleisch ziehen. Das tust du aber: Du vergleichst Algorithmen und schließt daraus auf Eigenschaften verschiedener Implementierungsverfahren... Fällt dir langsam dein Fehler auf?

greetz
Mike

[idefix2]

Zitat:

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.

Wie ich in meinem Post 58 geschrieben habe - eine schlechte Implementierung kann für schlechte Performance sorgen, auch bei iterativen Verfahren. Einen untauglich implementierten rekursiven algorithmus mit einem brauchbar implementierten itetrativen Algorithmus zu vergleichen, beweist gar nichts.

Es kommt auch bei iterativen Verfahren vor, dass man rechenaufwändige Zwischenergebnisse später wieder braucht, da bringst Du die Performance in der gleichen Weise in den Keller, wenn Du die Zwischenergebnisse immer wieder neu berechnest.

[Delphi-Laie]

Zitat:

Zitat von jfheins (Beitrag 1028130)

Benutze einen Algorithmus aus Post #59 oder Post #59 und es sollte schneller laufen.

Das ist durchaus möglich. Allerdings ist dieser Algorithmus - im Vergleich zur „vollrekursiven“ Variante - teilweise „entrekursiviert“ (Die, die Ihr Informatik studiert(et) - gibt es ein Verb dafür?) (worden). Die originale rekursive Definition der Fibonaccigliederberechnung findet sich dort jedenfalls nicht mehr. Wenn man einen vollrekursiven Algorithmus teilweise von der Rekursion befreit und sich dann eines Laufzeitverhaltens erfreut, das mit der Iteration mithalten kann - das ist m.E. kein plausibler Nachweis dafür, daß die Rekursion der Iteration ebenbürtig ist?! Denn gerade, weil die Rekursion es eben (vom Laufzeitverhalten bzw. der Komplexität) her nicht ist, ist sie in jenem Algorithmus teilweise entfernt worden.

[negaH]

Ok, gehen wir es mal systematisch an.

Wir wollen wissen ob eine "rekursive" Schreibweise ein und des selben Algorithmus im Gegensatz zu einer "iterativen" Schreibweise in einer Programmiersprache die keine der beiden Seiten bevorzugt auf einer Hardware die ohne zusätzliche Performance- und Speicherunterschiede beim Aufruf von Unterfunktionen, einen Unterschied machen.

Wir stellen uns eine Programmiersprache vor in der man ein Algo. sowohl iterativ wie auch rekursiv schreiben kann. Der dahinter liegende Compiler bzw. die Synthese zerlegt unseren geschriebenen Quelltext so das sie mit Boolscher Analyse die rekursive Variante in die iterative überführen kann oder umgekehrt. D.h. aus Sicht des erzeugten Resultates wird der Maschinencode für ASCIs oder das Bitfile für FPGAs bei beiden Schreibweise absolut identisch sein. Somit schließen wir Hardwareunterschiede mal komplett aus. Bei FPGAs ist es auch exakt so und nicht anders.

Was bleibt ?

Zwei Quelltexte die ein und den selben Algorithmus oder meinetwegen Formel beschreiben.
Es ist nun so das Mathematiker die solche Formeln aufschreiben sie fast immer rekursiv aufschreiben zb. in Polnischer Notation.
Es ist aus Sicht der Resourcen/Performance egal ob man nun im Quelltext diese Formel rekursiv oder iterativ aufschreibt. Wie oben schon definiert wird der Compiler/Synthese sowie so diese Quelltexte in ein und das selbe Resultat umwandeln. Das interessiert uns nicht.

Der Unterscheid ist:
- rekursive Formel -> rekursiver Algo -> rekursiver Quelltext
- rekursive Formel -> iterativer Algo -> iterativer Quelltext

Wäre es nun aus Sicht der Verständlichkeit nicht besser alles rekursiv zu machen ?

Ein weiterer Unterschied ist das man bei rekursiven Schreibweisen eine Menge an redundanten Wiederholungen einspart. Das ist ja auch der Grund warum Mathematiker/Informatiker bevorzugt solche Probleme rekursiv formulieren und implementieren.

Wir haben also einen Algo mit Komplexität X. Egal ob rekursiv oder iterativ implementiert, diese Komplexität muß erhalten bleiben da man ansonsten Äpfel mit Birnen vergleicht. Wir haben eine Hardware und einen Programmiersprache die in beiden Fällen keine der beiden bevorzugt.
Ergo: am Ende sind die Resultate in Punkto Komplexität, Performance und Resourcenverbracuh exakt identisch. Einzigst die Schreibweise macht einen Unterschied. Da man über die rekursive Schreibweise eine bessere Verständlichkeit erreicht, auf Grund des Weglassen von reduntanten Formelbestandteilen, muß die rekursive Variante im Allgmeinen besser Verständlich sein und damit wartbarer.

Gruß Hagen

[Delphi-Laie]

Zitat:

Zitat von idefix2 (Beitrag 1028134)

Zitat:

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.

Wie ich in meinem Post 58 geschrieben habe - eine schlechte Implementierung kann für schlechte Performance sorgen, auch bei iterativen Verfahren. Einen untauglich implementierten rekursiven algorithmus mit einem brauchbar implementierten itetrativen Algorithmus zu vergleichen, beweist gar nichts.

In dieser Diskussion finden sich pauschale Äußerungen, daß rekursiv dem Iterativen ebenbürtig ist, und das ist so pauschal eben falsch. Nunmehr wird - von Dir - bei rekursiv zwischen „brauchbar“ und „untauglich implementiert“ unterschieden. Daß der Algorithmus als solcher selbst bzw. an sich ein schlechteres Laufzeitverhalten hat (haben kann), wird auch mit solchen Aussagen umschifft. Wie soll denn ein rekursiver Algorithmus, der auf der Gleichung

fibonacci(n)=fibonacci(n-1)+fibonacci(n-2)

beruht oder aufbaut, „tauglich implementiert“ werden?

[negaH]

Zitat:

In dieser Diskussion finden sich pauschale Äußerungen, daß rekursiv dem Iterativen ebenbürtig ist, und das ist so pauschal eben falsch.

Dann beweise das bitte. Ich behaupte das es da keinen Unterschied geben darf und wird aus Sicht des Resultates wenn man einen fairen Vergleich anstellt.

Es unterscheidet sich ausschließlich nur die Schreibweise im Quelltext. Es verbleiben nur noch konstruktiv die Argumente, was ist verständlicher und damit wartbarer.

Gruß Hagen

[Mithrandir]

Leude... :roll:

Meint ihr nicht, ihr habts langsam? Ich dreht euch dauernd im Kreis, seit mindestens 6 Seiten. Wenn ihr Bock darauf habt, tausch euch per PN aus und postet das Resultat hier. So kommt ihr jedenfalls kein Stückchen weiter. ;)

[Delphi-Laie]

Zitat:

Zitat von negaH (Beitrag 1028142)

Zitat:

In dieser Diskussion finden sich pauschale Äußerungen, daß rekursiv dem Iterativen ebenbürtig ist, und das ist so pauschal eben falsch.

Dann beweise das bitte. Ich behaupte das es da keinen Unterschied geben darf und wird aus Sicht des Resultates wenn man einen fairen Vergleich anstellt.

Gern, und zwar ohne daß ich Sätze mehr verstümmele, als diese zu zitieren:

Zitat:

Zitat von negaH (Beitrag 1028083)

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.

Zitat:

Zitat von negaH (Beitrag 1028086)

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.

[negaH]

Und wo siehst Du jetzt eine Diskrepanz ?

Gruß Hagen

[JasonDX]

Zitat:

Zitat von Delphi-Laie (Beitrag 1028139)

In dieser Diskussion finden sich pauschale Äußerungen, daß rekursiv dem Iterativen ebenbürtig ist, und das ist so pauschal eben falsch.

Es ist dir bisher nicht gelungen, dies zu begründen. Beide Algorithmen lassen sich sowohl iterativ als auch rekursiv implementieren. Die Schlussfolgerung deines Vergleichs unterliegt aber der Wahl des Algorithmus, nicht der Implementierungsvariante, du ziehst somit die falschen Rückschlüsse daraus.

Zitat:

Zitat von Delphi-Laie (Beitrag 1028139)

Daß der Algorithmus als solcher selbst bzw. an sich ein schlechteres Laufzeitverhalten hat (haben kann), wird auch mit solchen Aussagen umschifft.

Du vergleichst also Algorithmen. Wir vergleichen Implementierungen. Du willst uns davon überzeugen, dass ein BMW schneller ist als ein Benz und veranstaltest dafür ein Wettrennen zwischen einem BMW und einem Fahrrad...

Zitat:

Zitat von Delphi-Laie (Beitrag 1028139)

Wie soll denn ein rekursiver Algorithmus, der auf der Gleichung

fibonacci(n)=fibonacci(n-1)+fibonacci(n-2)

„tauglich implementiert“ werden?

Gegenfrage: Wie soll denn ein iterativer Algorithmus, der auf der Gleichung [...] "tauglich implementiert" werden?
Jeder Algorithmus kann iterativ und rekursiv implementiert werden. Und wenn man sich jfheins' rekursive Variante ansieht und die Endrekursion auflöst, kommt man genau auf deine iterative Variante. Sollten bei der Implementierung Performanceunterschiede auftreten, sind diese somit offensichtlich Hardware-bedingt, da die theoretische Äquivalenz beider Implementierungen beweisbar ist.

greetz
Mike

[hitzi]

Delphi-Laie, vielleicht hilft dir ein bildlicher Vergleich deinen Fehler zu erkennen.

Rekursion = vorwärts laufen
Iteration = rückwärts laufen

Aufgabe: Laufe von A nach B

Vorwärts, wie auch rückwärts ist die Strecke bei idealen Bedingungen in gleicher Zeit zu schaffen. Nur die verwendete Hardware (zu Fuss, mit dem Auto, was auch immer) kann einen zeitlichen Unterschied ausmachen.

Bei deinen Vergleichen läufst du vorwärts(rekursiv) von A nach B, aber rückwärts nimmst du eine Abkürzung (andere Algorithmus) und bist eben rückwärts(iterativ) schneller am Ziel.

[idefix2]

Zitat:

Allerdings ist dieser Algorithmus - im Vergleich zur „vollrekursiven“ Variante - teilweise „entrekursiviert“

Was soll das heissen? rekursiv bedeutet doch nicht, dass man bereits vorhandene Ergebnisse ignorieren und bereits erfolgte Rechenschritte jedesmal von neuem machen muss.
Die Berechnung erfolgt in der rekursiven Variante 100% rekursiv, aber selbstverständlich wird eine vernünftige Implementierung JEDES Algorithmus auf bereits vorhandene Ergebnisse zurückgreifen und die nicht neuerlich berechnen, und das gilt natürlich genauso für iterative Verfahren.

Zitat:

Die originale rekursive Definition der Fibonaccigliederberechnung findet sich dort jedenfalls nicht mehr.

Die findet sich bei der Initialisierung des Feldes: Feld[0] := 0. Feld[1] := 1. Damit werden die Anfangswerte sowohl für das iterative als auch für das rekursive Verfahren gesetzt, und ich erspare mir in beiden Funktionen die Abfrage auf Sonderwerte.

Zitat:

Nunmehr wird - von Dir - bei rekursiv zwischen „brauchbar“ und „untauglich implementiert“ unterschieden. Wie soll denn ein rekursiver Algorithmus, der auf der Gleichung
fibonacci(n)=fibonacci(n-1)+fibonacci(n-2)
beruht oder aufbaut, „tauglich implementiert“ werden?

Das Ergebnis (stark ansteigende Laufzeit) beweist eben, dass die Implementierung untauglich ist. Wenn Du die berechneten Zwischenergebnisse speicherst, und direkt abrufst, falls es sie schon gibt, hast Du aus der untauglichen Implementierung eine taugliche Implementierung des GENAU GLEICHEN Algorithmus gemacht. Diese taugliche Implementierung ist dann im wesentlichen gleich schnell wie ein tauglich implementiertes iteratives Verfahren, und sicher viel schneller, als wennn Du in das iterative Verfahren irgend einen unnötigen Unfug einbaust, der die Laufzeit hinaufschnellen lässt.

Zitat:

Daß der Algorithmus als solcher selbst bzw. an sich ein schlechteres Laufzeitverhalten hat (haben kann), wird auch mit solchen Aussagen umschifft.

Nicht der Algorithmus hat das schlechtere Laufzeitverhalten, sondern eben Deine Implementierung. Sobald der Designfehler bei der Implementierung korrigiert ist, ist das Laufzeitverhalten gleich gut.

[negaH]

Zitat:

Du vergleichst also Algorithmen. Wir vergleichen Implementierungen.

Noch nichtmal das, wir vergleichen erstmal nur unterschiedliche Schreibweisen ein und der selben Sache.

Gruß Hagen

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

Zitat von gammatester (Beitrag 1027949)

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.