In de wiskunde bestaan er zogenaamde recurente betrekkingen.
Dit zijn betrekkingen die worden uitgedrukt in termen van zichzelf.
Bij de meeste programmeertalen is dit principe ook bekend en wordt het daar recursie genoemd.
In Pascal kun je recursie vinden bij procedures en functies.
Het bovenstaande klinkt allemaal misschien wat vaag en abstract, dus laten we maar eens aan de hand van een voorbeeld kijken hoe een en ander in zijn werk gaat.
Ik gebruik hiervoor het voorbeeld dat bijna overal voor dit onderwerp wordt gebruikt en dat is het berekenen van een faculteit.
De faculteit van een getal zegt op hoeveel verschillende manieren een verzameling van getal elementen gesorteerd kan worden.
Zo kun je 2 pennen op 2 verschillende manieren naast elkander leggen.
Drie pennen kun je al op 6 verschillende manieren naast elkaar leggen: 123, 132, 213, 231, 312 en 321.
Vijf pennen op 120 manieren!
De berekening die hierachter zit is zeer eenvoudig: het is de vermenigvuldiging van 1 t/m het getal waarvan je de faculteit wilt weten.
Dus de faculteit van 3 (de wiskundige notatie is 3!, het uitroepteken staat dus voor faculteit) is niets anders dan 1x2x3.
En zo is 4!=1x2x3x4=24, en 5!=1x2x3x4x5=120.
Een functie die dit uitrekent is niet moeilijk te maken (zie opgave 11.1).
Nu gaan we eens op een andere manier tegen deze vermenigvuldigingen aankijken.
2!=1×2. 3!=1x2x3, met haken geschreven: 3!=(1×2)x3, waarbij ik het deel tussen haken kan vervangen (substitutie) door 2!, want dat is immers ook 1×2. Dan krijg ik dus 3!=2!x3.
Voor 4! kan ik hetzelfde doen: 4!=(1x2x3)x4 –> 4!=3!x4, want 3!=1x2x3.
Ik hoop dat je ziet dat ik een manier heb gevonden om een faculteit uit te drukken in een vermenigvuldiging tussen een getal en een andere faculteit, ofwel ik druk de oplossing uit in termen van zichzelf.
In z’n algemeenheid geldt dat n!=(n-1)!*n, ga dat maar even na.
En nu komt de grap van dit verhaal: We kunnen dit (min of meer) één op één programmeren.
In Pascal ziet dat er zo uit:
function Fac(n: byte): integer;
begin
Fac := Fac(n-1) * n;
end;
De code hierboven werkt overigens niet naar behoren. Mocht je dit toch in een programma doen, dan krijg je een run-time error.
Het probleem is namelijk dat de functie zichzelf aanroept, maar zoals hierboven geprogrammeerd daar eindeloos mee doorgaat. Daar het geheugen van een computer eindig is komt er een punt van conflict, vandaar de run-time error.
Even tussen haakjes: (het geheugen waar we hier over praten is het stack-geheugen. Dat is een stukje geheugen, dat een programmeertaal reserveert om tussentijdse zaken op te slaan. Dit stukje geheugen is vaak zeer beperkt en dat leidt als snel tot een stack-overflow.).
We moeten er dus voor zorgen dat de aanroep van zichzelf op enig moment stopt.
In het geval van faculteiten moeten we kijken naar de (wiskundige) definitie:
vanwege wiskundig gemak is 0! gedefinieerd als 1, dus 0!=1. Voor alle overige (positief gehele) getallen geldt bovenstaande regel.
De stop zit dus kennelijk bij 0. In de code kunnen we dit met een if-constructie testen.
function Fac(n: byte): integer;
begin
if n = 0 then
Fac := 1
else
Fac := Fac(n-1) * n;
end;
BELANGRIJK: Bij een recursieve functie (of procedure) moet je ALTIJD een stop inbouwen!
Wanneer maak je nu goed gebruik van dit mechanisme? Om een antwoord te vinden op die vraag moete we eerst de eigenschappen van recursie tegenover die van iteratie zetten.
De voordelen van recursie t.o.v. iteratie zijn:
– gemakkelijk te coderen (als het onderwerp nieuw is, dan na enige oefening)
– vaak korte code
– soms onvermijdbaar
De nadelen van recursie t.o.v. iteratie zijn:
– aanslag op geheugen en daardoor
– trage(re) uitvoering
Het antwoord op bovenstaande vraag luidt (hoewel enigszins subjectief):
Recursie gebruik je wanneer een iteratieve oplossing dan wel te ingewikkeld, dan wel onmogelijk is.
In alle andere gevallen maak je gebruik van iteratieve oplossingen!
Voor een non-voorbeeld van recursie verwijs ik hier naar opgave 11.2.
Een mooi voorbeeld waar een iteratieve oplossing niet voor de hand ligt (onmogelijk is??) is de ’torens van Hanoi’.
Het verhaal gaat dat er ooit (ergens in de middeleeuwen) in de buurt van Hanoi een kloosterorde was die het volgende had bedacht:
Het einde van de wereld is nabij en wij kunnen aangeven wanneer, en wel als volgt:
We hebben 3 palen en 64 massief stenen schijven (met in het midden een gat) met allemaal verschillende diameter.
We leggen alle schijven om de eerste paal van groot (onder) tot klein (boven).
Nu gaan we ervoor zorgen dat deze stapel schijven van paal 1 naar paal 3 wordt verplaatst onder de volgende twee condities:
Per zet mag slechts 1 schijf worden verplaatst en er mag nooit een grotere schijf boven een kleinere komen.
Wanneer we hiermee klaar zijn zal de wereld vergaan!
Maakt u zich vooral niet druk dat u dit nog zal meemaken. Dit proces neemt minstens 213.503.982.335 millenia in beslag, onder de aanname dat de monikken 1 zet per seconde doen en geen fouten maken. En daarbij zal de aarde dan inderdaad al vergaan zijn!
Laten we eens bescheiden doen en eens kijken of we het spelletje met de 3 palen en schijven kunnen oplossen met iets minder schijven.
We gaan eerst eens kijken met 1 schijf. De palen noemen we even A, B en C. De uitgangspositie zal steeds alle schijven op paal A zijn.
Het doel om de schijven naar paal C te krijgen, waarbij paal B als hulp-paal dient.
De oplossing voor 1 schijf is gemakkelijk, nl: verplaats de schijf van paal A naar paal C en klaar. We noteren dit als A->C.
Met 2 schijven gat het als volgt: A->B, A->C, B->C. Teken de stappen maar uit als je het niet direct ziet.
Met 3 schijven is dit de oplossing: A->C, A->B, C->B, A->C, B->A, B->C, A->C.
Met 1 schijf zijn we in 1 beurt klaar, met 2 schijven hebben we 3 beurten nodig en met 3 schijven 7 beurten.
Hoeveel beurten hebben we met n schijven nodig? Wel dat is n²-1. Met 64 schijven is dat een gigantisch getal.
Kunnen we de oplossing van dit probleem programmeren? Een iteratieve oplossing heb ik nog nooit gevonden (behalve een flauwe, waarbij je zelf recursie programmeert). Eer recursieve oplossing daarentegen is zeer gemakkelijk.
De recursieve oplossing vertaald in vrij Nederlands luidt:
Als er 1 schijf is verplaats die dan van paal A naar paal C.
Zijn er meer schijven dan:
1. Verplaats alle schijven behalve de onderste van paal A naar paal B,
2. Verplaats de schijf van paal A naar paal C,
3.Verplaats alle schijven van paal B naar paal C.
Merk op dat de recursie in stap 1 en stap 3 zit.
Ok, hier komt de procedure:
procedure Verplaats(n: Byte;p1, p2, p3: char);
begin
if n=1 then
write(p1,’->’,p3)
else
begin
Verplaats(n-1,p1,p3,p2);
write(p1,’->’,p3);
Verplaats(n-1,p2,p1,p3);
end;
end;
Je kunt de procedure Verplaats(n, p1, p2, p3) het beste lezen als: verplaats n stenen van p1 via p2 naar p3.
Om de oplossingen te krijgen zoals hierboven genoteerd roep je de procedure als volgt aan: Verplaats(3,’A’,’B’,’C’).
Voor verdere uitvoer zie opgave 11.3.
Oefeningen.
11.1
Maak een functie FacIter(n: byte): integer, die d.m.v. een vermenigvuldiging de faculteit van n uitrekent. [Antwoord]
11.2
De rij van Fibonacci ziet er als volgt uit: 1, 1, 2, 3, 5, 8, 13, 21, 34, …(zie ook opgave 9.1)
De eerste 2 termen zijn 1, de daarop volgende termen is steeds de som van de voorgaande twee termen.
Schrijf een programma dat de n-de term van de rij van Fibonacci berekent.
Maak in je programma gebruik van een recursieve functie FibRec en een iteratieve functie FibIter.
Laat het programma de n-de term als invoer aan de gebruiker vragen, waarna
het programma eerst de uitkomst van FibIter laat zien en daarna de uitkomst van FibRec.
Experimenteer met steeds grotere waarde van n (doe dat in kleine stapjes!). Let daarbij niet op de uitkomst.
Merk op dat FibRec er steeds langer over gaat doen en probeer hiervoor een verklaring te geven.[Antwoord]
11.3
Maak een programma dat de ’torens van hanoi’ speelt.
Het aantal stenen moet als invoer door de gebruiker worden gegeven. [Antwoord]
11.4
Schrijf een recursieve functie Keerom(s: s80): s80 die de string s omdraait, waarbij s80 als string[80] is gedefinieerd. [Antwoord]
11.5
Schrijf een recursieve functie Keer(a,b: integer): integer, die middels herhaald optellen axb uitrekent. [Antwoord]
11.6
Bekijk onderstaande functie:
function V(a,b: integer): integer;
begin
if a=1 then
V := b
else
if a mod 2 = 1 then {als a oneven is}
V := V(a div 2, b * 2) + b { met div reken je de gehele deling uit, het deel rechts van de staartdeling}
else
V := V(a div 2, b * 2)
end;
Verklaar zonder deze functie te implementeren wat deze functie met a en b doet. [Antwoord]
[Bestanden] <– –> [Gestructureerde types]