Rekursion

Stell dich einmal zwischen zwei Spiegel: Du siehst dein Bild, und in diesem Bild noch einmal dein Bild, und darin wieder eines, scheinbar endlos. Oder schau dir ein Farnblatt an: Jeder Zweig sieht aus wie ein kleines Farnblatt, und dessen Zweige sehen wieder genauso aus. Dieses Muster, bei dem etwas eine kleinere Version von sich selbst enthält, heißt Rekursion. In der Informatik ist es eines der mächtigsten Werkzeuge überhaupt.

Eine Funktion ruft sich selbst auf

Du kennst Funktionen als Maschinen: Etwas kommt rein, etwas kommt raus. Der Trick der Rekursion: Eine Funktion darf sich selbst aufrufen, mit einer kleineren Eingabe. Ein Countdown zeigt das perfekt: countdown(3) sagt 3 und ruft dann countdown(2) auf. Der sagt 2 und ruft countdown(1) auf. Der sagt 1 und ruft countdown(0) auf. Jeder Aufruf erledigt ein kleines Stück und reicht den Rest an sich selbst weiter.

Der Basisfall stoppt die Kette

Was passiert bei countdown(0)? Hier muss die Funktion sagen: Stopp, ich bin fertig, und sich NICHT noch einmal aufrufen. Diesen Ausstieg nennt man Basisfall. Ohne ihn würde die Kette nie enden, wie die Spiegel im Spiegel: immer neue Aufrufe, bis dem Computer der Speicher ausgeht und das Programm abstürzt. Jede rekursive Funktion braucht deshalb zwei Dinge: einen Basisfall zum Aufhören und einen Schritt, der das Problem verkleinert.

Fakultät: Rekursion, die rechnet

Rekursion kann auch rechnen. Die Fakultät einer Zahl multipliziert alle Zahlen von 1 bis zu ihr: fakultaet(4) ist 4 mal 3 mal 2 mal 1, also 24. Rekursiv gedacht: fakultaet(4) ist einfach 4 mal fakultaet(3). Und fakultaet(3) ist 3 mal fakultaet(2), und so weiter, bis der Basisfall fakultaet(1) = 1 die Kette stoppt. Dann laufen die Ergebnisse zurück: 1, dann 2, dann 6, dann 24. Ein großes Problem, gelöst durch viele kleine Kopien seiner selbst.