Rekursive Funktion verstehen

[Stift005]

Hallo zusammen!

Könnte mir jemand helfen, folgende Funktion zu verstehen? Irgendwie hakts da gerade gewaltig bei mir.

Code: Alles auswählen

def towers_of_hanoi(n_rings, from_pos, helper_space, to_pos):
    if n_rings == 1:
        print(f"Move from {from_pos} to {to_pos}")
        pass
    else:
        towers_of_hanoi(n_rings - 1, from_pos, to_pos, helper_space)
        print(f"Move from {from_pos} to {to_pos}")
        towers_of_hanoi(n_rings - 1, helper_space, from_pos, to_pos)

towers_of_hanoi(3, "A", "B", "C")

Bei den ersten Aufrufen komme ich noch mit:
- 2, A, C, B
- 1, A, B, C
"Move from A to C"

Nun aber verliere ich den Faden...
- 2, A, C, B ???
...

Ich habe mir das ganze schon im Debugger angesehen, aber komme einfach nicht dahinter.

Endgültige Ausgabe ist:

Code: Alles auswählen

Move from A to C
Move from A to B
Move from C to B
Move from A to C
Move from B to A
Move from B to C
Move from A to C

[rogerb]

@Stift005,

Es beginnt mit dieser Zuordnung der Werte und Parameter wenn man zum ersten Mal in die Funktion eintritt:
from_pos: A
helper_space: B
to_pos: C

3, A, B, C

Im Rekursionsschritt geht es jetzt zuerst in diesen Funktionsaufruf:

Code: Alles auswählen

towers_of_hanoi(n_rings - 1, from_pos, to_pos, helper_space)

Wie du siehst, sind dabei die Parameter to_pos und helper_space miteinander vertauscht.
Das führt zu folgernder Zuordnung, wenn man wieder neu in die Funktion eintritt:

from_pos: A
helper_space: C
to_pos: B

2, A, C, B

Jetzt geht es wieder in den Funktionsaufruf:

Code: Alles auswählen

towers_of_hanoi(n_rings - 1, from_pos, to_pos, helper_space)

wobei to_pos und helper_space wieder vertauscht werden:

1 , A, B, C

Jetzt geht es in den Rekursionsanker, da n_rings==1 Wahr ist.

Es geht es zum ersten Mal einen Schritt in der Aufruf Liste zurück. Und zwar an die Stelle wo der Aufruf gestartet wurde.

Man ist wieder bei:
2, A, C, B

Damit geht es jetzt in den zweiten Funktionsaufruf im Rekursionsschritt

Code: Alles auswählen

towers_of_hanoi(n_rings - 1, helper_space, from_pos, to_pos)

Da sind jetzt diese Parameter vertauscht: helper_space, from_pos

Naja, usw.

Ist schon ziemlich verwirrend, ich weiß. Aber bei drei Ebenen geht es noch. Ich rate dir das mal aufzuschreiben. Notiere dir für jeden Funktionsaufruf, alle Variablen und ihre Werte.