Hoofdstuk 4 Recursie
Recursie is een bijzonder krachtig mechanisme dat in diverse programmeertalen gebruikt kan worden. In de meeste talen wordt het echter weinig toegepast en het zijn vooral programmeurs van functionele talen die het gebruiken.
In Scheme kun je nauwelijks serieuze programma's schrijven zonder van recursie gebruik te maken. Nou ja, het kan wel, maar met recursie wordt alles veel eenvoudiger en als je er even voor gaat zitten om het idee van recursie te begrijpen dan zul je zien hoe handig het eigenlijk is en hoe krachtig het is om allerlei vraagstukken mee op te lossen.
4.1 Koker met tennisballen
In de les beginnen we met een spel waarbij we een koker met tennisballen doorgeven en op die manier samen een vraagstuk oplossen. Hier staan de instructies:
- aantal tennisballen tellen
- getallen op de tennisballen optellen
- getallen op de tennisballen transponeren
Iedereen krijgt exact dezelfde instructies.
4.2 Herhaling als opstapje naar recursie
Stel dat je een aantal intervallen hebt, bijvoorbeeld prime, terts, kwart en sext. Dit kun je uitdrukken in getallen en deze in een lijst zetten:
'(1 3 4 6)
Als je alle getallen in dit rijtje met 1 verhoogt dan is het resultaat
'(2 4 5 7)
dus secunde, kwart, kwint, septime als we dit als intervallen interpreteren.
Maar hoe krijg je dit resultaat met een Scheme functie? Je moet dan iets maken dat elk element uit de lijst bekijkt, er 1 bij optelt en het terug in de lijst zet. Of zoiets.
De Scheme-manier is om een nieuwe lijst te construeren, te beginnen bij een lege lijst, en daar één voor één de verhoogde elementen aan toe te voegen, als volgt:
'() 1+1 => 2 '(2) 3+1 => 4 '(2 4) 4+1 => 5 '(2 4 5) 6+1 => 7 '(2 4 5 7)
Laten we het eerste interval uit de lijst bekijken met een functie f1. Je geeft f1 dus de oorspronkelijke lijst. f1 telt 1 bij het eerste interval op en roept vervolgens een tweede functie f2 aan die precies hetzelfde werkt als f1. f1 geeft de rest van de lijst (dus zonder het eerste interval) aan f2 zodat f2 met het tweede interval van de oorspronkelijke lijst werkt. Dan roept f2 een derde functie f3 aan die ook precies hetzelfde werkt en f2 geeft de rest van zijn lijst door aan f3. f3 krijgt in dit geval dus de lijst '(4 6). Tot slot hebben we nog een functie f4 nodig voor het laatste interval. De rest van de lijst is dan leeg omdat f4 met het laatste interval uit de lijst werkt. f4 roept verder geen functie aan maar geeft een lijst met het laatste vergrote interval als resultaat.
(define (f1 lst)
(cons (+ (first lst) 1)
(f2 (rest lst))))
(define (f2 lst)
(cons (+ (first lst) 1)
(f3 (rest lst))))
(define (f3 lst)
(cons (+ (first lst) 1)
(f4 (rest lst))))
(define (f4 lst)
(cons (+ (first lst) 1) '()))
Het verloop is als volgt:
f1 wordt aangeroepen met '(1 3 4 6) f1 neemt het eerste interval en telt er 1 bij op, dus 1+1 => 2 De cons in f1 zet het getal 2 aan het begin van een lijst en plakt er een nieuw te construeren lijst aan vast die door f2 gemaakt moet gaan worden. Daartoe geven roepen we f2 aan met '(3 4 6) als argument. f2 wordt aangeroepen met '(3 4 6) f2 neemt het eerste interval en telt er 1 bij op, dus 3+1 => 4 De cons in f2 zet het getal 4 aan het begin van een lijst en plakt er een nieuw te construeren lijst aan vast die door f3 gemaakt moet gaan worden. Daartoe geven roepen we f3 aan met '(4 6) als argument. f3 wordt aangeroepen met '(4 6) f3 neemt het eerste interval en telt er 1 bij op, dus 4+1 => 5 De cons in f3 zet het getal 5 aan het begin van een lijst en plakt er een nieuw te construeren lijst aan vast die door f4 gemaakt moet gaan worden. Daartoe geven roepen we f4 aan met '(6) als argument. f4 wordt aangeroepen met '(6) f4 neemt het eerste interval en telt er 1 bij op, dus 6+1 => 7 De cons in f4 zet het getal 7 aan het begin van een lijst en plakt er een lege lijst aan vast, dus het resultaat van f4 is '(7). Nu f4 klaar is kan ook f3 zijn werk afmaken, wat resulteert in '(5 7) Nu f3 klaar is kan ook f2 zijn werk afmaken, wat resulteert in '(4 5 7) Nu f2 klaar is kan ook f1 zijn werk afmaken, wat resulteert in '(2 4 5 7)
Op zich werkt dit wel, maar het is niet schaalbaar: als we vragen om 100 intervallen heb je 100 functies nodig en wat nog veel vervelender is: als je niet vooraf weet hoeveel intervallen er in de lijst staan, hoe moet je dan weten hoeveel functies je moet maken?
De oplossing eigenlijk heel eenvoudig. Elk van de vier functies heeft namelijk precies dezelfde structuur: neem een interval uit de lijst, tel er 1 bij op en zet het resultaat aan het begin van een lijst die gemaakt wordt door de volgende functie. Alleen f4 wijkt af omdat die geen volgende functie heeft, maar daar verzinnen we een list voor.
Afbeelding 4.2 "Tom Poes, verzin een list!"
4.2.1 Nog eens hetzelfde maar dan recursief
Afbeelding 4.3 "Recursive beard"
We nemen weer f1, maar laten die nu niet f2 aanroepen maar zichzelf:
(define (f1 lst)
(cons (+ (first lst) 1)
(f1 (rest lst))))
Het gewenste verloop is als volgt:
f1 wordt aangeroepen met '(1 3 4 6) f1 neemt het eerste interval en telt er 1 bij op, dus 1+1 => 2 De cons in f1 zet het getal 2 aan het begin van een lijst en plakt er een nieuw te construeren lijst aan vast die door f1 gemaakt moet gaan worden. Daartoe geven roepen we f1 aan met '(3 4 6) als argument. f1 wordt aangeroepen met '(3 4 6) f1 neemt het eerste interval en telt er 1 bij op, dus 3+1 => 4 De cons in f1 zet het getal 4 aan het begin van een lijst en plakt er een nieuw te construeren lijst aan vast die door f1 gemaakt moet gaan worden. Daartoe geven roepen we f1 aan met '(4 6) als argument. f1 wordt aangeroepen met '(4 6) f1 neemt het eerste interval en telt er 1 bij op, dus 4+1 => 5 De cons in f1 zet het getal 5 aan het begin van een lijst en plakt er een nieuw te construeren lijst aan vast die door f1 gemaakt moet gaan worden. Daartoe geven roepen we f1 aan met '(6) als argument. f1 wordt aangeroepen met '(6) f1 neemt het eerste interval en telt er 1 bij op, dus 6+1 => 7 De cons in f1 zet het getal 7 aan het begin van een lijst en plakt er een nieuw te construeren lijst aan vast die door f1 gemaakt moet gaan worden. Daartoe geven roepen we f1 aan met '() als argument.
Dit is bijna goed. Het levert in ieder geval de gewenste lijst op. Er gaat
alleen op het laatst iets mis: f1 wordt aangeroepen met een lege lijst en
kan er dus niet het eerste interval uit nemen met first. Dat resulteert
in een fout en je programma crasht.
De oplossing is ook hier eenvoudig: kijk in de functie als eerste of de lijst die je krijgt leeg is. Als dat zo is ben je klaar (vergelijk dit met het gedrag van f4 hierboven) en in alle andere gevallen voer je de rest van de functie uit. Dan krijg je dit:
(define (f1 lst)
(if (empty? lst) '()
(cons (+ (first lst) 1)
(f1 (rest lst)))))
4.3 Herhaling m.b.v. recursie
Het volgende voorbeeld laat zien dat een functie 'herhaal' zichzelf aanroept. Hij zal zichzelf blijven aanroepen, dus de naam is wel goed gekozen.
(define (herhaal)
(herhaal))
(herhaal)
Als je dit uitvoert zul je merken dat Racket niet meer naar je luistert.
Dat komt omdat hij druk bezig is om de functie 'herhaal' uit te voeren.
Je zult hem moeten onderbreken. De terminal-versie racket stopt met
control-C (ook vaak geschreven als CTRL-C of ^C).
Ondertussen beleven we er weinig plezier aan. Deze functie doet geen dingen waar we iets aan hebben. Kijk eens naar de volgende:
(define (herhaal) (displayln "Dit kan even gaan duren") (herhaal))
(herhaal)
Als je dit uitvoert zul je merken dat Racket opnieuw niet meer naar je luistert. Je zult hem weer moeten onderbreken.
Er is wel iets meer plezier aan te beleven: je krijgt nu tenminste een scherm vol tekst. Na een paar minuten ben je daar wel op uitgekeken. Laten we iets toevoegen waarmee we kunnen aangeven hoeveel herhalingen we willen.
(define (herhaal n)
(displayln "Dit kan even gaan duren")
(if (<= n 1) (display "Klaar")
(herhaal (- n 1))))
(herhaal 10)
Wat gebeurt er nu? Zet er nog één dingetje tussen om het iets duidelijker
te maken: (display n) (display ": ") en dan wordt de hele functie als
volgt:
(define (herhaal n)
(display n) (display ": ")
(displayln "Dit kan even gaan duren")
(if (<= n 1) (display "Klaar")
(herhaal (- n 1))))
Nu zie je bij het uitvoeren aan het begin van elke regel een regelnummer.
Dat komt door (display n). Daarmee laat je namelijk de waarde van n
zien. De eerste keer dat je de functie aanroept bevat n het aantal dat
je hebt opgegeven.
Kijk eens naar de regel (if (<= n 1) (display "Klaar")
Deze vergelijkt n met 1 en als n kleiner is dan 1 of gelijk aan 1 dan
wordt het woord "Klaar" geschreven en is de functie inderdaad klaar.
Maar nu wordt het interessant. Wat gebeurt er als n NIET kleiner dan of
gelijk aan 1 is, dus bijvoorbeeld 5. Dan wordt de laatste regel weer
uitgevoerd: (herhaal (- n 1))
Deze roept de functie dus opnieuw aan, maar nu met (- n 1) ofwel: hij
vraagt om 1 herhaling minder dan de vorige keer. Het spel begint dan van
voor af aan, maar houd in je achterhoofd dat n nu kleiner is geworden en
met elke regel kleiner wordt tot (if (<= n 1) besluit dat het genoeg
geweest is.
4.4 Recursieve bewerkingen op lijsten
Zoals je weet werken we in Scheme veel met lijsten: lijsten met getallen, lijsten met symbolen en zelfs lijsten met lijsten.
Bij veel van de programma's die we gaan maken nemen we een of meer lijsten als uitgangspunt of gaan we nieuwe lijsten produceren uit het niets. In sommige gevallen willen we geen lijst als resultaat maar bijvoorbeeld een getal of een symbool.
Samenvattend kunnen we veel vraagstukken oplossen met deze bewerkingen:
lijsten produceren uit een of meer lijsten
lijsten produceren uit niets
een enkelvoudig resultaat afleiden uit een lijst
We kijken eerst naar het laatste geval. Stel, we hebben een lijst met getallen en willen weten wat de som van al die getallen is. We gaan alle getallen in de lijst dus bij elkaar optellen. Hoe doe je dat wanneer er geen bestaande functie is die dat voor je doet?
Je zou een rekenmachine kunnen nemen en elk getal uit de lijst daarin overnemen. Voor minder dan vijf getallen is dat nog wel handig, maar bij enkele honderden getallen die ook nog eens kunnen veranderen moeten we iets anders verzinnen.
Je kunt ook alle getallen overnemen in een spreadsheet. Het resultaat kun je dan weer overnemen in je Scheme-programma. Je wint tijd omdat je niet zelf een Scheme-functie hoeft te maken, maar als de lijst met getallen elke minuut verandert werk je je te pletter. Dat moet efficienter kunnen. We gaan zelf even iets creatiefs verzinnen en dan de computer het saaie werk laten doen.
4.4.1 Het aantal elementen in een lijst tellen
Neem een lijst, bijvoorbeeld '(trein auto boot fiets)
Deze bevat vier elementen, dat is vrij eenvoudig te zien. Laten we een
functie count maken die in staat is om één item te tellen, uit de lijst
te verwijderen en vervolgens aan een andere count te vragen hoeveel items
er dan nog overblijven.
Dan doet hij dus het volgende:
(count '(trein auto boot fiets)) (+ 1 (count '(auto boot fiets))) (+ 1 (+ 1 (count '(boot fiets)))) (+ 1 (+ 1 (+ 1 (count '(fiets))))) (+ 1 (+ 1 (+ 1 (+ 1 (count '()))))) (+ 1 (+ 1 (+ 1 (+ 1 0)))) (+ 1 (+ 1 (+ 1 1))) (+ 1 (+ 1 2)) (+ 1 3) 4
4.4.2 Alle getallen in een lijst bij elkaar optellen
Hoe tel je alle getallen in een Scheme-lijst bij elkaar op?
Je zou telkens een getal uit de lijst kunnen nemen, bijvoorbeeld het eerste en een totaal bijhouden waar je het bij optelt. Wanneer de lijst leeg is ben je klaar en bevat het totaal de som van alle getallen.
Een manier die veel meer bij Scheme past is de volgende: beschouw de som van alle getallen in een lijst als het eerste getal plus de som van alle getallen in de rest van de lijst.
Voorbeeld: we hebben een lijst '(10 20 30 40) en we willen de som van alle
elementen berekenen. Zoals gezegd is de som van deze lijst:
10 + de som van '(20 30 40)
Op dezelfde manier kun je de som van '(20 30 40) zien als
20 + de som van '(30 40)
en de som van '(30 40) is
30 + de som van '(40)
de som van '(40) is
40 + de som van '()
en tot slot: de som van '() is 0.
Als de lijst leeg is heb je dus het getal 0 in handen en daarmee kun je voorgaande berekeningen afronden, want die waren nog niet 'af'. We lopen in omgekeerde volgorde het bovenstaande lijstje af en vullen de ontbrekende getallen in:
40 + de som van '() = 40 + 0 = 40
30 + de som van '(40) = 30 + 40 = 70
20 + de som van '(30 40) = 20 + 70 = 90
10 + de som van '(20 30 40) = 10 + 90 = 100
de som van '(10 20 30 40) = 100
Op deze manier heb je de som van alle getallen in de lijst berekend.
4.4.3 De optelfunctie in Scheme bouwen
De essentie is:
(define (add lst) (+ (first lst) (add (rest lst))))
Deze roepen we aan als:
(add '(10 20 30 40))
Er ontbreekt nog een manier om aan te geven dat de functie klaar is. Dat kunnen we doen door te kijken of de lijst nog getallen bevat. Als dat niet zo is, dus als de lijst leeg is, dan stoppen we en geven we als resultaat het getal 0 terug, precies zoals hierboven beschreven.
(define (add lst)
(if (empty? lst) 0
(+ (first lst) (add (rest lst)))))
De functie add begint met de lijst die je hem geeft en roept zichzelf
telkens aan met een kleinere versie van de lijst tot er een moment komt dat
er een add wordt aangeroepen met een lege lijst. Die geeft als resultaat
het getal 0 terug aan de add waardoor hij was aangeroepen en die zal er
een getal bij optellen en dat teruggeven aan de add waardoor hij was
aangeroepen en die zal daar een getal bij optellen en dat teruggeven aan de
add waardoor hij was aangeroepen en die zal daar een getal bij optellen en
dat teruggeven aan de add waardoor hij was aangeroepen en die zal...
... tot we zijn aangekomen bij de add die we zelf hadden aangeroepen. Die
geeft ons het getal dat hij dan kan berekenen door het eerste element uit de
lijst op te tellen bij het getal dat hij van de voorgaande add heeft
gekregen en daarmee is de berekening voltooid.
De hele berekening ziet er dan zo uit:
(+ 10 (add '(20 30 40))) (+ 10 (+ 20 (add '(30 40)))) (+ 10 (+ 20 (+ 30 (add '(40))))) (+ 10 (+ 20 (+ 30 (+ 40 (add '()))))) (+ 10 (+ 20 (+ 30 (+ 40 0)))) (+ 10 (+ 20 (+ 30 40))) (+ 10 (+ 20 70)) (+ 10 90) 100
4.4.4 Nog een voorbeeld maar nu met een lijst
Stel dat we een functie willen maken die een lijst twee keer zo lang maakt door elk element te herhalen. Dus de functie toegepast op de lijst '(a b c d) levert '(a a b b c c d d)
De essentie is:
(define (dubbel lst) (append (list (first lst) (first lst)) (dubbel (rest lst)))))
Deze roepen we aan als:
(dubbel '(a b c d))
Er ontbreekt nog een manier om aan te geven dat de functie klaar is. Dat kunnen we doen door te kijken of de lijst nog elementen bevat. Als dat niet zo is, dus als de lijst leeg is, dan stoppen we en geven we als resultaat een lege lijst terug.
(define (dubbel lst)
(if (empty? lst) '()
(append (list (first lst) (first lst)) (dubbel (rest lst)))))
De functie dubbel begint met de lijst die je hem geeft en roept zichzelf telkens aan met een kleinere versie van de lijst tot er een moment komt dat er een dubbel wordt aangeroepen met een lege lijst. Die geeft als resultaat een lege lijst aan de dubbel waardoor hij was aangeroepen en die zal twee elementen vooraan de resultaatlijst toevoegen en dat resultaat teruggeven aan de dubbel waardoor hij was aangeroepen en die zal twee elementen vooraan de resultaatlijst toevoegen en dat resultaat teruggeven aan de dubbel waardoor hij was aangeroepen en die zal twee elementen vooraan de resultaatlijst toevoegen en dat resultaat teruggeven aan de dubbel waardoor hij was aangeroepen en die zal twee elementen vooraan de resultaatlijst toevoegen en dat resultaat teruggeven aan de dubbel waardoor hij was aangeroepen en dan zijn we aangekomen bij de dubbel die we zelf hadden aangeroepen. Die geeft ons de resultaatlijst.
Het hele verloop ziet er dan zo uit:
(append (list 'a 'a) (dubbel '(b c d))) (append (list 'a 'a) (append (list 'b 'b) (dubbel '(c d)))) (append (list 'a 'a) (append (list 'b 'b) (append (list 'c 'c) (dubbel '(d))))) (append (list 'a 'a) (append (list 'b 'b) (append (list 'c 'c) (append (list 'd 'd) (dubbel '()))))) (append (list 'a 'a) (append (list 'b 'b) (append (list 'c 'c) (append (list 'd 'd) '())))) (append (list 'a 'a) (append (list 'b 'b) (append (list 'c 'c) '(d d)))) (append (list 'a 'a) (append (list 'b 'b) '(c c d d))) (append (list 'a 'a) '(b b c c d d)) '(a a b b c c d d)
4.5 Algemene vorm
Recursieve functies hebben in het algemeen dezelfde kenmerken: de functie
roept zichzelf aan, bij elke aanroep wordt het op te lossen vraagstuk
ietsje kleiner en er is een clausule die aangeeft wanneer het proces klaar
is.
Daarnaast is er meestal een parameter die gebruikt wordt om iets mee te
doen: de input en een resultaat: de output.
Gewoon voor de lol staat hieronder een uitgewerkt voorbeeld van een
algemene recursieve functie die wordt gebruikt om een serie getallen
bij elkaar op te tellen: 5+4+3+2+1. Probeer maar uit met (f 5).
;------------------------------------------------
; operator - wat wil je doen met (een deel van) de input?
; decrement - hoe verklein je het probleem?
; stop? - wanneer stop je?
; output - wat voor vorm heeft je output? Een getal? Een lijst?
;
(define operator (lambda (x y) (+ x y))) ; wat wil je doen met de input?
(define decrement (lambda (x) (- x 1))) ; hoe verklein je het probleem?
(define stop? (lambda (x) (<= x 0))) ; wanneer stop je?
(define output 0) ; wat voor vorm heeft je output?
; Algemene vorm
(define (f input)
(if (stop? input) output
(operator input (f (decrement input)))))
;------------------------------------------------
Nog eentje: een lijst getallen kwadrateren:
;------------------------------------------------
(define operator (lambda (x y) (cons (* (first x) (first x)) y)))
(define decrement (lambda (x) (rest x)))
(define stop? (lambda (x) (empty? x)))
(define output '())
(define (f input)
(if (stop? input) output
(operator input (f (decrement input)))))
;------------------------------------------------
4.6 Lijst of getal in, lijst of getal uit
De vier meest voorkomende varianten bij recursieve functies met per situatie een voorbeeld van een toepassing:
list in, list out transpose
list in, getal out sum
getal in, list out list met random getallen of melodie of zo
getal in, getal out kwadraat
4.7 Staartrecursie (tail recursion)
Dit is een onderwerp waar niet iedereen mee te maken zal krijgen maar voor wie zijn Scheme programma's efficienter (sneller, minder geheugengebruik) wil maken is het erg nuttig om dit te begrijpen.
Recursie is een mechanisme waarmee je met een paar regels code de computer flink voor je aan het werk kunt zetten. Het heeft echter een nadeel: het gebruikt nogal wat geheugen en processorkracht en daarom kan het langzaam zijn en soms niet eens in het geheugen passen.
Dat kun je in veel gevallen efficienter maken door tail recursion te gebruiken. In plaats van de deelresultaten telkens uit te stellen tot de volgende recursieve aanroep hou je bij elke aanroep een deelresultaat bij. Aan het eind heb je dan meteen het eindresultaat dat je kunt teruggeven en hoef je niet helemaal terug naar het begin om alle deelresultaten samen te voegen.
Voorbeeld: maak een lijst gevuld met 25 random waarden tussen 0 en 10.
Gewone recursie
(define (randomlist n)
(if (= n 0) '() ; geef lege lijst en wandel terug naar boven
(cons (random 10) (randomlist (- n 1)))))
Aanroepen:
(randomlist 25)
Tail recursion
(define (randomlist n (lst '())) ; lst bevat deelresultaat
(if (= n 0) lst ; geef resultaatlijst terug en klaar
(randomlist (- n 1) (cons (random 10) lst))))
Aanroepen:
(randomlist 25)
Als de recursieve aanroep de laatste in een functie is dan spreek je van staartrecursie. De recursieve aanroep kan dan direct geëvalueerd worden en hoeft niet op de stack gezet te worden.
Als de recursieve aanroep echter deel uitmaakt van een constructie die pas geëvalueerd kan worden als de recursie met zijn resultaat terugkomt wordt elke aanroep op de stack gezet en is er dus geen sprake van staartrecursie.
4.7.1 Efficiency demo
Een voorbeeld dat mooi het verschil in efficientie laat zien is het berekenen van het maximum in een lijst met getallen. Bekijk de volgende implementaties eens en probeer ze uit met de lijst die onderaan staat.
; no tail-recursion: determine the maximum at the end
(define (list-max lst)
(if (empty? lst) 0
(if (> (first lst) (list-max (rest lst)))
(first lst)
(list-max (rest lst)))))
; tail-recursion: calculate the maximum-so-far before the recursive call
(define (list-max lst (n 0))
(if (empty? lst) n
(list-max (rest lst) (if (> (first lst) n) (first lst) n))))
(define testlist '(2 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 27 28))
Begrijp je waarom de eerste versie er zo lang over doet?
4.7.2 Nog een paar voorbeelden
Hieronder staan nog een paar voorbeelden van functies die we al kennen, maar nu omgeschreven zodat ze 'tail-recursive' zijn.
(define (count lst (n 0))
(if (empty? lst) n
(count (rest lst) (+ n 1))))
(define (sum lst (n 0))
(if (empty? lst) n
(sum (rest lst) (+ n (first lst)))))
(define (product lst (n 1))
(if (empty? lst) n
(product (rest lst) (* n (first lst)))))
(define (randomlist top n (lst '()))
(if (<= n 0) lst
(randomlist top (- n 1) (cons (random top) lst))))
Als je lijsten produceert moet je goed de volgorde in de gaten houden. De
manier met cons die we bij gewone recursie gebruiken levert niet altijd
de juiste volgorde op.
(define (transpose lst n (result '()))
(if (empty? lst) (reverse result)
(transpose (rest lst) n (cons (+ (first lst) n) result))))
(define (transpose-new lst n (result '()))
(if (empty? lst) result
(transpose-new (rest lst) n (append result (list (+ (first lst) n))))))