Rekursion vs. Iteration

[Daniel]

Zitat von Delphi-Laie:

Zudem ruft süffisanterweise sich im 2. Codeschnipsel auch die Schleife selbst immer wieder auf, es ist also auch sich selbst (immer wieder) aufrufender Code!

Und genau das halte ich für unpräzise. Die Schleife (nun nicht gerade Dein Beispiel, aber allgemeine Schleifen) enthalten Code, der wiederholt ausgeführt wird. Du hast ja völlig korrekt angemerkt, dass im ersten Beispiel der Stack zum Problem wird und das ist der substantielle technische Unterschied zwischen beiden Varianten. In der zweiten Variante springt der Programmzeiger zum Anfang der Schleife, der Kontext bleibt gleich. In der ersten Variante, der Rekursion, wird eine frische, neue Funktion mit ihren eigenen frisch initialisierten lokalen Variablen aufgerufen. Es mag sein, dass am Ende beide Fassungen zum gleichen Rechenergebnis kommen, aber das Verhalten zur Laufzeit ist für meine Begriffe gänzlich unterschiedlich.

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.

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