Bouwsteen 2 — het basisgeval

Hier bouw je op verder: If en else

Weet je dit niet meer zeker? Lees het terug voordat je verdergaat.

• Python If en else

Leerdoel: je begrijpt waarom recursie een stopconditie nodig heeft en schrijft het basisgeval voor Hanoi.

Waarom een basisgeval?

Straks roept hanoi zichzelf aan met steeds minder schijven: n, dan n − 1, dan n − 2, enzovoort. Zonder afslag gaat dat door tot onder nul en stopt het nooit. Python grijpt dan in met:

RecursionError: maximum recursion depth exceeded

Het basisgeval is die afslag: het allerkleinste probleem, dat je direct kunt beantwoorden zonder jezelf nog eens aan te roepen.

Wat is het kleinste geval?

Nog kleiner dan één schijf is nul schijven, en een lege stapel verplaatsen kost geen enkele zet. Bij n == 0 geef je dus een lege lijst [] terug.

Dat is handiger dan stoppen bij n == 1: straks telt de recursie vanzelf af tot 0 en valt alles op zijn plek.

Bouw en test

Python

Code-omgeving wordt voorbereid…

Antwoord

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

return stopt de functie meteen, dus bij n == 0 komt de regel eronder niet meer aan bod. Die tijdelijke regel vervang je op de volgende pagina door de echte recursie.

Door naar de recursie →.