Man sollte noch eine weitere Rekursionsvariante erwähnen: In #24 hat alzaimar die naive Rekursion durch
Memoisation auf die gleiche asymptotische Laufzeit wie die iterative Version gebracht, allerdings mit Θ(n) Speicherverbrauch (genauer: Θ(n) Stack und Θ(n) Heap).
Genauso wie
Zitat von
alzaimar:
es für jeden rekursiven Algorithmus ein iteratives Äquivalent
gibt es auch immer umgekehrt ein direktes Äquivalent - sonst hätten funktionale Sprachen ohne Schleifen ein echtes Problem -, in diesem Fall:
Delphi-Quellcode:
function Fib(n)
function Loop(i, j, n')
begin
if n' = n then
Result := i
else
Result := Loop(j, i + j, n' + 1);
end;
Loop(0, 1, 0);
end;
In Delphi hat diese Variante genau die gleiche Zeit- und Platzkomplexität wie die Memoisationsvariante, der große Witz daran ist aber, dass die Funktion
endrekursiv ist (was alzaimar wohl mit "rechtsrekursiv" meinte, den Begriff kenne ich aber nur aus dem Compilerbau). Damit kann ein schlauer Compiler nicht nur durch
Tail Calls den linearen Stackverbrauch eliminieren, in solch simplen Fällen sollte er sogar quasi den
gleichen Maschinencode erzeugen, egal ob iterativ oder rekursiv!
Natürlich ist diese Variante nicht
ganz so leserlich wie die naive Rekursion, aber wenigstens diese dämliche Hilfsvariable entfällt ;P . Vor allem wollte ich eben auf diese direkte Äquivalenz der beiden Methoden hinaus.
Um das ganze mal zusammenzufassen
:
Code:
.
Zeit Stack Heap
iterativ Θ(n) Θ(1) 0
/rekursiv mit Tail Calls
naive Rekursion Θ(fib(n)) = Θ(φ^n) Θ(n) 0
+ Memoisation Θ(n) Θ(n) Θ(n)
Aber in welche Klasse fällt denn bitte inheriteds netter Algo, O(log² n)
?