Fibonacci in 6 Versionen

[fkerber]

Codewalker stellt eine weitere rekursive, aber endrekursive, Variante vor. Die rekursive Variante ist deutlich langsamer als die iterative Lösung. Grund ist, dass die Funktion nicht endrekursiv ist. Das bedeutet, dass kein Zwischenergebnis errechnet werden kann, sondern die Rekursionstiefe doppelt exponentiell wächst.

Eine endrekursive Variante ist deutlich speicherschonendner und vor allem schneller:

Delphi-Quellcode:

function Fibonacci_Rekursiv2(Index : Integer) : Int64;
  function Fibonacci_Rekursiv_Help(f1,f2,n: Integer): Integer;
    begin
      if n = 0 then
        Result:=f1
      else 
        Result:=Fibonacci_Rekursiv_Help(f2,f1+f2,n-1);
    end;
begin
  case Index of
    1, 2 : Result := 1;
    else Result := Fibonacci_Rekursiv_Help(0,1,Index);
  end;
end;