|
Das wohl naheliegendste Einsatzgebiet ist das Berechnen von Gliedern rekursiver Folgen. Hier bietet sich der Eisatz von rekursiven Funktionen an, die selbst einen Wert annehmen können. Beim Aufruf der Funktion muß überprüft werden, ob die als Parameter übergebene Nummer des Gliedes Eins ist. Wenn dies der Fall ist, wird der Funktion der Wert für a1 übergeben und die Funktion beendet. Andernfalls wird der Funktion ein Wert zugewiesen, der aus einer Berechnung mit dem Funktionswert des vorhergehenden Gliedes resultiert, was einen Selbstaufruf mit dem um eins verringerten Parameter zur Folge hat - der Vorgang beginnt von neuem.
Im Folgenden sollen zwei Beispiele näher betrachtet werden:
3.1.1 Die Fakultätsfunktion
Die Glieder der Fakultätsfunktion erhält man, indem man alle ganzen Zahlen von 1 bis inklusive der Nummer des zu berechnenden Gliedes multipliziert. So ergibt sich für das dritte Glied zum Beispiel 6, für das fünfte schon 120. Die Fakultätsfunktion läßt sich leicht in der rekursiven Form darstellen: an = n * a(n-1), wobei das erste Glied den Wert Eins besitzt. Auf diesem Bildungsgesetz basiert das folgende Programm:
program fakultaet;
uses crt;
var i : integer;
function fakt(n : integer) : real;
begin
if n=1 then fakt:=1 else fakt:=fakt(n-1)*n;
end;
begin
clrscr;
writeln(\' Fakultätsberechnungsprogramm von Stefan Krywult\');
write(\'n = \');
readln(i);
writeln(i,\'! = \',fakt(i));
readln;
clrscr;
end.
Zunächst gibt der Benützer die Zahl ein, deren Fakultät berechnet werden soll. Sie wird in der Integervariablen i zwischengespeichert und dann der rekursiven Funktion fakt als mit n bezeichneter Parameter übergeben. Nun beginnt eine rekursive Schleife: Solange n größer als eins ist, erfolgen Selbstaufrufe, und die Werte, welche die Funktion dabei zurückliefert, werden mit dem jeweils gültigen n multipliziert. Ist n gleich eins, wird der Funktion der Wert Eins zugewiesen.
Nun folgt der genaue Ablauf der Rekursion, wenn als Startparameter Drei übergeben wurde:
Rekursionsebene: 1 n = 3 n 1 fakt := fakt(2)*3
Rekursionsebene: 2 n = 2 n 1 fakt := fakt(1)*2
Rekursionsebene: 3 n = 1 n = 1 fakt := 1
Rekursionsebene: 2 n = 2 n 1 fakt := 1*2 fakt := 2
Rekursionsebene: 1 n = 3 n 1 fakt := 2*3 fakt := 6 => fakt(3) = 6
3.1.2 Die Ackermann-Funktion
Wesentlich schwerer ist es, die Ackermann-Funktion zu berechnen. Sie ist eine zweidimensionale Funktion, das heißt, sie benötigt zwei Parameter. Ihr Bildungsgesetz sieht so aus:
n + 1 für m = 0, n > 0
A(m,n) = A(m-1, 1) für m > 0, n = 0
A(m-1, A(m, n-1)) für m > 0, n > 0
Doch auch diese Funktion läßt sich fast nach dem selben Schema wie die Fakultätsfunktion programmieren: Zuerst muß ermittelt werden, welcher der drei Fälle vorliegt (bei der Fakultät waren es nur zwei: n=1 oder n>1). Dann erfolgt entweder ein Selbstaufruf mit den entsprechenden Parametern oder die einfache Berechnung A=n+1.
Mit folgender Pascalfunktion lassen sich Werte der Ackermann-Funktion berechnen, der restliche Programmcode kann dem Anhang entnommen werden (A1, "ackermann"):
function ack(m, n : integer) : integer;
begin
If (m=0) and (n>0) then ack := n+1
If (m>0) and (n=0) then ack := ack(m-1,1);
If (m>0) and (n>0) then ack := ack(m-1, ack(m,n-1));
end;
Der Rekursionsablauf ist bei dieser Funktion nur schwer zu durchschauen, da sie sich oftmals sogar zweimal selbst aufruft: Sie ruft sich auf, um den Parameter für den eigentlichen Selbstaufruf zu erhalten. Da die Wahrscheinlichkeit, daß beide Parameter größer als Eins sind, ziemlich groß ist, verzweigt sich die Funktion häufig.
Das heißt: Die Funktion ruft sich zweimal auf, diese beiden Funktionen rufen sich wieder zweimal auf und so weiter. Die Zahl der Selbstaufrufe wächst daher stetig. Die rekursive Berechnung der Ackermann-Funktion ist deshalb sehr zeit- und speicherintensiv. Hier wäre es günstiger, die wesentlich schwierigere, aber zeit- und speichersparende iterative Variante zu wählen.
Um den komplizierten Ablauf der Funktionsberechnung zu zeigen, folgt nun die Beschreibung des Ablaufes nach dem Funktionsaufruf ack(1, 1):
Rekursionsebene: 1 m = 2 n = 1 m > 0 n > 0 ack := ack(1, ack(2,0))
Rekursionsebene: 2 m = 2 n = 0 m > 0 n = 0 ack := ack(1, 1)
Rekursionsebene: 3 m = 1 n = 1 m > 0 n > 0 ack := ack(0,ack(1,0))
Rekursionsebene: 4 m = 1 n = 0 m > 0 n = 0 ack := ack(0,1)
Rekursionsebene: 5 m = 0 n = 1 m = 0 n > 0 ack := 1+1 ack := 2
Rekursionsebene: 4 m = 1 n = 0 m > 0 n = 0 ack := 2
Rekursionsebene: 3 m = 1 n = 1 m > 0 n > 0 ack := ack(0, 2);
Rekursionsebene: 4 m = 0 n = 2 m = 0 n > 0 ack := 2 + 1 ack := 3
Rekursionsebene: 3 m = 1 n = 1 m > 0 n > 0 ack := 3
Rekursionsebene: 2 m = 2 n = 0 m > 0 n > 0 ack := 3
Rekursionsebene: 1 m = 2 n = 1 m > 0 n > 0 ack := ack(1, 3)
Rekursionsebene: 2 m = 1 n = 3 m > 0 n > 0 ack := ach(0, ack(1, 2))
Rekursionsebene: 3 m = 1 n = 2 m > 0 n > 0 ack := ach(0, ack(1, 1))
Rekursionsebene: 4 m = 1 n = 1 m > 0 n > 0 ack := ach(0, ack(1, 0))
Rekursionsebene: 5 m = 1 n = 0 m > 0 n = 0 ack := ach(0, 1)
Rekursionsebene: 6 m = 0 n = 1 m = 0 n > 0 ack := 1+1 ack := 2
Rekursionsebene: 5 m = 1 n = 0 m > 0 n = 0 ack := 2
Rekursionsebene: 4 m = 1 n = 1 m > 0 n > 0 ack := ach(0, 2)
Rekursionsebene: 5 m = 0 n = 2 m = 0 n > 0 ack := 2 + 1 ack := 3
Rekursionsebene: 4 m = 1 n = 1 m > 0 n > 0 ack := 3
Rekursionsebene: 3 m = 1 n = 2 m > 0 n > 0 ack := ach(0, 3)
Rekursionsebene: 4 m = 0 n = 3 m > 0 n > 0 ack := 3 + 1 ack := 4
Rekursionsebene: 3 m = 1 n = 2 m > 0 n > 0 ack := 4
Rekursionsebene: 2 m = 0 n = 3 m > 0 n > 0 ack := ach(0, 4)
Rekursionsebene: 3 m = 0 n = 4 m = 0 n > 0 ack := 4 +1 ack := 5
Rekursionsebene: 2 m = 0 n = 3 m > 0 n > 0 ack := 5
Rekursionsebene: 1 m = 2 n = 1 m > 0 n > 0 ack := 5
|
