Rekursion – Grundlegendes Konzept der Informatik


Verbreitet die Message!

Rekursion ist eines der Grundkonzepte der Software-Entwicklung und gehört daher in die Toolbox jedesDevelopers. Obwohl das Grundkonzept äußerst simpel ist, tun sich gerade Anfänger schwer damit, das Prinzip zu veranschaulichen und anzuwenden.

Was ist Rekursion?

Rekursion bezeichnet in der Softwareentwicklung gemeinhin, dass eine Methode sich selbst wieder aufruft. Um die Anwendung zu verstehen, nehmen wir erst einmal die einfache Methode her:

methodXY(){
var lokaleVariable1;
var lokaleVariable2;

/* 
* Implementierung & Anweisungen*
*/

methodXY();
}

Zur Laufzeit erstellt der Compiler die Methode in dem er Speicher für die Methode bereitstellt. Sowohl für die Variablen, als auch für den Prozess selbst muss Speicher zur Verfügung gestellt werden. Sie geben Aufschluss darüber, ob der Prozess bereits abgearbeitet ist, oder wo im Speicher der geladene Code vorgehalten wird. Startet also unser Programm wird erstmalig Speicher wie folgt belegt:

Die Methode ist noch nicht aufgerufen worden.

Was passiert nun, wenn die Methode aufgerufen wird?

Der mit “Laufzeit” betitelte Pfeil steht hier für den Zeitpunkt an dem sich das Programm gerade befindet. Zum Zeitpunkt des Aufrufs von methodeXY() wird neuer Speicher für eine zweite Instanz der Methode belegt. Die Abarbeitung findet nun am Anfang der aufgerufenen MethodeXY() statt. Treiben wir das Spiel weiter, sieht das Programm zu einem späteren Zeitpunkt so aus:

Die zweite Instanz der Methode hat hier noch eine weitere – die dritte Instanz – aufgerufen (diese befindet sich gerade “mittem im Code” / in der Abarbeitung). Es befinden sich 3 Instanzen im Speicher – mit jeweils dem Overhead einer Methode. Wichtig ist dabei, dass sowohl die erste Instanz, als auch die zweite, als auch die dritte noch nicht abgearbeitet wurde!

Unschwer zu erkennen ist unser Beispiel eine Endlosschleife. Es würden unendlich Methoden instanziiert und der Speicher (RAM) schnell voll sein. Der daraus resultierende Laufzeitfehler heißt: Stack Overflow Exception – das Programm stürzt ab.

Wir benötigen also ein irgendwie geartetes Ende dieser Kette, den sogenannten Rekursionsabbruch. Unser abstraktes Beispiel hat aus didaktischen Gründen eine Vereinfachung: Die MethodeXY gibt nichts zurück, das ist aber – wie wir sehen werden – ein weiterer Kern der Rekursion.
Wir gehen also weg von unserem abstrakten Beispiel und schauen uns ein Minimalbeispiel an.

Beispiel: Fakultät

Die Fakultät ist eine sehr einfache mathematische Funktion, die sich wunderbar eignet um Rekursion zu erklären, da sie selbst (mathematisch) rekursiv definiert ist: Die Fakultät einer Zahl x ist einfach die wiederholte Multiplikation aller ihrer Vorgänger (außer der Null) – die Schreibweise ist x! (gesprochen x Fakultät).
Dabei ist 0! per Definition 1.
1! = 0! * 1.
2! = 1 * 2.
3! = 1 * 2 * 3 und so weiter.

Hier fällt bereits auf, dass man 3! auch anders aufschreiben kann, nämlich als 3! = 2! * 3 -leichter sieht man das auch dadurch dass 3! = (1*2)*3 und (1*2) = 2! ist (Substitution).
Das ist der Kern, den wir bei der Rekursion nutzen wollen! Wir wollen nicht 3! berechnen indem wir von eins bis 3 aufmultiplizieren*, sondern 3 * 2! berechnen.
Dann müssen wir 2! berechnen.
Das tun wir dann indem wir 2*1! berechnen. 1! = 1* 0!
Jetzt wird es spannend, denn 0! kennen wir ja per Definition – es ist 1. Wir haben hier unseren Rekursionsabbruch.

Mathematisch wird die Rekursion wie folgt definiert:

(1) 0! = 1
(2) x! = (x-1)! * x

Um es nochmal andersherum, von innen nach außen zu erklären: 3! kann man schreiben als 3! = ( 2! * ( 1! *  (0!)))
Die Klammerung ist hier nicht nur die mathematische Schreibweise, sondern auch jeweils immer eine Methoden Instanz! Wir wollen genau an diese Stelle kommen: (0!) = 1, nur können wir bei Rekursion dort nicht starten, sondern dies ist immer der letzte Schritt – deshalb auch der Rekursionsabbruch:

Nimm Dir kurz die Zeit um dir zu überlegen, wie du das rekursiv implementieren könntest. Es nützt dem Verständnis sehr, wenn du versuchst dies jetzt ohne weitere Anleitung zu implementieren. Du kannst auch Pseudocode schreiben. Poste deinen Lösungsansatz gern als Kommentar unter diesen Beitrag! Wie muss der Rekursive Aufruf aussehen?


Implementierung Fakultät:

function fakultaet (x){
  if (x==0) { return 1;}
  
  return fakultaet(x-1)*x;
}

Was genau passiert hier? Nehmen wir das Beispiel 3!

Hier sieht man den Ablauf der Rekursion bis zum Rekursionsabbruch. Im letzten Methodenaufruf haben wir also das erste Ergebnis, dass nicht mehr von einer anderen Instanz abhängt.
Wichtig ist jetzt zu verstehen, wie die Rekursion wieder rückwärts aufgelöst wird. Sehen wir uns dazu nur den Ausschnitt der letzten beiden Instanzen an.

Hier weiß also die Instanz fakultaet(1) über den Rückgabewert von fakultaet(0) und kann dies auswerten. Es entsteht eine Rekursionsauflösung:

Das aufrufende Programm wartet während des ganzen Prozesses in der ersten Instanz der Methode auf “Antwort” der anderen Methoden. Die erste Instanz der Methode geht her und versucht den Ausdruck auszuwerten und geht dabei stur (imperativ) vor. Die erste Instanz schaut dabei nicht in die “Zukunft”, bzw. die weiteren Instanzen, sondern arbeitet einfach stur die aufgerufene Methode ab. Das heißt, wenn der Rekursionsabbruch nicht in jedem Fall erreicht würde, bekämen wir den Stack Overflow Error. Es ist also absolut essentiell, dafür zu sorgen, dass dieser immer erreicht wird!
Bonusfrage: Wie könnte man garantieren / beweisen, dass unser Algorithmus terminiert?


*Natürlich lässt sich gerade dieses Beispiel sehr einfach ohne Rekursion (nämlich iterativ) berechnen, aber hier dient die Rekursion dem didaktischen Zweck!

Verbreitet die Message!

Schreiben Sie einen Kommentar