Rekursion vs. Iteration

[Delphi-Laie]

Zitat von Daniel:

Zitat von Delphi-Laie:

Das Laufzeitverhalten ist dagegen eher mau, denn diese Baumstruktur des Prorgrammablaufes beim Aufrufen der rekursiv aufgerufenen Unterprogramme x. Ordnung führen mit ziemlicher Sicherheit zu mindestens exponentiellem Laufzeitverhalten (bei der Fakultät z.B. sogar zu hyperexponentiellem Wachstum).

Und warum das Laufzeitverhalten per se mau sei, kann ich aus Deinem Beitrag immer noch nicht entnehmen. Kannst Du die Formulierung "exponentielles Verhalten" präzisieren? Ich kenne z.B. exponentielles Wachstum - aber nicht exponentielles Verhalten.

Laufzeitverhalten schrieb ich.

Dann gehe mal einen rekursiven Algorithmus (im engeren Sinne, wie ich es ausführlich beschrieb), während er abläuft (also den Prozeß seines Ablaufes) durch: Die hierarchieniedrigsten Aufrufe sind die häufigsten! Konkret z.B. beim rekursiven Fibonacci: Fib(0) bzw. Fib(1) werden am häufigsten berechnet. Ziseliert man diesen Prozeß (graphisch), entsteht eine Baumstruktur. Und die Anzahl der Elemente von Bäumen ist - soweit ich weiß - exponentiell.

Edit: So allgemein gilt das doch nicht. Beim Quicksort ist das Laufzeitverhalten viel günstiger (logarithmisch), allerdings gibt es dort keine Mehrfachaufrufe: Was sortiert ist, wird nie wieder vom Algorithmus berührt (vielleicht ist das schon der Grund für die gute Komplexität?!), im Gegensatz zu den vielen Mehrfachberechnungen bei z.B. dem rekursiven Fibonacci. Das mehrmalige (konkret immer zweifache) Aufrufen von hierarchiegleichen Subprozessen (wie im Vorbeitrag ausgeführt) ist aber auch hier gegeben.