Rekursion in der Informatik einfach erklärt

Bei direkter Rekursion ruft eine Funktion sich selbst auf. Ihre Regeln unterscheiden einen Fall ohne weiteren Selbstaufruf und einen Fall mit Selbstaufruf.

Der Rekursionsanfang heißt auch Basisfall. Hier liefert die Funktion direkt ein Ergebnis zurück. Die Abbruchbedingung legt fest, wann dieser Fall gilt. Der Rekursionsschritt enthält den Selbstaufruf. Für einen erfolgreichen Ablauf muss dessen Eingabe so verändert werden, dass schließlich ein Basisfall erreicht wird.

Betrachte die ausgedachte Funktion „zaehle“. Ihre Eingabe n ist eine ganze Zahl ab null. Bei n=0 gibt sie direkt 0 zurück. Bei n>0 berechnet sie 1+\operatorname{zaehle}(n-1) und gibt dieses Ergebnis zurück. Die Schreibweise \operatorname{zaehle}(n-1) bedeutet: Rufe „zaehle“ mit der Eingabe n-1 auf. Der nächste Aufruf erhält also eine um eins kleinere Eingabe.

Betrachte die ausgedachte Funktion „summe“. Die Eingabe n ist eine ganze Zahl ab null. Bei n=0 gibt sie 0 zurück. Sonst berechnet sie n+\operatorname{summe}(n-1) und gibt das Ergebnis zurück.

Ein äußerer Aufruf kann seine Addition erst abschließen, wenn der innere Aufruf sein Ergebnis zurückgegeben hat. Beim Aufrufen werden die Eingaben kleiner. Sobald der Basisfall antwortet, werden die wartenden Rechnungen von innen nach außen abgeschlossen. Dabei verwendest du jeweils den Rückgabewert des inneren Aufrufs, nicht dessen Eingabe.

Der Aufrufstapel ist ein Speicher für noch nicht abgeschlossene Funktionsaufrufe und ihre benötigten Werte. Ein Stapel ist hier ein Modell: Der zuletzt begonnene, noch offene Aufruf wird zuerst abgeschlossen. Bei „summe“ muss zum Beispiel gespeichert bleiben, welche Zahl nach der Rückgabe noch addiert werden soll.

Terminierung bedeutet, dass ein Ablauf nach endlich vielen Schritten endet. Prüfe dafür den erlaubten Eingabebereich, die Abbruchbedingung und die Änderung der Eingabe bei jedem Selbstaufruf. Eine vorhandene Abbruchbedingung genügt nicht: Der Ablauf muss sie tatsächlich erreichen.

Die ausgedachte Funktion „runter“ erlaubt ganze Zahlen ab null. Bei n=0 gibt sie 0 zurück. Sonst ruft sie \operatorname{runter}(n-1) auf und gibt dessen Ergebnis zurück. Von jeder erlaubten Eingabe führen endlich viele Schritte um eins zur null. Deshalb erreicht diese Funktion ihren Basisfall.

Die ausgedachte Funktion „hoch“ hat denselben Basisfall, ruft sich sonst aber mit n+1 auf. Bei einer positiven Startzahl wachsen die Eingaben und erreichen null nicht. Auch eine unveränderte positive Eingabe würde den Basisfall nicht erreichen. Ohne Basisfall entstehen bei solchen Selbstaufrufen ebenfalls weitere Aufrufe statt einer regulären Rückgabe.

In einer Umsetzung können zu viele offene Aufrufe den verfügbaren Speicher für den Aufrufstapel überschreiten. Ein solcher Überlauf heißt auch „Stack Overflow“. Das ist eine mögliche Folge und tritt nicht bei jedem rekursiven Aufruf auf.

Beachte die genaue Bedingung: n\leq0 bedeutet „n ist kleiner oder gleich null“. Dann gehören auch negative Eingaben zum Basisfall. Beim Verringern um zwei kann eine Folge die null überspringen und trotzdem einen solchen Basisfall erreichen.

Die Fakultät einer positiven ganzen Zahl ist das Produkt aller ganzen Zahlen von eins bis zu dieser Zahl. Das Zeichen ! kennzeichnet die Fakultät. Zum Beispiel gilt 4!=1\cdot2\cdot3\cdot4=24. Das Zeichen \cdot steht für Multiplikation. Hier betrachten wir Eingaben n\geq1, also ganze Zahlen ab eins.

Die rekursive Funktion „fak“ gibt bei n=1 direkt 1 zurück. Für größere Eingaben berechnet sie n\cdot\operatorname{fak}(n-1). Jeder Aufruf wartet auf das kleinere Ergebnis und multipliziert es anschließend mit seiner eigenen Eingabe.

Iteration bedeutet Wiederholung durch eine Schleife. Eine Schleife führt einen Arbeitsschritt wiederholt aus. Für eine iterative Fakultätsberechnung speicherst du zunächst das Ergebnis 1. Dann multiplizierst du dieses Ergebnis der Reihe nach mit den ganzen Zahlen von 2 bis n. Nach jeder Multiplikation ersetzt du das gespeicherte Ergebnis durch das neue. Bei n=1 gibt es keinen Schleifendurchlauf; das Ergebnis bleibt 1.

Beide Verfahren bilden für die erlaubten Eingaben dasselbe Produkt. Die Schleife sammelt dabei keine wartenden Selbstaufrufe. Im beschriebenen Aufrufstapel-Modell benötigt jeder wartende rekursive Aufruf zusätzlichen Speicher. Iterative Verfahren sind meist effizienter, kommen also mit weniger Aufwand aus, und benötigen meist weniger Speicher. Für ein konkretes Programm hängt das auch von seiner Umsetzung ab.