Ein beliebtes Beispiel für rekursives Programmieren ist das 1883 vom Mathematiker Eduard Lucas erfundene (Mathematik-)Denkspiel “Die Türme von Hanoi“.

Das Spiel besteht darin, einen Stapel A von verschieden großen Scheiben, welche der Größe nach sortiert sind, auf einen Stapel C mithilfe eines “Zwischenlager”-Stapel B zu bewegen ohne dabei eine größere Scheibe auf eine kleinere Scheibe zu legen. Am Ende muss auf dem Stapel C die selbe geordnete Reihenfolge vorliegen, wie auf dem Ursprungs-Stapel A. Zusätzlich gilt, dass jeweils nur eine Scheibe bewegt werden darf.

Der Stapel A mit 4 Scheiben wird so gelöst:

Dazu gibt es nun einen rekursiven Lösungsweg in der Programmierung. Man löst jeweils das kleinste Problem und wendet das selbe auf das nächt größere Problem an. Das heißt, man löst das Problem eines Stapels mit zwei Scheiben, kann dieses Problem gelöst werden, löst man das Problem für 2+1 bzw. schlussendlich n+1 Scheiben.

Der entsprechende Algorithmus in C:

void hanoi(int h, char src, char dest, char tmp) {
    if (h == 1) {
        moveDisk(src, dest);
    } else {
        hanoi(h-1, src, tmp, dest);
        moveDisk(src, dest);
        hanoi(h-1, tmp, dest, src);
    }
}
 
void moveDisk(char src, char dest) {
    printf("Move %c to %c\n", src, dest);
}

(Als simples Beispiel wird moveDisk() lediglich die entsprechenden Züge ausgeben.)

Ein beliebtes Beispiel für rekursives Programmieren ist das 1883 vom Mathematiker Eduard Lucas erfundene (Mathematik-)Denkspiel “Die Türme von Hanoi“. Das Spiel besteht darin, einen Stapel A von verschieden großen Scheiben,...