In de wiskunde bestaan er zogenaamde recurente betrekkingen.
\nDit zijn betrekkingen die worden uitgedrukt in termen van zichzelf.
\nBij de meeste programmeertalen is dit principe ook bekend en wordt het daar\u00a0recursie<\/i>\u00a0genoemd.
\nIn Pascal kun je recursie vinden bij procedures en functies.
\nHet 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.
\nIk gebruik hiervoor het voorbeeld dat bijna overal voor dit onderwerp wordt gebruikt en dat is het berekenen van een faculteit.
\nDe faculteit van een getal zegt op hoeveel verschillende manieren een verzameling van\u00a0getal<\/i>\u00a0elementen gesorteerd kan worden.
\nZo kun je 2 pennen op 2 verschillende manieren naast elkander leggen.
\nDrie pennen kun je al op 6 verschillende manieren naast elkaar leggen: 123, 132, 213, 231, 312 en 321.
\nVijf pennen op 120 manieren!<\/p>\n
De berekening die hierachter zit is zeer eenvoudig: het is de vermenigvuldiging van 1 t\/m het getal waarvan je de faculteit wilt weten. 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. function Fac(n: byte): integer; De code hierboven werkt overigens niet naar behoren. Mocht je dit toch in een programma doen, dan krijg je een 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.).<\/p>\n We moeten er dus voor zorgen dat de aanroep van zichzelf op enig moment stopt. function Fac(n: byte): integer; BELANGRIJK: Bij een recursieve functie (of procedure) moet je\u00a0ALTIJD<\/u>\u00a0een stop inbouwen!<\/b><\/p>\n 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 nadelen van recursie t.o.v. iteratie zijn: Het antwoord op bovenstaande vraag luidt (hoewel enigszins subjectief): Voor een non-voorbeeld van recursie verwijs ik hier naar\u00a0opgave 11.2<\/a>.<\/p>\n Een mooi voorbeeld waar een iteratieve oplossing niet voor de hand ligt (onmogelijk is??) is de ’torens van Hanoi’. Laten we eens bescheiden doen en eens kijken of we het spelletje met de 3 palen en schijven kunnen oplossen met iets minder schijven. 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. Merk op dat de recursie in stap 1 en stap 3 zit. procedure Verplaats(n: Byte;p1, p2, p3: char);<\/span> <\/a>11.1<\/b> <\/a>11.2<\/b> <\/a>11.3<\/b> 11.4<\/b> 11.5<\/b> 11.6<\/b> function V(a,b: integer): integer;<\/span>
\nDus de faculteit van 3 (de wiskundige notatie is 3!, het uitroepteken staat dus voor faculteit) is niets anders dan 1x2x3.
\nEn zo is 4!=1x2x3x4=24, en 5!=1x2x3x4x5=120.
\nEen functie die dit uitrekent is niet moeilijk te maken (zie\u00a0opgave 11.1<\/a>).
\nNu gaan we eens op een andere manier tegen deze vermenigvuldigingen aankijken.<\/p>\n
\nVoor 4! kan ik hetzelfde doen: 4!=(1x2x3)x4 –> 4!=3!x4, want 3!=1x2x3.
\nIk 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.
\nIn z’n algemeenheid geldt dat n!=(n-1)!*n, ga dat maar even na.
\nEn nu komt de grap van dit verhaal: We kunnen dit (min of meer) \u00e9\u00e9n op \u00e9\u00e9n programmeren.
\nIn Pascal ziet dat er zo uit:<\/p>\n
\nbegin
\nFac := Fac(n-1) * n;
\nend;<\/span><\/p>\n
\nHet 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.<\/p>\n
\nIn het geval van faculteiten moeten we kijken naar de (wiskundige) definitie:
\nvanwege wiskundig gemak is 0! gedefinieerd als 1, dus 0!=1. Voor alle overige (positief gehele) getallen geldt bovenstaande regel.
\nDe stop zit dus kennelijk bij 0. In de code kunnen we dit met een if-constructie testen.<\/p>\n
\nbegin
\nif n = 0 then
\nFac := 1
\nelse
\nFac := Fac(n-1) * n;
\nend;<\/span><\/p>\n
\nDe voordelen van recursie t.o.v. iteratie zijn:
\n– gemakkelijk te coderen (als het onderwerp nieuw is, dan na enige oefening)
\n– vaak korte code
\n– soms onvermijdbaar<\/p>\n
\n– aanslag op geheugen en daardoor
\n– trage(re) uitvoering<\/p>\n
\nRecursie gebruik je wanneer een iteratieve oplossing dan wel te ingewikkeld, dan wel onmogelijk is.
\nIn alle andere gevallen maak je gebruik van iteratieve oplossingen!<\/p>\n
\nHet verhaal gaat dat er ooit (ergens in de middeleeuwen) in de buurt van Hanoi een kloosterorde was die het volgende had bedacht:
\nHet einde van de wereld is nabij en wij kunnen aangeven wanneer, en wel als volgt:
\nWe hebben 3 palen en 64 massief stenen schijven (met in het midden een gat) met allemaal verschillende diameter.
\nWe leggen alle schijven om de eerste paal van groot (onder) tot klein (boven).
\nNu gaan we ervoor zorgen dat deze stapel schijven van paal 1 naar paal 3 wordt verplaatst onder de volgende twee condities:
\nPer zet mag slechts 1 schijf worden verplaatst en er mag nooit een grotere schijf boven een kleinere komen.
\nWanneer we hiermee klaar zijn zal de wereld vergaan!
\nMaakt 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!<\/p>\n
\nWe 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.
\nHet doel om de schijven naar paal C te krijgen, waarbij paal B als hulp-paal dient.
\nDe oplossing voor 1 schijf is gemakkelijk, nl: verplaats de schijf van paal A naar paal C en klaar. We noteren dit als A->C.
\nMet 2 schijven gat het als volgt: A->B, A->C, B->C. Teken de stappen maar uit als je het niet direct ziet.
\nMet 3 schijven is dit de oplossing: A->C, A->B, C->B, A->C, B->A, B->C, A->C.
\nMet 1 schijf zijn we in 1 beurt klaar, met 2 schijven hebben we 3 beurten nodig en met 3 schijven 7 beurten.
\nHoeveel beurten hebben we met n schijven nodig? Wel dat is n\u00b2-1. Met 64 schijven is dat een gigantisch getal.<\/p>\n
\nDe recursieve oplossing vertaald in vrij Nederlands luidt:
\nAls er 1 schijf is verplaats die dan van paal A naar paal C.
\nZijn er meer schijven dan:
\n1. Verplaats alle schijven behalve de onderste van paal A naar paal B,
\n2. Verplaats de schijf van paal A naar paal C,
\n3.Verplaats alle schijven van paal B naar paal C.<\/p>\n
\nOk, hier komt de procedure:<\/p>\n
\nbegin<\/span>
\n\u00a0 if n=1 then<\/span>
\n\u00a0 \u00a0 write(p1,’->’,p3)<\/span>
\n\u00a0 else<\/span>
\n\u00a0 \u00a0 begin<\/span>
\n\u00a0 \u00a0 \u00a0 Verplaats(n-1,p1,p3,p2);<\/span>
\n\u00a0 \u00a0 \u00a0 write(p1,’->’,p3);<\/span>
\n\u00a0 \u00a0 \u00a0 Verplaats(n-1,p2,p1,p3);<\/span>
\n\u00a0 \u00a0 end;<\/span>
\nend;<\/span>
\n<\/b><\/span>
\nJe kunt de procedure\u00a0Verplaats(n, p1, p2, p3)<\/b>\u00a0het beste lezen als: verplaats n stenen van p1 via p2 naar p3.
\nOm de oplossingen te krijgen zoals hierboven genoteerd roep je de procedure als volgt aan: Verplaats(3,’A’,’B’,’C’).
\nVoor verdere uitvoer zie\u00a0opgave 11.3<\/a>.<\/p>\nOefeningen.<\/h2>\n
\nMaak een functie\u00a0FacIter(n: byte): integer<\/b>, die d.m.v. een vermenigvuldiging de faculteit van n uitrekent. [Antwoord<\/a>]\n
\nDe rij van Fibonacci ziet er als volgt uit: 1, 1, 2, 3, 5, 8, 13, 21, 34, …(zie ook opgave\u00a09.1<\/a>)
\nDe eerste 2 termen zijn 1, de daarop volgende termen is steeds de som van de voorgaande twee termen.
\nSchrijf een programma dat de n-de term van de rij van Fibonacci berekent.
\nMaak in je programma gebruik van een recursieve functie FibRec en een iteratieve functie FibIter.
\nLaat het programma de n-de term als invoer aan de gebruiker vragen, waarna
\nhet programma eerst de uitkomst van FibIter laat zien en daarna de uitkomst van FibRec.
\nExperimenteer met steeds grotere waarde van n (doe dat in kleine stapjes!). Let daarbij niet op de uitkomst.
\nMerk op dat FibRec er steeds langer over gaat doen en probeer hiervoor een verklaring te geven.[Antwoord<\/a>]\n
\nMaak een programma dat de ’torens van hanoi’ speelt.
\nHet aantal stenen moet als invoer door de gebruiker worden gegeven. [Antwoord<\/a>]\n
\nSchrijf een recursieve functie\u00a0Keerom(s: s80): s80<\/b>\u00a0die de string s omdraait, waarbij s80 als string[80] is gedefinieerd. [Antwoord<\/a>]\n
\nSchrijf een recursieve functie\u00a0Keer(a,b: integer): integer<\/b>, die middels herhaald optellen axb uitrekent. [Antwoord<\/a>]\n
\nBekijk onderstaande functie:<\/p>\n
\nbegin<\/span>
\n\u00a0 if a=1 then<\/span>
\n\u00a0 \u00a0 V := b<\/span>
\n\u00a0 else<\/span>
\n\u00a0 \u00a0 if a mod 2 = 1 then {als a oneven is}<\/span>
\n\u00a0 \u00a0 \u00a0 V := V(a div 2, b * 2) + b { met div reken je de gehele deling uit, het deel rechts van de staartdeling}<\/span>
\n\u00a0 \u00a0 else<\/span>
\n\u00a0 \u00a0 \u00a0 V := V(a div 2, b * 2)<\/span>
\nend;<\/span>
\n<\/b><\/span>
\nVerklaar zonder deze functie te implementeren wat deze functie met\u00a0a<\/i>\u00a0en\u00a0b<\/i>\u00a0doet. [Antwoord<\/a>]\n