12.8 Aanpassen — alleen tellen

Leerdoel: je past het recursieve patroon aan om alléén 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. Je hoeft dan niets te verplaatsen — je telt gewoon. Dezelfde recursieve structuur, maar met getallen in plaats van een lijst:

• 0 schijven → 0 zetten (het basisgeval).
• n schijven → 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 recurrence T(n) = 2 · T(n − 1) + 1.

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 stap 9: zelf bouwen →.