Rekursive Programmierung
Bei der rekursiven Programmierung ruft sich eine Prozedur, Funktion oder Methode in einem Computerprogramm selbst wieder auf (d. h. enthält eine Rekursion). Auch der gegenseitige Aufruf stellt eine Rekursion dar.
Wichtig bei der rekursiven Programmierung ist eine Abbruchbedingung in dieser Funktion, weil sich das rekursive Programm sonst theoretisch unendlich oft selbst aufrufen würde.
Rekursive Programmierung kann unter anderem in prozeduralen und objektorientierten Programmiersprachen angewandt werden. Obwohl diese Sprachen in ihrem Sprachstandard die Rekursion ausdrücklich zulassen, stellen Selbstaufrufe und gegenseitige Aufrufe hier (aufgrund der verwendeten Programmierparadigmen) jedoch eher die Ausnahme dar. Auch wenn in der Praxis zur Verbesserung des Programmierstils auch hier durchaus häufig auf Rekursion zurückgegriffen wird, sind die meisten Funktionen in diesen Sprachen doch 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.
Beispiele
Fakultät
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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1 \cdot 2 \cdot 3 \cdot 4 = 24} .
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.
Die Definition funktioniert so:
- 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
- Die Fakultät von 2 ist also 1*1*2=2
- Die Fakultät von 3 ist also 1*1*2*3=6
- Die Fakultät von 4 ist also 1*1*2*3*4=24
In einer Programmiersprache wie Pascal, die rekursive Programmierung zulässt, kann man die Fakultät folgendermaßen eingeben:
Man definiert eine Funktion factorial, die eine Zahl x als Eingabewert bekommt. Diese Funktion multipliziert x mit dem Rückgabewert von factorial(x - 1) außer bei x = 0, dann liefert die Funktion das Ergebnis 1. Dies ist die Abbruchbedingung:
Rekursive Implementation der Fakultätsfunktion
function factorial(x: Integer): Integer;
begin
if x = 0 then
factorial := 1
else
factorial := x * factorial(x - 1);
end;
Mit der Startzahl x = 4 würde der Computer rechnen:
4 * (3 * (2 * (1 * factorial(0))))
heraus kommt dann das richtige Ergebnis, nämlich 24.
Binäre Suche
Die binäre Suche in einem Array lässt sich rekursiv implementieren. Wenn das mittlere Element kleiner als das gesuchte Element ist, wird die hintere Hälfte des Arrays rekursiv durchsucht. Wenn es größer als das gesuchte Element ist, wird die vordere Hälfte des Arrays rekursiv durchsucht. Ist es gleich dem gesuchten Element, ist die Suche beendet.
Die Abbruchbedingung für die Rekursion ist erfüllt, wenn das mittlere Element gleich dem gesuchten Element ist, die Suche also erfolgreich ist, oder wenn der Endindex kleiner als der Startindex ist, die Suche also erfolglos ist.
Die folgende Funktion (Methode) für die rekursive binäre Suche ist in der Programmiersprache C#:
int RekursiveBinaereSuche(int[] werte, int gesuchterWert, int startIndex, int endIndex)
{
if (endIndex < startIndex)
{
// Wenn Element nicht gefunden, dann null zurückgeben
return null;
}
int mittlererIndex = (startIndex + endIndex) / 2;
if (werte[mittlererIndex] == gesuchterWert)
{
// Wenn Element gefunden, dann Index zurückgeben
return mittlererIndex;
}
else
{
if (werte[mittlererIndex] < gesuchterWert)
{
// Rekursiver Aufruf der Funktion für die hintere Hälfte
return RekursiveBinaereSuche(werte, gesuchterWert, mittlererIndex + 1, endIndex);
}
else
{
// Rekursiver Aufruf der Funktion für die vordere Hälfte
return RekursiveBinaereSuche(werte, gesuchterWert, startIndex, mittlererIndex - 1);
}
}
}
Effizienz
Rekursive Programme haben in der Regel keine gute Performance. Durch die wiederholten Funktionsaufrufe (Inkarnationen) wird immer wieder derselbe Methodeneintrittscode bearbeitet und bei jeder Inkarnation der Kontext gesichert, was zu zusätzlichem Programmcode und höherem Arbeitsspeicherverbrauch führt. Alle rekursiven Algorithmen lassen sich jedoch auch durch iterative Programmierung implementieren und umgekehrt.
Fakultät
Man hätte die Fakultät auch so implementieren können:
function factorial(x: Integer): Integer;
var i, number: Integer;
begin
number := 1;
for i := 1 to x do
number := number * i;
factorial := number;
end;
Hierbei gilt die Regel, dass für einfache Probleme eine iterative Implementierung häufig effizienter ist. So sollte z. B. auch die Fakultätsfunktion der Effizienz wegen in der Praxis iterativ implementiert werden. Bei komplizierten Problemstellungen (z. B. Aufgaben mit Bäumen) hingegen lohnt sich oftmals der Einsatz einer rekursiven Lösung, da für solche Probleme eine iterative Formulierung schnell sehr unübersichtlich – und ineffizient – werden kann, da im schlimmsten Fall der Stack durch den iterativen Algorithmus selbst verwaltet werden muss, was sonst der Prozessor direkt erledigt.
Nicht alle höheren Programmiersprachen lassen rekursive Aufrufe zu. Ein Beispiel dazu ist Fortran. Andere Programmiersprachen sind dagegen grundsätzlich rekursiv (wie z. B. Prolog). Solche rekursiven Programmiersprachen und auch andere Sprachen wie z. B. Scheme setzen die Rekursion meistens effizient um.
Implementierung
Rekursion wird in der Regel durch einen Stack implementiert, der die Rücksprungadressen, aber auch alle lokalen Variablen und eventuell Funktionsergebnisse aufnimmt. Würde man, wie im obenstehenden Beispiel, die Fakultät von 4 berechnen, so würde jeder Aufruf folgende Informationen auf den Stack 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 Stack gelegt:
| Stapelanfang | Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \rightarrow} | 1 | Platz für Ergebnis |
| 2 | 4 (Argument) | ||
| Stapelzeiger | Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \rightarrow} | 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 | Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \rightarrow} | 1 | Platz für Ergebnis |
| 2 | 4 (Argument) | ||
| 3 | Rücksprungadresse ins Hauptprogramm | ||
| 4 | Platz für Ergebnis | ||
| 5 | 3 (Argument) | ||
| Stapelzeiger | Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \rightarrow} | 6 | Rücksprungadresse in die Fakultätsfunktion |
Das Argument ist wieder ungleich 0, also geht's weiter mit 3*fac(2).
| Stapelanfang | Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \rightarrow} | 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 | Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \rightarrow} | 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 | Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \rightarrow} | 12 | Rücksprungadresse in die Fakultätsfunktion |
Das Argument ist wieder ungleich 0, also1*fac(0).
| Stapelanfang | Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \rightarrow} | 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 | Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \rightarrow} | 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 Stack und schreiben die 1 in den dafür vorgesehenen Platz. Der Rücksprung führt in die Fakultätsfunktion zurück:
| Stapelanfang | Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \rightarrow} | 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 | Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \rightarrow} | 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 Stack geholt und das neue Ergebnis in den dafür vorgesehenen Platz geschrieben. Rücksprung in die Fakultätsfunktion:
| Stapelanfang | Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \rightarrow} | 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 | Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \rightarrow} | 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 | Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \rightarrow} | 7 | 2 (Ergebnis) |
Das Ergebnis wird mit dem Argument multipliziert (2*3). Zurück in die Fakultätsfunktion:
| Stapelanfang | Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \rightarrow} | 1 | Platz für Ergebnis |
| 2 | 4 (Argument) | ||
| 3 | Rücksprungadresse ins Hauptprogramm | ||
| Stapelzeiger | Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \rightarrow} | 4 | 6 (Ergebnis) |
Das Ergebnis wird mit dem Argument multipliziert (6*4). Zurück ins Hauptprogramm
| Stapelanfang Stapelzeiger |
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \rightarrow} | 1 | 24 (Ergebnis) |
Das Hauptprogramm muss dann nur noch das Ergebnis 24 vom Stack holen.
