Rekursion erklärt
Was ist Rekursion? Wofür braucht man sie? Diese Fragen soll der vorliegende Artikel möglichst einfach beantworten.
Was ist Rekursion?
Rekursion ist ein Programmierkonzept, bei der eine Funktion nur einen kleinen Teil der Arbeit macht und damit ein Problem ein bisschen verkleinter, und sich dann selbst aufruft um den Rest des Problems zu lösen.
Das wird so lange fortgesetzt, bis das Problem auf einen sehr einfachen Fall reduziert ist.
Ein Beispiel
Ein klassisches Beispiel zum erklären der Rekursion ist die sogenannte Fakultätsfunktion.
Sie ist folgendermaßen definiert:
n! = n * (n-1) * ... * 2 * 1
Das heißt die Fakultät einer Zahl das Produkt aller ganzer Zahlen kleiner gleich der Zahl selbst.
Die obige Definition ist aber nicht sehr elegant: obwohl
offensichtlich ist, was gemeint ist, liefert sie für
n=1 streng genommen keine sinnvollen Werte, weil in der
Definition eine 2 auftaucht.
Die elegantere Defintion geht so:
n! = 1 wenn n=1 ist n! = n * (n-1)! sonst
Man beachte, dass in der Defintion der Fakultät die Fakultät selbst auftaucht, trotzdem ist sie sinnvoll definiert.
Diese Form der Definition ist sehr eng an die rekursive Programmierung angelehnt. In C programmiert sieht diese Funktion so aus:
int fakultaet(int n){ if (n == 1){ return 1; } else { return n * fakultaet(n-1); } }
Was passiert jetzt, wenn man fakultaet(3) aufruft?
Im ersten Aufruf ist die Bedingung n == 1 sicher nicht
erfüllt, also wird der zweite Zweig aufgerufen, und
3 * fakultaet(2) zurückgeliefert.
Aber der Wert für fakultaet(2) ist nicht bekannt,
die Funktion muss also noch einmal berechnet werden, diesmal mit
dem Argument 2.
Auch der Aufruf von fakultaet(2) liefert noch keine
reine Zahl zurück, sondern 2 * fakultaet(1), und
fakultaet(1) ist endlich 1.
Es wurde also folgendes berechnet:
fakultaet(3) = 3 * fakultaet(2) = 3 * 2 * fakultaet(1) = 3 * 2 * 1 = 6
Wozu das ganze?
Wer dieses Beispiel gesehen hat, fragt sich sicher, was die Rekursion denn soll. Schließlich tut es ein ganz einfaches, iteratives (also nicht-rekursives) Programm genauso:
int fakultaet(int n){ int p = 1; while(n > 1){ p = p * n; n--; } return p; }
Und schneller ist es auch noch.
Rekursion hat aber den Vorteil, dass es ganz natürlich größere Probleme in kleinere zerlegt, und so zum Teil erheblich leichter anzupacken ist.
Beispiel gefällig? Nehmen wir die "Türme von Hanoi".
Das ist ein altes Spiel, bei dem man drei Pfosten hat, auf denen Ringe verschiedener Größe liegen. Ziel des Spiels ist es, den Turm auf einen der anderen Pfosten zu verschieben, ohne jemals zwei Ringe auf einmal zu bewegen oder einen größeren auf einen kleineren Ring zu legen.
Dabei kann man die Lösungsstrategie folgendermaßen beschreiben: wenn man nur einen Ring verschieben will, kann man es einfach machen. Wenn man mehrere Ringe verschieben will, verschiebt man erstmal alle außer dem untersten auf den Zwischenstapel, verschiebt den letzten Ring und dann verschiebt man den restlichen Stapel auf seine Endposition über den verschobenen Ring.
Oder als C-Programm:
void move(int coin, char start, char end){ printf("Moving coin %d from '%c' to '%c'\n", start, start, end); } void hanoi(int coin, char start, char end, char third) { if (coin == 1){ move(1, start, end); } else { hanoi(coin - 1, start, third, end); move(coin, start, end); hanoi(coin - 1, third, end, start); } } int main(int argc, char** argv){ hanoi_move(3, 'A', 'B', 'C'); return 0; }
Man glaubt es kaum, dass dieser einfache Code das Problem lösen soll, aber es ist tatsächlich so.
Um sich das zu veranschaulichen, kann man sich "von Hand" überlegen, in welcher Reihenfolge die Aufrufe geschehen.
Um Platz zu sparen ersetze ich hier in jeder Ebene alle Aufrufe von Unterfunktionen, obwohl sie im Programm nacheinander (und nicht gleichzeitig) gesehen
0. Ebene:
hanoi(3, 'A', 'B', 'C');
1. Ebene:
hanoi(2, 'A', 'C', 'B');
move('A', 'C');
hanoi(2, 'C', 'B', 'A');
2. Ebene:
hanoi(1, 'A', 'B', 'C');
move('A', 'C');
hanoi(1, 'C', 'B', 'A');
move('A', 'C');
hanoi(1, 'C', 'A', 'B');
move('C', 'B');
hanoi(1, 'A', 'B', 'C');
3. Ebene:
move('A', 'B');
move('A', 'C');
move('C', 'B');
move('A', 'C');
move('C', 'A');
move('C', 'B');
move('A', 'B');
Zuerst wird also ein Ring von A nach B bewegt. Das Programm hat drei Funktionsaufrufe gebraucht, um das herauszufinden.
Typisch für rekursive Funktionen sind diese Schritte:
- Eine Abbruchbedingung, die dafür sorgt, dass keine endlose Schleife entsteht
- Ein kleiner Teil des Problems wird in der Funktion selbst gelöst, der Rest wird durch rekursives von sich selbst gelöst
- Wenn nötig werden die beiden Lösungen kombiniert.
Noch ein Beispiel: Merge Sort
Die Türme von Hanoi sind sind ein eher akademisches Beispiel. Häufig in der freien Wildbahn des Programmierers trifft man auf das Problem, eine Liste sortieren zu müssen. Ein beliebtes und schnelles Verfahren ist Merge Sort.
Merge Sort funktioniert wie folgt:
- Wenn die Eingabeliste ein oder gar kein Element enthält, ist sie sortiert
- Teile die Liste in in der Mitte. Sortiere die beiden Hälften rekursiv
- Füge die beiden sortieren Listen zu einer gemeinsamen sortierten Liste (nach dem Reissverschlußprinzip) zusammen.
Und wieder in C implementiert:
#include <stdio.h> void mergesort(int* const list, const int length) { if (length <= 1) { return; } int half = length / 2; /* sort the left half */ mergesort(list, half); /* sort the right half */ mergesort(list+half, length - half); /* join the sorted half */ int left_p = 0; int right_p = half; int new_values[length]; for (int i = 0; i < length; i++) { if (left_p == half ) { new_values[i] = list[right_p++]; } else if (right_p == length) { new_values[i] = list[left_p++]; } else { if (list[left_p] <= list[right_p]) { new_values[i] = list[left_p++]; } else { new_values[i] = list[right_p++]; } } } for (int i = 0; i < length; i++) { list[i] = new_values[i]; } } int main(int argc, char** argv) { int l[9] = { 12, 0, 3, 7, 6, 8, 3, -3, 8}; mergesort(l, 9); for (int i = 0; i < 9; i++) { printf("%d ", l[i]); } printf("\n"); }