Aanpassen — alleen tellen

Leerdoel: je past het recursieve patroon aan om alleen het aantal zetten te berekenen, zonder de lijst op te bouwen.

Het idee

Soms wil je niet de hele lijst zetten, maar alleen hoeveel het er zijn. Dan hoef je niets te verplaatsen, alleen te tellen: dezelfde recursieve structuur, maar met getallen in plaats van een lijst. Voor 0 schijven zijn het 0 zetten, het basisgeval. Voor n schijven is het het aantal zetten voor n − 1 schijven, plus 1 voor de grootste schijf, plus nog eens dat aantal voor n − 1.

Dat is precies de formule van de patronen-pagina, T(n) = 2 · T(n − 1) + 1. Zo'n formule, die de kosten van n uitdrukt in de kosten van een kleiner probleem, heet een recurrence.

Bouw en test

Python

Code-omgeving wordt voorbereid…

Antwoord

def tel_zetten(n):
    if n == 0:
        return 0
    return tel_zetten(n - 1) + 1 + tel_zetten(n - 1)

Of korter: return 2 * tel_zetten(n - 1) + 1. Beide geven 2ⁿ − 1.

Door naar uitrollen tot het basisgeval →.