Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by Khabarakh,
11. Jun 2010
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 f(n) = f(n-1) + f(n-2); f(0) = 0; f(1) = 1ab und besitzt eine Laufzeit von Θ(fib(n)) = Θ(1.61...^n) (ja, das Ding hat sich selbst als Laufzeit ;) ). Wenn man an...
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by Khabarakh,
8. Jun 2010
Ja, Rekursion lässt sich immer als Iteration + Stack umsetzen. Nicht zufällig heißt das Ding, auf dem die Variablen landen, gleich ;) .
In deinem Beispiel: Das Ursprungsverzeichnis auf einen Stack werfen, solange dieser nicht leer ist, das oberste Element behandeln und alle Unterverzeichnisse hinzufügen.
Rekursionen sind wirklich wunderhübsch, aber da die wenigsten imperativen Sprachen Tail...