10.7 Rekursionen

Eine Funktion kann sich selbst wieder aufrufen. Man spricht dann von einer Rekursion. Jede Rekursion benötigt eine Abbruchbedingung, in der sie sich nicht selbst aufruft. Andernfalls erhält man eine Endlosschleife.

Ein klassisches Beispiel für eine Rekursion ist die Fakultät, da die Definition der Fakultät rekursiv ist. Allerdings läßt sich die Fakultät nichtrekursiv schneller berechnen. Die Fakultät von 1 (geschreiben 1!) ist definiert als 1. Die Fakultät einer beliebigen Zahl n ist diese Zahl multipliziert mit der Fakultät der um eins kleineren Zahl. Oder etwas mathewmatischer formuliert: n! = n * (n-1)!

int fakultaet(int x)
{
   if (x == 1)
      return 1;
   else
      return x * fakultaet(x - 1);
}

Achtung! Die Fakultät erreicht sehr schnell große Werte so daß man mit einem 16 Bit int schnell an die Grenzen stoßen kann. Außerdem prüft obige Funktion nicht, ob der Parameter auch positiv ist. Machen sie sich ruhig den Programmlauf klar, indem sie Ausgaben einfügen und die Funktion in main aufrufen.

Oder versuchen sie sich an den Türmen von Hanoi. Hierbei haben sie 3 Stäbe, auf denen sie Scheiben aufschieben können. Jede Scheibe kann nur auf einen leeren Stab oder auf einen Stab mit einer größeren Scheibe geschoben werden. Wie verschiebt man jetzt den Turm von Scheiben auf einen anderen Stab? Auch dieses Problem kann man rekursiv lösen. Man nimmt einfach den Turm aus allen Scheiben bis auf die letzte, schiebt ihn auf den Stab, wo später der Turm nicht hin soll. Dann schiebt man die letzte Scheibe auf den Zielstab und anschließend den "geparkten" Turm auf diese Scheibe. Der kleinere Turm wird natürlich auch wieder mit dem gleichen Algorithmus verschoben. Erst wenn man einen Turm aus einer Scheibe hat ist die Abbruchbedingung erreicht. Diese Scheibe kann direkt verschoben werden.

English version not yet available.