Rekursive Programmierung

Grundprinzip der rekursiven Programmierung

Bei der rekursiven Programmierung ruft sich eine Prozedur, Funktion oder Methode innerhalb eines Computerprogramms selbst wieder auf. Auch ein gegenseitiger Aufruf mehrerer Funktionen zählt als Rekursion.

Entscheidend ist eine Abbruchbedingung. Sie legt fest, wann keine weiteren rekursiven Aufrufe erfolgen. Ohne eine solche Bedingung könnte sich das Programm theoretisch unendlich oft selbst aufrufen.

Rekursive Programmierung ist unter anderem in prozeduralen und objektorientierten Programmiersprachen möglich. Dort sind Selbstaufrufe und gegenseitige Aufrufe wegen der verwendeten Programmierparadigmen eher die Ausnahme; die meisten Funktionen arbeiten rein iterativ. In manchen funktionalen Programmiersprachen oder Makroprozessoren fehlen iterative Sprachkonstrukte, sodass rekursive Programmierung zwingend verwendet werden muss.

Fakultät als rekursives Beispiel

Die Fakultät einer Zahl ist das Produkt aller ganzen Zahlen von 1 bis zu dieser Zahl. Für 4 gilt daher: 1 · 2 · 3 · 4 = 24.

Die rekursive Definition lautet:

• Die Fakultät von 0 ist definitionsgemäß 1.
• Die Fakultät einer ganzen Zahl größer als 0 ist das Produkt dieser Zahl mit der Fakultät der nächstkleineren ganzen Zahl.

Damit wird 4! schrittweise auf kleinere Aufgaben zurückgeführt: 4 · 3!, 3 · 2!, 2 · 1! und 1 · 0!. Wegen der Abbruchbedingung 0! = 1 ergibt sich schließlich 1 · 1 · 2 · 3 · 4 = 24.

In Pascal kann eine Funktion factorial die Zahl n mit factorial(n − 1) multiplizieren. Für n = 0 gibt sie 1 zurück; dies ist die Abbruchbedingung. Für n = 4 entsteht der Ausdruck 4 · (3 · (2 · (1 · factorial(0)))) und damit das Ergebnis 24.

Rekursive binäre Suche

Die binäre Suche wird auf einem vorsortierten Array verwendet. In jedem Schritt wird das mittlere Element mit dem gesuchten Wert verglichen.

• Ist das mittlere Element gleich dem gesuchten Wert, ist die Suche erfolgreich beendet und der mittlere Index wird zurückgegeben.
• Ist es kleiner als der gesuchte Wert, wird rekursiv nur die hintere Hälfte durchsucht.
• Ist es größer, wird rekursiv nur die vordere Hälfte durchsucht.

Die Rekursion endet außerdem erfolglos, wenn der Endindex kleiner als der Startindex ist. Die C#-Methode RekursiveBinaereSuche erhält das Array werte, den gesuchten Wert sowie startIndex und endIndex. Sie berechnet den mittleren Index als (startIndex + endIndex) / 2 und ruft sich anschließend mit dem passenden Teilbereich erneut auf. Bei Erfolg gibt sie den Index zurück, bei erfolgloser Suche null.

Effizienz und Wahl der Methode

Rekursive Programme haben in der Regel keine gute Performance. Die wiederholten Funktionsaufrufe, auch Inkarnationen genannt, bearbeiten erneut den Methodeneintrittscode. Außerdem wird bei jeder Inkarnation der Kontext gesichert. Dadurch entstehen zusätzlicher Programmcode und ein höherer Arbeitsspeicherverbrauch.

Alle rekursiven Algorithmen lassen sich auch iterativ implementieren und umgekehrt. Für einfache Probleme ist eine iterative Implementierung häufig effizienter. Die Fakultätsfunktion sollte der Effizienz wegen in der Praxis iterativ umgesetzt werden, zum Beispiel mit einer Schleife, die eine Variable number zunächst auf 1 setzt und sie für i von 1 bis x wiederholt mit i multipliziert.

Bei komplizierten Problemstellungen, etwa Aufgaben mit Bäumen, kann eine rekursive Lösung übersichtlicher sein. Eine iterative Formulierung kann dort schnell unübersichtlich und ineffizient werden, weil im schlimmsten Fall der Stack durch den iterativen Algorithmus selbst verwaltet werden muss, während dies sonst der Prozessor erledigt.

Nicht alle höheren Programmiersprachen erlauben rekursive Aufrufe. Älteres Fortran ist ein Beispiel dafür; ab Fortran 90 sind rekursive Aufrufe möglich. Andere Sprachen sind grundsätzlich rekursiv, etwa Prolog. Rekursive Programmiersprachen und Sprachen wie Scheme setzen Rekursion meistens effizient um.

Umsetzung mit dem Stack

Rekursion wird in der Regel durch einen Stack, also einen Stapelspeicher, umgesetzt. Er nimmt die Rücksprungadressen, alle lokalen Variablen und gegebenenfalls Funktionsergebnisse auf. Jeder rekursive Aufruf legt damit einen neuen Aufrufkontext auf dem Stack an.

Bei der Berechnung von fac(4) werden für jeden Aufruf unter anderem Platz für das Ergebnis, das Argument und die Rücksprungadresse gespeichert. Zuerst wird fac(4) aus dem Hauptprogramm aufgerufen. Danach folgen fac(3), fac(2), fac(1) und fac(0). Der Stack wächst dabei mit jedem Aufruf.

Beim Aufruf fac(0) greift die Abbruchbedingung. Das Ergebnis 1 wird gespeichert. Anschließend werden die Aufrufe in umgekehrter Reihenfolge abgearbeitet: 1 · 1 ergibt 1, danach 1 · 2 = 2, 2 · 3 = 6 und schließlich 6 · 4 = 24. Nach jedem Schritt werden die benötigte Rücksprungadresse und das Argument vom Stack geholt; das neue Ergebnis wird im dafür vorgesehenen Platz abgelegt. Am Ende holt das Hauptprogramm das Ergebnis 24 vom Stack.