Читать книгу Algorithmen und Datenstrukturen - Gunter Saake - Страница 37

Fakultätfunktion

Das Thema Rekursion wird später an mehreren Stellen noch ausführlich behandelt. Da dieser Begriff zentral für den Stoff diese Buches ist, werden wir ihn nun bereits anhand zweier kurzer Beispiele erläutern. Das vielleicht bekannteste (mathematische) Beispiel für Rekursion ist die Definition der Fakultätfunktion x! mit

x!=(x − 1)! · x

0!=1

Hierbei wird die Fakultät einer Zahl x aus dem Produkt dieser Zahl und der Fakultät ihres Vorgängers x − 1 berechnet: Die Funktion wird sozusagen »mit sich selbst« erklärt. Betrachten wir dazu als Beispiel die Auswertung für 3!. Nach der obigen Definition kann dies durch 2!·3 ersetzt werden, 2! wiederum durch 1!·2 usw., bis wir 0! erreichen, was laut Definition 1 ist:

Türme von Hanoi

Bei dem zweiten Beispiel geht es um die bekannten »Türme von Hanoi« (siehe auch Goldschlager/Lister [GL90] auf den Seiten 57 bis 59 in ausführlicher Beschreibung).

Bei den Türmen von Hanoi handelt es sich ursprünglich um eine kurze Geschichte, die erfunden wurde, um das Prinzip der Rekursion zu verdeutlichen.

In dieser Geschichte haben Mönche die Aufgabe, einen Turm von 64 unterschiedlich großen goldenen Scheiben zu bewegen. Dabei gelten folgende Regeln:

 Zu jedem Zeitpunkt können Türme von Scheiben unterschiedlichen Umfangs auf drei Plätzen stehen. Der ursprüngliche Standort wird als Quelle bezeichnet, das Ziel als Senke. Der dritte Platz dient als Arbeitsbereich (kurz AB), um Scheiben zwischenzulagern.

 Nur jeweils die oberste Scheibe eines Turmes darf einzeln bewegt werden.

 Dabei darf niemals eine größere auf einer kleineren Scheibe zu liegen kommen.

Die Aufgabe ist nun das Bewegen eines Turmes der Höhe n (etwa n = 64 im Originalbeispiel) von einem Standort zu einem zweiten unter Benutzung des dritten Hilfsstandorts (siehe Abbildung 2–4).

Es ist nun gar nicht so einsichtig, in welcher Reihenfolge man Scheiben von wo nach wo bewegen muss, um tatsächlich dieses Ziel zu erreichen (man probiere es selbst mit einem kleinen n, etwa n = 4 – statt goldener Scheiben genügen auch Teller oder unterschiedlich große Bücher).

Durch Nachdenken kommt man allerdings zu der Erkenntnis, dass man, sofern man weiß, wie man einen um eins kleineren Turm bewegen kann, auch den größeren Turm bewegen kann. Die Vorgehensweise zeigt folgender Pseudocode-Algorithmus: