Rekursion II

Aus ProgrammingWiki

Inhaltsverzeichnis 1 Die Fibonaccizahlen 1.1 iterativ 1.2 rekursiv 2 Ackermann-Funktion

Die Fibonaccizahlen

Leonardo Fibonacci di Pisa (* um 1180; † 1241) beschrieb die Fortpflanzung von Kaninchen mit der Zahlenfolge:

Definition:

Beschreibung:

Die Kaninchenpaar bekommt nach zwei Monaten Nachwuchs (Pärchen!), dies dann jeden Monat. Die "Kinderpaare" verhalten sich genauso. Die Kaninchen leben "unendlich lange".

Das bedeutet:

• Die ersten beiden Glieder der Zahlenfolge sind jeweils 1.
• Jedes weitere Glied ergibt sich aus der Summe seiner beiden Vorgänger.

Prüfen!

siehe auch [1]

iterativ

Zunächst eine iterative Version:

function fibo_it(n:integer):integer; var f1,f2,i:integer; begin result := 1; f1 := 1; f2 := 1; for i := 3 to n do begin result := f1 + f2; f1 := f2; f2 := result; end; end;

writeln(fibo_it(4));

ausführen

rekursiv

Schreiben Sie nun eine rekursive Funktion gemäß der oberen Beschreibung:

function fibo_rek(n:integer):integer; begin end;

function fibo_rek(n:integer):integer; begin if (n=1) or (n=2) then result:=1 else result:= fibo_rek(n-1)+fibo_rek(n-2); end;

write(fibo_rek(3));

ausführen

Ackermann-Funktion

Die Ackermann-Funktion folgendermaßen definiert:

Definition:

Informationen zur Ackermann-Funktion unter [2]