De slimme abt van Hanoi

"Lang geleden, bij het begin der schepping, toen de wereld net ontstaan was, sprak de oppergod Brahma tegen de monniken van Zijn klooster in de stad Hanoi:
'Aanschouw de binnenplaats'
Tot de verbazing van de monniken waren er op de binnenplaats, die net nog leeg was geweest op wat gras en stof na, drie palen te zien. Op de eerste paal zat een groot aantal gouden schijven, een enorme gouden schijf omringde de onderkant van de paal, een iets kleinere gouden schijf lag daarbovenop, een nog iets kleinere lag daar weer bovenop, totdat er uiteindelijk net onder de top van de eerste paal een piepklein gouden schijfje lag.
'Zoals iedere dag anders moet zijn en alles wat ontstaan is weer moet vergaan, zo zullen jullie Mijn klok bijhouden. Het is jullie taak elke dag een schijf te verplaatsen van de ene naar de andere paal, totdat alle 64 gouden schijven van de eerste naar de laatste paal zullen zijn overgebracht, wat de Laatste Dag zal zijn. Volgens de wetten van de kosmische harmonie mag er nooit een grotere schijf op een kleinere schijf liggen. En maak geen fout in de verplaatsing, of riskeer mijn toorn. Morgen, bij het ochtendgloren, moet de eerste schijf verplaatst zijn."

Ineens was Brahma verdwenen, maar de drie palen met hun gouden schijven stonden nog steeds op de binnenplaats. Alle monniken keken naar de abt, die van de eerste naar de tweede naar de derde paal keek.

"Wat moeten we doen, o abt?"

De abt lachte zenuwachtig.

"Maak jullie geen zorgen. Ik heb alles onder controle." En hij liep snel naar zijn kamer om te mediteren.

Tot diep in de nacht konden de monniken de abt horen ijsberen in zijn kamer. De abt was geen wiskundige (aan het begin van de wereld was de wiskunde namelijk nog niet uitgevonden) en hij had kennelijk veel moeite met het vinden van de juiste eerste stap. Alle monniken waren dan ook al in slaap gevallen toen de prior (de onder-abt) wakker werd van een gebons op zijn deur.

"Opstaan, broeder" - het was de abt. "Ik heb een taak voor je."

Slaapdronken opende de prior de deur, waarna zijn superieur de strategie uitlegde.

"Na veel nadenken, broeder, is het mij duidelijk dat ik als abt veel te belangrijk ben om elke dag met gouden schijven te sjouwen. Zoals ik de belangrijkste persoon hier ben, zo zal ik alleen de belangrijkste en grootste gouden schijf verplaatsen. Jij hebt de opdracht de bovenste 63 schijven naar de tweede paal te plaatsen, daarna zal ik de grootste schijf naar de derde paal verplaatsen, en dan mag jij het werk afronden door de 63 kleinere schijven allemaal keurig daar weer op te stapelen. O ja, en je moet de eerste schijf vóór de komende ochtend geplaatst hebben. Slaap lekker."

De prior was te slaperig om goed te realiseren wat er gebeurd was, maar nadat de abt was vertrokken en luid in zijn cel ernaast lag te snurken, besefte de prior dat hij een probleem had. Drie-en-zestig gouden schijven verplaatsen was veel ingewikkelder dan hij kon oplossen. Maar omdat hij een belangrijke broeder was, waarom kon hij dan niet het trucje van de abt toepassen? Zo werd drie minuten later de kloosteroudste gewekt, met de opdracht de 62 bovenste schijven naar de laatste paal te verplaatsen, zodat de prior de 63e schijf naar de 2e paal kon verplaatsen, waarna de kloosteroudste weer die 62 schijven naar de middelste paal moest verplaatsen zodat alle schijven klaar zouden zijn voor het verplaatsen van de grootste gouden schijf door de abt.

De kloosteroudtse vond dat echter ook te ingewikkeld, en gaf de op één na oudste monnik de opdracht de 61 bovenste schijven naar de middelste paal te verplaatsen, zodat de oudste monnik de 62e schijf naar de derde paal kon verplaatsen, zodat... En omdat er precies 64 monniken in het klooster waren verplaatste de jongste novice de volgende ochtend de eerste gouden schijf, op een manier die Brahma behaagde.

-----------------------------------------------------------------------------------------

Je beseft misschien dat dit maar een sprookje is, en ook nog dat dit een sprookje is dat waarschijnlijk is verzonnen door een wiskundige (immers, wiskunde gaat er gemakkelijk van uit dat de wereld volgens wiskundige regels geregeerd wordt, en bovendien dat alles onveranderlijk is). Het verhaal van de torens van Hanoi is officieel bedacht door de Franse wiskundige Edouard Lucas, hoewel volgens sommigen de echte uitvinder Harrison Heath was, die dol was op schijfpuzzels en aan wie we ook "vier-op-een-rij" te danken hebben.

Maar interessanter dan de ontstaansgeschiedenis van de puzzel is zijn oplossing. De abt lijkt erg flauw doordat hij zijn werk afschuift op zijn ondergeschikten. Maar in werkelijkheid is dat een erg slimme oplossing omdat de abt het probleem kleiner maakt. Een probleem met 64 schijven wordt een probleem met 63 schijven wordt een probleem met 62 schijven... tot het uiteindelijk een doodeenvoudig probleem met één schijf is.

Zo'n aanpak van problemen wordt "recursie" genoemd. Een standaardvoorbeeld van recursie is het berekenen van faculteiten (1! = 1, 2! = 2x1=2, 3!=3x2x1=6, 4!=4x3x2x1=24, 5!=...) die kan worden samengevat tot de volgende twee regels.

Als n=1, dan n! = 1
Als n>1, dan n! = n x (n-1)!

Als je dus 3! wilt berekenen werkt de eerste regel niet, volgens de tweede regel moet je 3 vermenigvuldigen met 2!. Dat weet je ook niet, de eerste regel geldt ook niet voor 2!, maar de tweede regel zegt dat 2!=2x1!. 1! weet je (dat is 1), dus 2! wordt 2x1 = 2, en 3! wordt 3x2=6, wat inderdaad het juiste antwoord is.

De oplossing van de Hanoi-puzzel ziet er zo uit:

Verplaats (n schijven, van bron_toren, via hulp_toren, naar doel_toren)
Als n>=2 schijven:
Verplaats(n-1 schijven, van bron_toren, via doel_toren, naar hulp_toren)
Verplaats schijf van bron_toren naar doel_toren
Als n>=2 schijven:
Verplaats(n-1 schijven, van hulp_toren, via bron_toren, naar doel_toren)

Dit klinkt heel ingewikkeld, maar probeer het eens met 2 schijven. De intuitieve oplossing is de bovenste schijf naar de middelste toren te verplaatsen, de onderste schijf direct naar de doeltoren, en dan de bovenste schijf daarbovenop te plaatsen. En dat klopt ook met het algoritme: als je twee schijven van toren 1 via toren 2 naar toren 3 verplaatst, moet je eerst 1 schijf verplaatsen van toren 1 'via toren 3' naar toren 2. Via toren 3 is hier niet nodig, omdat het er maar eentje is, dus direct van 1 naar 2. Dan de onderste schijf van 1 naar 3, tenslotte de kleinste schijf van de hulptoren 2 naar de doeltoren 3!

De meeste studenten die ik over recursie heb verteld worden in het begin heel erg duizelig, en zelfs verward van het begrip. Recursie is echt iets dat je moet bestuderen, voorbeelden bekijken, en als je dat een paar avonden hebt gedaan voor het slapen gaan begrijp je het ineens. En dat is al snel een "Eureka"-moment waarna het ineens lijkt alsof je veel meer van de wereld begrijpt en een stuk slimmer bent geworden. Bovendien heb je dan ineens een slimme extra methode om sommige ingewikkelde problemen eenvoudig op te lossen, van het ontdekken van het juiste pad in een doolhof tot het vinden van een woord in een woordenboek. Daar vertel ik misschien een volgende keer over, want recursie is verrassend veelzijdig. Maar laten we het nu nog even eenvoudig houden. Als je denkt dat je recursie begrijpt, probeer dan eens te voorspellen naar welke paal de jongste novice de eerste schijf verplaatste. Als je dàt weet, dan zou je alvast een zeer goede indruk maken mocht je ooit solliciteren voor het abt-schap van een door de oppergod aangewezen wereldklok-bijhoudend klooster...