Referat Die Rekursion als mathematisches Verfahren

Die Rekursion als mathematisches Verfahren

In der Mathematik gibt es zwei grundlegend verschiedene Methoden, das Bildungsgesetz einer bestimmten Folge darzustellen. Bei der expliziten Beschreibung ist es möglich, ein

_{Folgenglied direkt über die Nummer desselben auszurechnen, so zum Beispiel}

Bei der rekursiven Darstellung wird das Glied nicht absolut definiert, sondern es wird nur der

Zusammenhang mit dem vorigen Glied angegeben, so zum Beispiel ^{z a}n ^{= a}(n-1)

Um also das dritte Glied dieser Folge zu erhalten, muß zuerst das zweite ausgerechnet werden.

Das zweite basiert jedoch auf dem ersten. Die Glieder müssen daher schrittweise berechnet werden. Damit der Vorgang beim ersten Glied endet, muß dieses einen festen Wert besitzen, der ebenfalls bei der Definition angegeben werden muß. Das obige Bildungsgesetz lautet daher richtig:

an = a_(n , a

Dadurch wird dieselbe Folge wie oben definiert. Die Länge des Rechenwegs zu einem bestimmten Glied ist proportional zur Höhe der Gliednummer, während sie beim expliziten Bildungsgesetz immer  gleich ist. Hier sind zum Beispiel die Rechenschritte für das dritte Glied:

explizit:             a 1 a

rekursiv:            a =a +2 a =a +2 a =3 a 2 a 2+2 a

Trotz ihrer Länge ist die rekursive Darstellung oft nützlicher, da sie meistens einfacher ist und

_{mit ihr manche Rechenarten gezielt umgangen werden können:}

/ 1

an = x*n => an = a(n-1)+x an = x^n => an = a(n-1)*x an = n! => an = a(n-1)*n

Abschließend ist zu bemerken, daß die Bildungsgesetze der meisten Folgen auf beide Arten darstellbar sind. Bei manchen ist dies jedoch nicht möglich.

2 Die Realisierung von Rekursionen im Computer

Rekursive Verfahren sind nicht nur in der Mathematik, sondern auch in der Informatik von großer Bedeutung. Sie werden nicht nur zum Errechnen rekursiver Folgen, die zum Beispiel bei der Darstellung von Wachstumsprozessen oder Fraktalen Anwendung finden, sondern auch zum schrittweisen und effektiven Lösen komplizierter und langwieriger Aufgaben (zum Beispiel bei Sortieralgorithmen oder Backtrackingprogrammen) verwendet.

Während früher solche Verfahren auch wirklich rekursiv programmiert wurden, werden sie heute meistens in einer leichter verständlichen iterativen, d.h. nicht rekursiven, Form verwirklicht, was es Programmierern wesentlich erleichtert, sich in Programmen ihrer Kollegen zurechtzufinden.

In diesem Kapitel wird anhand der Programmiersprache Pascal die Programmierung und die Funktionsweise rekursiver Programme erklärt. Dazu muß vorher das modulare Konzept der Programmiersprache Pascal, an der die Verwendung rekursiver Verfahren demonstriert werden soll, näher betrachtet werden.

.1 Das modulare Konzept von Pascal

Die Programmiersprache  Pascal ermöglicht die Verwendung von sogenannten Unterprogrammen in Form von Prozeduren und Funktionen. Der einzige Unterschied zwischen den beiden ist, daß Funktionen nach dem Aufruf einen Wert besitzen und

/ 2

Prozeduren nicht. Unterprogramme sind eigenständige Programmabschnitte, die aus dem Hauptprogramm, aber auch aus anderen Unterprogrammen, aufgerufen werden können. Ihre Verwendung ist von großem Vorteil, da sie das Programm übersichtlicher gestalten. So können lange Befehlsketten, die immer wieder vorkommen, durch einen einzigen Befehl, nämlich einen Unterprogrammaufruf, ersetzt werden. Dieser Aufruf wird Call genannt.

Bei einem Call werden auf dem Stack folgende Informationen gespeichert:

die Parameter für das Unterprogramm,

die Rücksprungadresse, d h. die Speicherstelle, an der die Programmausführung nach dem

Durchlaufen des Unterprogrammes fortgesetzt werden soll,

der letzte Inhalt des BP-Registers(),

lokale Variablen, die nur im Unterprogramm Gültigkeit haben,

etwaige Funktionswerte.

Die Verwaltung des Stacks erfolgt nach dem LIFO-Prinzip (Last In - First Out) wobei der zuletzt abgelegte Wert als erstes wieder gelesen wird. Den Vorgang, Daten auf den Stack zu legen, nennt man Push.

Beim Verlassen eines Unterprogrammes ermöglicht die zuvor auf den Stack geschriebene Rücksprungadresse die Rückkehr zum aufrufenden Programmteil (RET . Der Speicherplatz der lokalen Variablen wird wieder freigegeben, und auf dem Stack liegende Werte werden in umgekehrter Reihenfolge wieder abgehoben. Dieser Prozeß wird POP genannt. Vom Stack entfernte Daten sind unwiderruflich gelöscht.

In Pascal ist es möglich, auch aus einem Unterprogramm heraus ein anderes Unterprogramm aufzurufen. Es ist sogar zulässig, daß ein Unterprogramm während seines Ablaufes sich selbst noch einmal aufruft. Diesen Selbstaufruf nennt man Rekursion.

.2 Rekursionen in Pascal

Bei der rekursiven Definition von Folgen, die im vorigen Kapitel beschrieben wurde, ist es notwendig, das erste Glied a 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);

begin

write(von,'  ');

if von>0 then zaehl(von-1);

write(von,'  ');

end;

begin clrscr; write('Rekursionstiefe: '); readln(i);

zaehl(i);                                

readln;

clrscr;

end.

Dieses Beispielprogramm gibt, wenn als Rekursionstiefe 6 eingegeben wurde, Folgendes am

_{Bildschirm aus:}

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 6380 Stackpointer: 163 2 von: Wert: 2 Adresse: 29031 6374 Stackpointer: 163 6 von: Wert: 1 Adresse: 29031 6368 Stackpointer: 163 0 von: Wert: 0 Adresse: 29031 6362 Stackpointer: 163 4 von: Wert: 0 Adresse: 29031 6362 Stackpointer: 16 54 von: Wert: 1 Adresse: 29031 6368 Stackpointer: 163 0 von: Wert: 2 Adresse: 29031 6374 Stackpointer: 163 6 von: Wert: 3 Adresse: 29031 6380 Stackpointer: 163 2

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.