Ga naar hoofdinhoud

Bouwsteen 3 — de recursie

Hier bouw je op verder

Leerdoel: je zet de drie stappen om in code en maakt de functie volledig recursief.

De drie stappen​

Pak het recept van Op zoek naar patronen er nog eens bij. Om n schijven van bron naar doel te verplaatsen:

  1. n − 1 schijven naar de hulp-paal. Dat is hetzelfde probleem, met doel even als hulp: hanoi(n - 1, bron, hulp, doel).
  2. De grootste schijf naar doel, één losse zet: (bron, doel).
  3. n − 1 schijven van hulp naar doel. Weer hetzelfde probleem, nu met bron als hulp: hanoi(n - 1, hulp, doel, bron).

Kijk goed hoe de palen in stap 1 en 3 van rol wisselen: in elke deelstap is een andere paal de tijdelijke parkeerplek. Die drie stukken plak je aan elkaar tot één lijst zetten. Daar heb je twee verschillende dingen voor nodig: zetten += andere_lijst plakt alle zetten uit een lijst achter zetten, en zetten.append(zet) hangt er één losse zet aan.

Bouw en test​

Python
Code-omgeving wordt voorbereid…
Antwoord
def hanoi(n, bron, doel, hulp):
    if n == 0:
        return []

    zetten = []
    zetten += hanoi(n - 1, bron, hulp, doel)   # n-1 naar de hulp-paal
    zetten.append((bron, doel))                 # grootste schijf naar doel
    zetten += hanoi(n - 1, hulp, doel, bron)   # n-1 op hun plek
    return zetten

In stap 1 staat hulp op de plek van doel, want de schijven moeten nu naar de hulp-paal, en doel doet dienst als tijdelijke hulp. In stap 3 is het andersom. Verwissel je die twee, dan klopt de oplossing niet meer; zie de fouten-pagina.

Door naar compleet →.