Er gaat iets mis — top-3 fouten

Leerdoel: je herkent de drie fouten die bij de recursieve Hanoi-oplossing het vaakst voorkomen.

Basisgeval vergeten

Foutmelding: RecursionError: maximum recursion depth exceeded.

Oorzaak: zonder if n == 0 blijft de functie zichzelf aanroepen met n - 1, ook onder nul. Er is geen afslag, dus de recursie stopt nooit.

# FOUT — geen basisgeval
def hanoi(n, bron, doel, hulp):
    zetten = []
    zetten += hanoi(n - 1, bron, hulp, doel)   # telt eindeloos af
    zetten.append((bron, doel))
    zetten += hanoi(n - 1, hulp, doel, bron)
    return zetten

Oplossing: begin met de stopconditie.

# GOED
def hanoi(n, bron, doel, hulp):
    if n == 0:
        return []
    ...

hulp en doel verwisseld in de recursieve call

Geen foutmelding, maar de test voor 2 schijven faalt. De lijst is even lang als het hoort, alleen legt de tweede zet de grootste schijf bovenop de kleinste: [("A", "C"), ("A", "C"), ("B", "C")] in plaats van [("A", "B"), ("A", "C"), ("B", "C")]. Speel je die zetten na, zoals bij zelf bouwen, dan wil de derde zet een schijf van een lege paal pakken.

Oorzaak: in stap 1 moeten de n - 1 bovenste schijven naar de hulp-paal, niet naar het uiteindelijke doel. De paal doel dient in die stap even als tijdelijke hulp.

# FOUT — n-1 schijven gaan meteen naar doel
zetten += hanoi(n - 1, bron, doel, hulp)
zetten.append((bron, doel))
zetten += hanoi(n - 1, hulp, doel, bron)

Oplossing: in stap 1 staat hulp op de doel-plek, en doel is de tijdelijke hulp.

# GOED
zetten += hanoi(n - 1, bron, hulp, doel)   # naar de HULP-paal
zetten.append((bron, doel))
zetten += hanoi(n - 1, hulp, doel, bron)

Vuistregel: de schijven die je tijdelijk opzij zet gaan naar de paal die je in deze stap niet als bron of doel gebruikt.

append in plaats van += bij de recursieve aanroep

Geen foutmelding, maar de test voor 2 schijven faalt terwijl de zetten er goed uitzien. Print je de lijst, dan zit er een lijst ín de lijst: [[[], ("A", "B"), []], ("A", "C"), [[], ("B", "C"), []]] in plaats van [("A", "B"), ("A", "C"), ("B", "C")].

Oorzaak: append hangt wat je het geeft als één element aan de lijst, ook als dat zelf een lijst is. De recursieve aanroep geeft een lijst zetten terug, en die wil je niet als geheel erin, maar zet voor zet erachter.

# FOUT — de lijst van de deelstap wordt één element
zetten.append(hanoi(n - 1, bron, hulp, doel))
zetten.append((bron, doel))
zetten.append(hanoi(n - 1, hulp, doel, bron))

Oplossing: += voor een lijst, append voor één zet.

# GOED
zetten += hanoi(n - 1, bron, hulp, doel)   # lijst achter lijst
zetten.append((bron, doel))                 # één losse zet
zetten += hanoi(n - 1, hulp, doel, bron)

Vuistregel: krijg je een lijst terug, plak hem met +=; heb je één zet, gebruik append.

Door naar cheatsheet →.