PMG/Kurs 11/Rekursion II

Wiki-Quelltext dieser Seite.

<language>Pascal</language>
=== Die Fibonaccizahlen ===

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

<blockquote><math>1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...</math></blockquote>

'''Definition:'''
<blockquote>
<math>\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}</math>
</blockquote>

'''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:

<code id="4fe852b55bb3d">
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;
</code>

<run id="4fe852b55bc30">
writeln(fibo_it(4));
</run>

==== rekursiv ====


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

<code id="4fe852b55bbac">
function fibo_rek(n:integer):integer; 
begin
 
end;
</code>

 <code id="4fe8538ae6d87" hidden>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;</code>


<run id="4fe852b55bc8a">
write(fibo_rek(3));
</run>

<check>
result := (fibo_rek(3) = 2) and (fibo_rek(6) = 8);
</check>


=== Ackermann-Funktion ===

Die Ackermann-Funktion folgendermaßen definiert:

'''Definition:'''
<blockquote>
<math>Ack(0, y)=y+1</math><br>
<math>Ack(n + 1, 0)     = Ack(n, 1)</math><br>
<math>Ack(n +1, y+1)      = Ack(n, Ack(n + 1, y))</math>
</blockquote>

<br>

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