|
Bei der rekursiven Definition von Folgen, die im vorigen Kapitel beschrieben wurde, ist es notwendig, das erste Glied a1 absolut zu bestimmen, indem man ihm einen Zahlenwert zuweist. Auch bei der Programmierung rekursiver Unterprogramme muß es eine Abbruchbedingung geben, bei der die Rekursion stoppt und kein neuerlicher Selbstaufruf mehr erfolgt. Beim Fehlen einer Abbruchbedingung ruft sich das Unterprogramm so lange selbst auf, bis der Stack-Speicher erschöpft ist. In der Folge kommt es zu einer Fehlermeldung, dem sogenannten Stack-Overflow.
Wird ein rekursives Unterprogramm aufgerufen, erfolgt ein Push-Vorgang und Daten werden auf den Stack gelegt. Dann werden die Befehle bis zum Selbstaufruf ausgeführt. Dies wird "rekursiver Aufstieg" genannt. Ist die Abbruchbedingung noch nicht erreicht, erfolgt ein Selbstaufruf. Erneut werden Daten auf dem Stack abgelegt.
So entwickelt sich Schritt für Schritt eine Datenstruktur auf dem Stack. Bis jetzt wurde nur der rekursive Aufstieg ausgeführt. Tritt jedoch die Abbruchbedingung in Kraft, erfolgt der "rekursive Abstieg", bei dem die Befehle nach dem Selbstaufruf ausgeführt werden. Nach Beendigung des Unterprogrammes werden Daten vom Stack geholt. Es erfolgt ein schrittweises Auflösen der zuvor gebildeten Datenstruktur. Der rekursive Abstieg endet mit dem Rücksprung ins Hauptprogramm.
Die Anzahl der Selbstaufrufe nennt man "Rekursionstiefe."
Folgendes Beispielprogramm soll zur Veranschaulichung des Rekursionsablaufes dienen:
program rekursion01;
uses crt;
var i : integer;
procedure zaehl(von:integer); {rekursive Prozedur mit dem Parameter von}
begin
write(von,\' \'); {Variable von am Bildschirm ausgeben - Rekursionsaufstieg}
if von>0 then zaehl(von-1); {Abbruchbedingung und Selbstaufruf}
write(von,\' \'); {Variable von am Bildschirm ausgeben-Rekursionsabstieg}
end;
begin
clrscr;
write(\'Rekursionstiefe: \');
readln(i);
zaehl(i); {erstmaliger Aufruf mit dem zuvor eingegebenen Wert i}
readln;
clrscr;
end.
Dieses Beispielprogramm gibt, wenn als Rekursionstiefe 6 eingegeben wurde, Folgendes am Bildschirm aus:
6 5 4 3 2 1 0 0 1 2 3 4 5 6
aufsteigende absteigende Rekursion
Um den Rekursionsablauf zu beschreiben, wird nur 3 als Eingabe für die Rekursiontiefe angenommen, damit sich die Länge der Beschreibung in Grenzen hält. Wird die Prozedur zaehl mit dem Wert 3 aufgerufen, so wird zunächst die Zahl Drei am Bildschirm ausgegeben. Anschließend kommt es zu einem Selbstaufruf, da die Rekursionsbedingung erfüllt ist (Drei ist größer als Null). Als Parameter wird der eigene Parameter, um Eins verringert, übergeben. Für den neuen Prozeduraufruf werden neue lokale Variable auf dem Stack abgelegt, die der aufrufenden Prozedur bleiben jedoch auf dem Stack erhalten, da diese noch nicht beendet wurde. Hierauf wird die Zahl Zwei ausgegeben, und es kommt erneut zum Selbstaufruf.
Dieser Ablauf setzt sich so lange fort, bis die Prozedur zaehl mit Null als Parameter aufgerufen wird. Auch Null wird am Bildschirm ausgegeben, aber es kommt zu keinem weiteren Selbstaufruf, da die Rekursionsbedingung nicht mehr erfüllt ist (Null ist nicht größer als Null), und der Rekursionsabstieg beginnt. Der Programmablauf wird mit dem nächsten Befehl der Prozedur fortgesetzt, und Null wird nochmals am Bildschirm ausgegeben. Dann wird das Unterprogramm beendet, die lokalen Variablen vom Stack entfernt und zur aufrufenden Prozedur zurückgekehrt. Hier hat die Variable von den Wert Eins. Die Zahl Eins wird daher ausgegeben und das Unterprogramm beendet. Wieder werden die lokalen Variablen vom Stack gelöscht und die Programmausführung mit der aufrufenden Prozedur fortgesetzt, in der die Variable von den Wert Zwei besitzt.
Nach der Ausgabe der Zahlen Zwei und Drei erfolgt schließlich der Rücksprung ins Hauptprogramm - die Rekursion ist beendet.
Bei jedem Aufruf der Prozedur zaehl wird für die Variable von neuer Speicherplatz belegt, sie ist daher jeweils nur auf einer Rekursionstufe gültig, d.h. auf jeder Rekursionsstufe bezeichnet die Variable von eine andere Stelle im Speicher. Um die Push- und Pop-Vorgänge muß sich der Programmierer in Pascal nicht selbst kümmern. Der Stack wird automatisch vom Compiler verwaltet. Um die compilerinterne Verwaltung des Stack zu veranschaulichen, habe ich das obige Programm so verändert, daß nicht nur die Variablenwerte, sondern auch deren Speicheradressen angegeben werden. Außerdem wird die Adresse des Stack vor und nach dem Durchlaufen der Rekursion angezeigt. Den genauen Quellcode kann man dem Anhang entnehmen (A1, "rekursion01tx"). Die Ausgabe des Programms sieht ungefähr so aus:
Vor dem Prozeduraufruf: Stacksegment: 29031 Stackpointer: 16378
von: Wert: 3 Adresse: 29031:16380 Stackpointer: 16372
von: Wert: 2 Adresse: 29031:16374 Stackpointer: 16366
von: Wert: 1 Adresse: 29031:16368 Stackpointer: 16360
von: Wert: 0 Adresse: 29031:16362 Stackpointer: 16354
von: Wert: 0 Adresse: 29031:16362 Stackpointer: 16354
von: Wert: 1 Adresse: 29031:16368 Stackpointer: 16360
von: Wert: 2 Adresse: 29031:16374 Stackpointer: 16366
von: Wert: 3 Adresse: 29031:16380 Stackpointer: 16372
Nach dem Prozeduraufruf: Stacksegment: 29031 Stackpointer: 16378
Die maximale Größe des Stack beträgt 16 Kilobyte, und er wird von der höchsten bis zur niedrigsten Adresse gefüllt. Daher wird die Adresse des Stack-Endes, auf das der Stackpointer zeigt, mit jedem Prozeduraufruf kleiner.
|
