Exkurs - Implementierung in Python
Rekursion in Python
In Python können rekursive Algorithmen mit Funktionen, die sich selbst aufrufen, implementiert werden.
Damit können zum Beispiel die Zahlen 1, ..., n auch ohne Schleife ausgegeben werden. Wenn mehr als eine Zahl ausgegeben werden soll, werden zuerst die Zahlen 1, ..., n-1 im rekursiven Aufruf ausgegeben. Danach folgt die Ausgabe von n, die die Ausgabe komplettiert. Im Basisfall n = 1 wird nur die Zahl 1 ausgegeben.
xxxxxxxxxx1
undefinedAusgabe
Man muss nur aufpassen, dass man auch einen Basisfall implementiert. Ansonsten versucht die Funktion immer weiter, sich selbst aufzurufen. Der Python-Interpreter bricht diese Versuche irgendwann ab und wirft einen Fehler.
xxxxxxxxxx1
undefinedAusgabe
Türme von Hanoi - Implementierung des rekursiven Algorithmus
Schon in Erkundung - Strategie für mehr als drei Scheiben haben wir uns gefragt:
Ist es möglich, eine verallgemeinerte Funktion
bewegeMehrereScheiben(n, X, Z, Y) zu implementieren, die eine passende Zugfolge für eine beliebige Scheibenanzahl n erzeugt? Aufgabe 1
Implementiere den rekursiven Algorithmus als Python-Programm.
Aufgabe 2
- Teste die Ausgabe des Algorithmus für fünf oder mehr Scheiben mithilfe der Simulation.
- Zähle in der Ausgabe des Algorithmus für ein paar Eingaben die Anzahl der Züge. Schätze ab, wie lang die Mönche wohl brauchen, um einen 64-Scheiben-Turm umzustapeln. Wir gehen davon aus, dass sie zum Transport einer Scheibe mindestens 10 Sekunden benötigen.
