Zur Themenübersicht

Rekursive Algorithmen

Unter Rekursion versteht man den Vorgang, dass Prozeduren oder Funktionen sich ,während ihrer Ausführung, selbst Aufrufen. Auf diese Weise, wird Programmquelltext kürzer und viele Variablenzuweisungen werden gespart. Außerdem fallen häufig Schleifen weg.

Rekursive Formulierung des ggt-Algorithmus als Funktion und als Prozedur:

Als Beispiel für die pratktische Anwendung der Rekursion, dient der bereits bekannte Euklidische(ggt)-Algorithmus.

1.1 Die rekursive ggt-Procedur

Die Deklaration einer rekursiven Procedur 
unterscheidet sich in keiner Weise von der
einer normalen Procedur.

Der eigentliche ggt-Algorithmus benötigt,
dank der Rekursion, keine Schleife mehr. Die
Abbruch Bedingung, dass der Rest = 0 sein muss,
steht in der If Abfrage. Wenn das der Fall ist,
wir dem Referenzparameter ggtlok das Ergebniss
(blok) zugewiesen.

Für den Else-Fall, tritt die Rekursion ein. 
Erklärung, siehe unten.

procedure berechneggt(alok,blok :Integer; var ggtlok :Integer);
var rest :Integer;
begin

    if (alok mod blok) = 0
      then ggtlok := blok

      else berechneggt (blok,alok mod blok,ggtlok);
end;

Der eigentliche Clou liegt in der rechts
dargestellten Zeile. An dieser Stelle, setzt 
die Rekursion ein. Die Procedur ruft sich selbst
auf. In der Speicherverwaltung wird eine reele 
neue Instanz der Procedur berechneggt erstellt.
Das Umbennen der Variablen und die "mod" berechnung
in der nicht rekursiven Procedur, wird hier dadurch
ersetzt, dass die Werte an den richtigen Stellen in
der aktuellen ParameterListe eingesetzt werden.
Die neue "Version" der berechneggt Procedur hat die
selbe Funktionsweise wie ihre erste Instanz.
Erst wenn die If-Abfrage true ergibt, wird keine neue
Instanz von berechneggt erstellt. Was man auch als  
größte Rekursionstiefe bezeichnet.

berechneggt (blok,alok mod blok,ggtlok);

1.2 Die rekursive ggt-Funktion

Auch die Deklaration einer rekursiven Funktion 
unterscheidet sich nicht von der Normalform.

Der Algorithmus selbst ist von der Logik her
vollkommen gleich aufgebaut:

Die If-Abfrage ist wiederum die Abbruchbedingung für
die Rekursionstiefe. Wenn der Rest 0 ist, wird das
Ergebniss (blok) durch den Funktionsnamen (ggt)
ausgegeben.

Die Rekursion funktioniert genau wie bei der Procedur.

function ggt (alok,blok :integer) :integer;

begin
if (alok mod blok) = 0
    then ggt := blok;

    else result := ggt (blok,alok mod blok);
end;

Der große Unterschied zwischen den beiden Methoden, 
liegt in der Art der Rückgabe des Ergebnisses.

Die Proceduren (Mehrzahl, da Rekursion) geben das
Ergebniss durch den Referenzparameter "ggtlok" direkt
zurück.

Die Funktionen hingegen, geben ihr Ergebniss ganz 
normal durch result an die Stelle ihres Aufrufes
zurück. Dadurch, dass erst die letzte Funktion, also
die bei der größten Rekursionstiefe einen reelen wert
zurück gibt, wird der Wert sozusagen durchgereicht,  
bis er an Stelle angelangt, wo die funktion ggt zu   
ersten mal aufgerufen wurde.

Das ändert am Ergebniss jedoch nichts.

procedure berechneggt(alok,blok :Integer; var ggtlok :Integer);

result := ggt (blok,alok mod blok);

Abschließend ist zu sagen, dass Rekursionen zwar schwieriger zu verstehen sind, jedoch viel zeitraubende Tipparbeit ersparen.

Zur Themenübersicht
Zum Seitenanfang
Zur vorigen Seite	Zur nächsten Seite

Hannah-Arendt-Gymnasium, Lengerich