i

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.

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.

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

  1. Teste die Ausgabe des Algorithmus für fünf oder mehr Scheiben mithilfe der Simulation.
  2. 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.

Suche

v
2.2.1.5
www.inf-schule.de/algorithmen/rekursivealgorithmen/problemloesen/exkurs_python
www.inf-schule.de/2.2.1.5
www.inf-schule.de/@/page/K29UEjXtRnhmCM9w

Rückmeldung geben