Aufgabe 3.5 – Rekursive Berechnung der Fibonacci-Zahlen

 

Wie wir noch aus Lerneinheit 1 wissen, ist die Folge der Fibonacci-Zahlen wie folgt definiert:
{f_n} = {f_{n-2}}+{f_{n-1}},\quad n \geq 2,\quad {f_0} = 0,\quad {f_1} = 1

  1. Schreiben Sie eine Funktion F=fibonacci_rec(n), die die n-te Fibonacci-Zahl durch explizite rekursive Funktionsaufrufe berechnet!
  2. Schreiben Sie eine Funktion F=fibonacci_lop(n), die die n-te Fibonacci-Zahl analog zu Lerneinheit 1 ohne rekursive Aufrufe in einer Schleife berechnet!
  3. Schreiben Sie eine Testfunktion b=fibotest(n), die das Verhältnis b der Laufzeiten der beiden Funktionen aus a) und b) ermittelt.

Lösung

a )

function F=fibonacci_rec(n)
	% Lösungsvariante mit rekursivem Funktionsaufruf
	if n<=2
		F=1;
	else
		F=fibonacci_rec(n-1)+fibonacci_rec(n-2);
	end
end

b )

function f=fibonacci_lop(n)
	% Lösungsvariante mit Ringpuffer
	% Initialisierung
	buffer=[1 1];

	for i = 3:n
		f=sum(buffer);
		% speichere aktuelle Zahl im Ringpuffer
		buffer(rem(i,2)+1)=f;
	end
end

c )

function b=fibotest(n)
	tic
	fibonacci_lop(n);
	t1=toc;
	tic
	fibonacci_rec(n);
	t2=toc;
	b=t2/t1;
end