012
24.09.2002, 10:21 Uhr
virtual
Sexiest Bit alive
(Operator)
|
Es geht mir nicht darum zu behaupten, daß eine iterative Lösung besser sei, sie ist eben einfach nur möglich. Ich denke, dass es Vor- und Nachteile gibt, die von der Problemstellung abh.
Wenn die Problemstellung sich nur mit Mühe in einen iterativen Algo umsetzen läßt, der letztlich schwerer zu verstehen ist, würde ich einen rekursiven Ansatz vorziehen. Wenn der Algo jetzt besonders schnell sein muss und der Overhead eines rekursiven Funktionsaufrufs sehr teuer ist (im Verhältnis zum Rest der Funktion), vielleicht eher die iterative Variante.
Bei Fibonacci ist zB der Algo leicht durchschaubar, wenn er Rekursiv implementiert ist:
| C++: |
unsigned fibonacci(unsigned n)
{
if (n<3) return 1;
return fibonacci(n-1) + fibonacci(n-2);
}
|
Aber der Overhead des Funktionsaufrufe ist fast unerträglich hoch. Dann schon eher was iteratives der Form:
| C++: |
unsigned fibonacci(unsigned n)
{
unsigned n1 = 1;
unsigned n2 = 1;
unsigned s = 1;
for(unsigned i=3; i<=n; ++i)
{
s = n1+n2;
n1 = n2;
n2 = s;
}
return s;
}
|
Hier ist zwar der Rekursive Gedanke vom Fibonacci nicht klar erkennbar, aber die Funktion sollte deutlich schneller sein weil die Funktionsaufrufe teurer sind als die beiden zuweisungen an n1 und n2- (Frage: lauten die ersten Zahl der Fibonacci Folge wirklich 1 und 1, oder vertue ich mich da`?)
--
Gruß, virtual
Quote of the Month
Ich eß' nur was ein Gesicht hat (Creme 21) |
