Bijlage: Recursief tellen

Wat was het probleem?
Bekijk alle verschillende rijtjes met lengte 15 die uit enen en nullen. In totaal zijn dat er 215 = 32768. Dat is niet moeilijk; op elke positie heb je een keuze uit twee mogelijkheden. Maar hoeveel zijn het er als je als extra voorwaarde stelt dat er geen twee nullen achter elkaar mag staan? Dit probleem is niet meer zo eenvoudig. Toch is er een methode die hier hulp brengt. Die methode heet recursief tellen. Je telt eerst het aantal rijtjes bij een kortere lengte, bijvoorbeeld rijtjes met lengte 1 en rijtjes met lengte 2. Die kun je "gewoon" tellen"

lengte 1

0

1

 

 

 

aantal(1) = 2

lengte 2

01

10

11

 

 

aantal(2) = 3

lengte 3

010

011

101

110

111

aantal(3) = 5

De vraag is nu: wat is aantal(15)?

Een recursieve oplossing
Je kunt het beste eerst nadenken over aantal(4). Gevraagd is dus het aantal rijtjes met lengte 4 waarin geen twee nullen achter elkaar staan. Een rijtje van 4 ontstaat als je achter een rijtje van lengte 3 een extra symbool zet. Je kunt ook zeggen dat het ontstaat als je voor een symbool een rijtje van drie symbolen neerzet!

Achteraan kun je een 0 of een 1 neerzetten. Dat betekent dat het totale aantal bestaat uit twee deelgroepen;

deelgroep 1: Er staat een 1 achteraan

De rijtjes hebben in dit geval het "skelet" * * * 1. Voor die laatste 1 mag je neerzetten wat je wilt. Als er maar geen twee nullen achter elkaar staan. Dat betekent dat je alle toegestane rijtjes met lengte drie ervoor mag plaatsen.

En dat zijn er aantal(3) = 5. De rijtjes die op die manier ontstaan zijn:

0101

0111

1011

1101

1111

deelgroep 2: Er staat een 0 achteraan

De rijtjes hebben in dit geval als "skelet" * * * 0. Voor die laatste 0 mag je nu geen 0 neerzetten. Anders staan er twee nullen achter elkaar. Er moet dus een 1 voor die nul achteraan staan. Het skelet is dus * * 1 0.
Nu moet je nog een rijtje met lengte twee ervoor plaatsen. Maar het aantal mogelijkheden is dan nog gelijk aan aantal(2) = 3. Dat zijn namelijk alle toegestane mogelijkheden. De rijtjes die op die manier ontstaan zijn:

1110

0110

1010

In totaal zijn er dus acht rijtjes.

0101

0111

1011

1101

1111

1110

0110

1010

Dat aantal heb je bepaald zonder gewoon te tellen. Je hebt gebruik gemaakt van de formule:

aantal(4) = aantal(3) + aantal(2)

Aantal(4) bereken je dus met getallen die je al kent. Op dezelfde wijze kun je nu aantal(5) bepalen. Het aantal toegestane dat eindigt op een 1 is aantal(4) = 8 en het aantal toegestane rijtjes dat eindigt op 1 0 is aantal(3) = 5.
Dus aantal(5) = 8 + 5 = 13. Algemeen geldt:

aantal(n) = aantal(n -1) + aantal(n - 2) met n > 2

Er zijn namelijk aantal(n-1) toegestane rijtjes die eindigen op een 1 en aantal(n-2) toegestane rijtjes die eindigen op 10. En samen zijn dat alle toegestane rijtjes. Je telt namelijk niks dubbel (als een rijtje op een 1 eindigt kan het niet meer op 1 0 eindigen) en bovendien vergeet je niks (een rij eindigt op een 1 of op een 1 0 ; een andere mogelijkheid is er niet)

Met de GR of Excel of andere geschikte software kun je nu aantal(15) bepalen. hieronder zie je een tabel met de eerste 15 aantallen

n

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

aantal(n)

2

3

5

8

13

21

34

55

89

144

233

377

610

987

1597

De getallen in deze rij heten de getallen van Fibonacci. De rij van Fibonacci duikt in vele onderdelen van de wiskunde op.

Een nadeel van een recursief nadeel is het feit dat je alle voorgangers moet uitrekenen. Als je aantal(10000) wilt weten dan moet je ook aantal(9999) en aantal(9998) kennen. Maar daarvoor heb je weer aantal(9997) en aantal(9996) nodig etc. In dit geval bestaat er ook een directe formule. Het lijkt misschien ongelofelijk maar de rij Fibonaccigetallen worden ook gegeven door:

Een formule die je niet zo maar kunt zien. Hij kan afgeleid worden uit de recursieve formule maar daar gaan we verder niet op in.

Recursie kan in veel situaties ingezet worden. Een bekend voorbeeld is het probleem van de torens van Hanoi. Dat spelletje zie je hieronder. De spelregels staan in het kleine venster. De vraag is natuurlijk: bepaal het minimale aantal verplaatsingen dat je nodig hebt?

In het figuur hierboven zijn al twee schijven verplaatst. Eerst is de kleinste schijf naar het midden gebracht, daarna de iets grotere schijf naar het rechterplatform en tenslotte is de kleinste schijf op die ene schijf aan de rechterkant geplaatst.

Ook dit probleem is eenvoudig met recursie oplosbaar. Noem het (minimale) aantal zetten bij n schijven x(n). 
Gevraagd is dus x(5).

Als je een stapel van vijf schijven wilt verplaatsen dan moet je eerst de bovenste vier schijven naar het midden verplaatsen. Dat kan op x(4) manieren. Vervolgens leg je de grootste schijf aan de rechterkant; die ligt dan goed. Daarna moet je de vier schijven in het midden op die grootste schijf aan de rechterkant zien te krijgen. Daar heb je weer x(4) verplaatsingen voor nodig. In totaal heb je dus x(4) + 1 + x(4) = 2.x(4) + 1 verplaatsingen nodig.

Op precies dezelfde manier beredeneer je dat x(n) = 2.x(n-1) + 1. Met deze recursieve betrekking bereken je nu snel het aantal verplaatsingen. Als er precies één schijf links ligt dan ben je met één verplaatsing klaar, dus x(1) = 1

Verder volgt:

x(2)

= 2.x(1) + 1

= 2.1 + 1

= 3

x(3)

= 2.x(2) + 1

= 2.3 + 1

= 7

x(4)

= 2.x(3) + 1

= 2.7 + 1 

= 15

x(5)

= 2.x(2) + 1

= 2.15 + 1

= 31

Ook nu is er weer een directe formule: x(n) = 2n -1. Als je start met 100 schijven dan moet je 1267650600228229401496703205375 keer een schijf verplaatsen.

Recursie is een krachtig hulpmiddel. Het grote probleem is natuurlijk het vinden van het voorschrift. Bij het rijtjesprobleem "zet" je een positie vast en dat leverde twee deelgroepen op. Bij de torens van Hanoi hou je in feite ook een plaats vast: de onderste schijf en kijk je wat je met de rest van de schijven verder doet. Bij andere problemen kun je deze technieken ook vaak gebruiken.

De uitleg bij de torens van Hanoi en historische achtergronden bij die puzzel kun je vinden via de link torens Hanoi . En wie digitaal wil schuiven kan terecht bij schuiven maar.