Einsatz Von Rekursion
← Rekursion in der Praxis | ● | Berechenbarkeit →
Ein weiteres Einsatzbeispiel sind die Fibonacci-Zahlen. Diese lassen sich mittels Rekursion elegant berechnen:
{
return((n<2)? 1 : fib(n-1)+fib(n-2));
}
Q Wie lautet die iterative Darstellung? Was ist die Laufzeit der beiden Varianten? Wie verhält sich die Laufzeit bei grossem n? Welche ist daher definitiv vorzuziehen?
Die iterative Variante, da sie eine lineare Laufzeit hat in Abhängigkeit von n.
Die rekursive Variante hat wegen der Aufrufverdoppelung eine exponentielle Laufzeit. Daher wird diese Art von Rekursion manchmal auch fat recursion genannt. Die andere Variante wird aufgrund des Laufzeitverhaltens lineare Rekursion genannt.
Zusammenfassend läßt sich sagen, dass Rekursion hervorragend geeignet ist, um eine Vielzahl von algorithmischen Problemen elegant abzubilden. Nur in manchen Fällen ist wegen der Performanz die iterative Variante vorzuziehen.
← Rekursion in der Praxis | ● | Berechenbarkeit →