Rekursion II

Aus ProgrammingWiki

< PMG < Kurs 11

Archivierte Version vom 2012-06-25T12:14:26+00:00. Aktuelle Version

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:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

Definition:

\mbox{fib}(n)=\begin{cases}1,\mbox{wenn}\hspace{0.3em}n=1\\1,\mbox{wenn}\hspace{0.3em}n=2\\\mbox{fib}(n-1)+\mbox{fib}(n-2),\mbox{sonst}\end{cases}

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 http://www.ijon.de/mathe/fibonacci/index.html

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));

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));

Ackermann-Funktion

Die Ackermann-Funktion folgendermaßen definiert:

Definition:

Ack(0, y)=y+1
Ack(n + 1, 0) = Ack(n, 1)
Ack(n +1, y+1) = Ack(n, Ack(n + 1, y))

Informationen zur Ackermann-Funktion unter http://de.wikipedia.org/wiki/Ackermannfunktion

Rekursion II

Inhaltsverzeichnis

Die Fibonaccizahlen

iterativ

rekursiv

Ackermann-Funktion

Suche