Rekursion vs. Iteration

[jfheins]

Zitat von Delphi-Laie:

Ich verstand zudem sehr wohl, daß man Iterationen auch über Rekursion (bzw. umgekehrt) abbilden kann, daß es da eine Äquivalenz gibt.

Das ist schön, das habe ich nämlich immer wieder bezweifelt.

Zitat von Delphi-Laie:

Natürlich kann man auch eine Rekursion dort hineinwürgen, wenn man denn unbedingt eine haben möchte, weil man sie so sehr mag, aber die eingangs so hochgelobten Vorteile wie Übersichtlichkeit, Wartbarkeit, geringeres Fehlerrisiko usw. bleiben dabei nach meiner Einschätzung voll auf der Strecke, sie sind jedenfalls nicht offensichtlich besser als bei der Iteration.Dafür stimmt aber das Laufzeitverhalten. Beides ist anscheinend wenigstens an diesem Beispiel nicht unter einen Hut zu bringen

Richtig. Das liegt daran, dass sich für Fibonacci die iterative Problemlösung besser eignet. Das heißt aber nicht dass Iteration allgemein und immer besser ist, sondern bei diesem Problem. Ich hatte das Gefühl, du verallgemeinerst das Beispiel. Siehe auch:

Zitat von alzaimar:

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.

Zitat:

(weshalb ich die Pauschalität weiterhin negiere).

Was negierst du? Du hast doch oben selbst gesagt, dass du verstanden hast dass man immer Rekursion auf Iteration abbilden kann und umgekehrt. Also eine 100% Äquivalenz was die Laufzeitkomplexität angeht.

Zitat:

Welchen Vorteil nun eine solche Rekursion gegenüber der Iteration hat, weiß ich immer noch nicht, aber ich möchte es nunmehr auch nicht mehr wissen.

Bei manchen Problemen (Fibonacci gehört nicht dazu) ist die rekursive Schreibweise leichter verständlich und übersichtlicher als die iterative. (Gleicher Algorithmus und damit gleiche Komplexität wohlgemerkt) Reicht das nicht?