@jfheins:
Ich glaube der Lehrer wollte nicht hören, dass man an seiner Begriffswahl herummeckert. (Ist aber eine sehr... interessante Lösung
)
Ähem, die rekursive Variante hat (*schnell anschau ohne viel nachzudenken*) sieht mir nach exponentieller Laufzeit aus (wenn man die Nummer des berechneten Folgenglieds betrachtet), da jeder Aufruf zwei Unteraufrufe auslöst bis zu einer Tiefe von n-2. Also sehr ineffizient gegenüber der iterativen Variante mit variablen Laufzeit, macht also viel aus.
Es gibt übrigens auch eine Variante mit konstanter Laufzeit, aber das nur so am Rande. (Bzw. linear, wenn man die Zeit für die Ausgabe mit einbezieht, aber dann wären auch die anderen Varianten schlechter.)