Rekursive Programmierung
Bei der rekursiven Programmierung ruft sich eine Prozedur, Funktion oder Methode in einem Computerprogramm selbst wieder auf. Auch der gegenseitige Aufruf stellt eine Rekursion dar. Wichtig dabei ist eine Abbruchbedingung in dieser Funktion, weil sich das rekursive Programm sonst (theoretisch) bis in alle Ewigkeit selbst aufrufen würde. Die rekursive Programmierung findet oft Anwendung in prozeduralen und objektorientierten Programmiersprachen. Obwohl diese Sprachen in ihrem Sprachstandard die Rekursion ausdrücklich zulassen, stellen Selbstaufrufe und gegenseitige Aufrufe bei der Programmierung die Ausnahme dar. Die meisten Programme in diesen Sprachen sind rein iterativ.In einigen Sprachen, wie z. B. in manchen funktionalen Programmiersprachen oder Makroprozessoren, muss die rekursive Programmiermethode zwingend verwendet werden, da iterative Sprachkonstrukte fehlen.
Ein Beispiel für die Verwendung einer rekursiven Programmierung ist die Berechnung der Fakultät einer Zahl. Die Fakultät ist das Produkt aller ganzen Zahlen von 1 bis zu dieser Zahl. Die Fakultät von 4 ist also .
Mathematiker definieren die Fakultät meistens so (eine rekursive Definition):
- Die Fakultät der Zahl 0 ist definitionsgemäß 1.
- Die Fakultät einer ganzen Zahl, die größer als Null ist, ist das Produkt dieser Zahl mit der Fakultät der nächstkleineren ganzen Zahl.
- Will man die Fakultät von 4 berechnen, so muss man zunächst die Fakultät von 3 berechnen und das Ergebnis mit 4 multiplizieren.
- Will man die Fakultät von 3 berechnen, so muss man zunächst die Fakultät von 2 berechnen und das Ergebnis mit 3 multiplizieren.
- Will man die Fakultät von 2 berechnen, so muss man zunächst die Fakultät von 1 berechnen und das Ergebnis mit 2 multiplizieren.
- Will man die Fakultät von 1 berechnen, so muss man zunächst die Fakultät von 0 berechnen und das Ergebnis mit 1 multiplizieren.
- Die Fakultät von 0 ist nach Definition 1.
- Die Fakultät von 1 ist also 1*1=1
- Will man die Fakultät von 1 berechnen, so muss man zunächst die Fakultät von 0 berechnen und das Ergebnis mit 1 multiplizieren.
- Die Fakultät von 2 ist also 2*1=2
- Will man die Fakultät von 2 berechnen, so muss man zunächst die Fakultät von 1 berechnen und das Ergebnis mit 2 multiplizieren.
- Die Fakultät von 3 ist also 3*2=6
- Will man die Fakultät von 3 berechnen, so muss man zunächst die Fakultät von 2 berechnen und das Ergebnis mit 3 multiplizieren.
- Will man die Fakultät von 4 berechnen, so muss man zunächst die Fakultät von 3 berechnen und das Ergebnis mit 4 multiplizieren.
- Die Fakultät von 4 ist also 4*6=24
Man definiert eine Funktion fac, die eine Zahl x als Eingabewert bekommt. Diese Funktion multipliziert x mit dem Rückgabewert von fac(x-1) außer x=0, dann liefert die Funktion das Ergebnis 1. Dies ist die Abbruchbedingung:
Rekursive Implementation der Fakulätsfunktion
function fac(x : Integer): Integer; begin if x = 0 then fac := 1 else fac := x * fac(x - 1); end;Mit der Startzahl x=4 würde der Computer rechnen:
heraus kommt dann das richtige Ergebnis, nämlich 24.
Rekursive Programme haben keine gute Performance. Durch die wiederholten Funktionsaufrufe wird immer wieder derselbe Methodeneintrittscode bearbeitet und jedesmal der Kontext gesichert, was zu hohem Arbeitsspeicherverbrauch führt. Die meisten rekursiven Algorithmen lassen sich jedoch durch iterative Programmierung implementieren. Man hätte die Fakultät auch so implementieren können:
Iterative Implementation der Fakulätsfunktion
function fac(x : Integer): Integer; var i, Ergebnis: Integer; begin Ergebnis:=1; for i:=1 to x do Ergebnis:=Ergebnis*i; fac:=Ergebnis; end;
Nicht alle höheren Programmiersprachen lassen rekursive Aufrufe zu; ein Beispiel dazu ist Fortran.
Implementation
Rekursion wird in der Regel durch einen Stack implementiert, der die Rücksprungadressen, aber auch alle lokalen Variablen und evtl. Funktionsergebnisse aufnimmt. Würde man, wie im obenstehenden Beispiel, die Fakultät von 4 berechnen, so würde jeder Aufruf folgende Informationen auf den Stapel legen:
- Platz für Ergebnis
- Argument x
- Rücksprungadresse
Zunächst würde im Hauptprogramm also fac(4) aufgerufen und damit die folgenden Informationen auf den Stapel gelegt:
Stapelanfang | 1 | Platz für Ergebnis | |
2 | 4 (Argument) | ||
Stapelzeiger | 3 | Rücksprungadresse ins Hauptprogramm |
Die Fakultätsfunktion prüft jetzt, ob das Argument 0 ist. Da dies nicht der Fall ist, wird 4*fac(3) berechnet. Zunächst muss also fac mit dem Argument 3 aufgerufen werden:
Stapelanfang | 1 | Platz für Ergebnis | |
2 | 4 (Argument) | ||
3 | Rücksprungadresse ins Hauptprogramm | ||
4 | Platz für Ergebnis | ||
5 | 3 (Argument) | ||
Stapelzeiger | 6 | Rücksprungadresse in die Fakultätsfunktion |
Das Argument ist wieder ungleich 0, also geht's weiter mit 3*fac(2).
Stapelanfang | 1 | Platz für Ergebnis | |
2 | 4 (Argument) | ||
3 | Rücksprungadresse ins Hauptprogramm | ||
4 | Platz für Ergebnis | ||
5 | 3 (Argument) | ||
6 | Rücksprungadresse in die Fakultätsfunktion | ||
7 | Platz für Ergebnis | ||
8 | 2 (Argument) | ||
Stapelzeiger | 9 | Rücksprungadresse in die Fakultätsfunktion |
Das Argument ist wieder ungleich 0, also2*fac(1).
Stapelanfang | 1 | Platz für Ergebnis | |
2 | 4 (Argument) | ||
3 | Rücksprungadresse ins Hauptprogramm | ||
4 | Platz für Ergebnis | ||
5 | 3 (Argument) | ||
6 | Rücksprungadresse in die Fakultätsfunktion | ||
7 | Platz für Ergebnis | ||
8 | 2 (Argument) | ||
9 | Rücksprungadresse in die Fakultätsfunktion | ||
10 | Platz für Ergebnis | ||
11 | 1 (Argument) | ||
Stapelzeiger | 12 | Rücksprungadresse in die Fakultätsfunktion |
Das Argument ist wieder ungleich 0, also1*fac(0).
Stapelanfang | 1 | Platz für Ergebnis | |
2 | 4 (Argument) | ||
3 | Rücksprungadresse ins Hauptprogramm | ||
4 | Platz für Ergebnis | ||
5 | 3 (Argument) | ||
6 | Rücksprungadresse in die Fakultätsfunktion | ||
7 | Platz für Ergebnis | ||
8 | 2 (Argument) | ||
9 | Rücksprungadresse in die Fakultätsfunktion | ||
10 | Platz für Ergebnis | ||
11 | 1 (Argument) | ||
12 | Rücksprungadresse in die Fakultätsfunktion | ||
13 | Platz für Ergebnis | ||
14 | 0 (Argument) | ||
Stapelzeiger | 15 | Rücksprungadresse in die Fakultätsfunktion |
Jetzt ist das Argument 0, das Ergebnis also 1. Wir holen die Rücksprungadresse und das Argument vom Stapel und schreiben die 1 in den dafür vorgesehen Platz. Der Rücksprung führt in die Fakultätsfunktion zurück:
Stapelanfang | 1 | Platz für Ergebnis | |
2 | 4 (Argument) | ||
3 | Rücksprungadresse ins Hauptprogramm | ||
4 | Platz für Ergebnis | ||
5 | 3 (Argument) | ||
6 | Rücksprungadresse in die Fakultätsfunktion | ||
7 | Platz für Ergebnis | ||
8 | 2 (Argument) | ||
9 | Rücksprungadresse in die Fakultätsfunktion | ||
10 | Platz für Ergebnis | ||
11 | 1 (Argument) | ||
12 | Rücksprungadresse in die Fakultätsfunktion | ||
Stapelzeiger | 13 | 1 (Ergebnis) |
Jetzt kann man das Ergebnis mit dem Argument multiplizieren (1*1). Das neue Ergebnis ist wieder 1. Die Rücksprungadresse und das Argument werden vom Stapel geholt und das neue Ergebnis in den dafür vorgesehenen Platz geschrieben. Rücksprung in die Fakultätsfunktion:
Stapelanfang | 1 | Platz für Ergebnis | |
2 | 4 (Argument) | ||
3 | Rücksprungadresse ins Hauptprogramm | ||
4 | Platz für Ergebnis | ||
5 | 3 (Argument) | ||
6 | Rücksprungadresse in die Fakultätsfunktion | ||
7 | Platz für Ergebnis | ||
8 | 2 (Argument) | ||
9 | Rücksprungadresse in die Fakultätsfunktion | ||
Stapelzeiger | 10 | 1 (Ergebnis) |
Wiederum wird das Ergebnis mit dem Argument multipliziert (1*2). Zurück in die Fakultätsfunktion:
Stapelanfang | 1 | Platz für Ergebnis | |
2 | 4 (Argument) | ||
3 | Rücksprungadresse ins Hauptprogramm | ||
4 | Platz für Ergebnis | ||
5 | 3 (Argument) | ||
6 | Rücksprungadresse in die Fakultätsfunktion | ||
Stapelzeiger | 7 | 2 (Ergebnis) |
Das Ergebnis wird mit dem Argument multipliziert (2*3). Zurück in die Fakultätsfunktion:
Stapelanfang | 1 | Platz für Ergebnis | |
2 | 4 (Argument) | ||
3 | Rücksprungadresse ins Hauptprogramm | ||
Stapelzeiger | 4 | 6 (Ergebnis) |
Das Ergebnis wird mit dem Argument multipliziert (6*4). Zurück ins Hauptprogramm
Stapelanfang Stapelzeiger | 1 | 24 (Ergebnis) |
Das Hauptprogramm muss dann nur noch das Ergebnis 24 vom Stapel holen.
Siehe auch: Quicksort