4 Soorten Recursie en Soorten Processen
4.1 Add: Optelling a.d.h.v. increment en decrement
Veronderstel dat je beschikt over een voorgedefinieerde increment-functie 1+ (resp. decrement-functie 1-) die één enkel argument neemt en er 1 bij optelt (resp. van aftrekt). Definieer nu zelf de optelling (add a b) aan de hand van deze increment- en decrement functies.
(define (1- x) (- x 1)) (define (1+ x) (+ 1 x))
4.1.1 Add: Iteratief proces (Staartrecursie)
Schrijf een versie van add die een iteratief proces genereert d.m.v. staartrecursie. Noem deze versie (iter-add a b). Ook hier mag je ervan uitgaan dat a en b positievegetallen zijn.
(define (iter-add a b) (if (= a 0) b (iter-add (1- a) (1+ b))))
> (iter-add 4 5) 9
4.1.2 Add: Recursief proces (Constructieve Recursie)
Schrijf een versie van add die een recursief process genereert. Noem deze versie (rec-add a b). Je mag ervan uitgaan dat a en b positieve getallen zijn.
(define (rec-add a b) (if (= b 0) a (1+ (rec-add a (1- b)))))
> (rec-add 4 5) 9
4.2 Multiply: Linear proces (Recursief & Iteratief)
In paragraaf 1.2.4 van Abelson & Sussman wordt de machtsverheffing gedefinieerd in termen van de vermenigvuldiging. Definieer nu op analoge wijze de vermenigvuldiging aan de hand van de optelling. Schrijf hiervoor een functie die twee positieve getallen vermenigvuldigt, en die als volgt werkt:
\[a \times 0 = 0\\a \times 1 = (a \times 0) + a\\a \times 2 = (a \times 1) + a\]
Doe dit zowel op recursieve als iteratieve wijze. Noem de recursieve versie (rec-multiply a b). Noem de iteratieve versie (iter-multiply a b).
(define (rec-multiply a b) (if (zero? b) 0 (+ a (rec-multiply a (- b 1))))) (define (iter-multiply a b) (define (iter result counter) (if (zero? counter) result (iter (+ result a) (- counter 1)))) (iter 0 b))
> (rec-multiply 5 2) 10
> (iter-multiply 5 2) 10
4.3 Multiply: Logaritmisch proces (Recursief & Iteratief)
Veronderstel dat je beschikt over procedures (double a) en (halve a) die hun argument verdubbelen respectievelijk halveren. Definieer een functie die hetzelfde is als de multiply uit de vorige vraag, maar die in logaritmische tijd haar resultaat berekent. Doe dit zowel op recursieve als op iteratieve wijze. Noem de recursieve versie (rec-fast-multiply a b). Noem de iteratieve versie (iter-fast-multiply a b).
Hint: Gebruik de analogie met de definitie van fast-expt uit Abelson&Sussman paragraaf 1.2.4
(define (double x) (+ x x)) (define (halve x) (/ x 2))
(define (square x) (* x x)) (define (rec-fast-multiply a b) (cond ((zero? b) 0) ((even? b) (rec-fast-multiply (double a) (halve b))) (else (+ a (rec-fast-multiply a (- b 1)))))) (define (iter-fast-multiply a b) (define (iter a b acc) (cond ((zero? b) acc) ((even? b) (iter (double a) (halve b) acc)) (else (iter a (- b 1) (+ acc a))))) (iter a b 0))
> (rec-fast-multiply 3 4) 12
> (rec-fast-multiply 100 200) 20000
> (iter-fast-multiply 3 4) 12
> (iter-fast-multiply 100 200) 20000
4.4 Mutuele recursie: De Hofstadter-reeksen
In zijn beroemde boek "Gödel, Escher, Bach" beschrijft Douglas Hofstadter tal van reeksen, waaronder de Vrouwelijk (\(V\)) en Mannelijk (\(M\)) reeksen. Deze reeksen worden als volgt gedefinieerd:
\[V (n) = \left\lbrace\begin{array}{ll} 1 & \mbox{als } n=0 \\ n - M(V(n-1)) & \mbox{als } n>0 \\ \end{array}\right.\]
\[M (n) = \left\lbrace\begin{array}{ll} 0 & \mbox{als } n=0 \\ n - V(M(n-1)) & \mbox{als } n>0 \\ \end{array}\right.\]
Implementeer de mutueel-recursieve procedures (hofstadter-V n) en (hofstadter-M n) om het n-de getal van respectievelijk de Vrouwelijk en Mannelijk reeksen te berekenen.
(define (hofstadter-V n) (if (= n 0) 1 (- n (hofstadter-M (hofstadter-V (- n 1)))))) (define (hofstadter-M n) (if (= n 0) 0 (- n (hofstadter-V (hofstadter-M (- n 1))))))
> (hofstadter-V 7) 5
> (hofstadter-M 7) 4
4.5 Mutuele recursie: De Hofstadter-reeksen printen d.m.v. do
Schrijf een procedure (hofstadter-reeksen n) die een tabel print met de eerste n elementen van de vrouwelijke reeks in de linker kolom, en de eerste n elementen van de mannelijke reeks in de rechter kolom. Implementeer hofstadter-reeksen door gebruik te maken van een do-lus.
(define (hofstadter-V n) (if (= n 0) 1 (- n (hofstadter-M (hofstadter-V (- n 1)))))) (define (hofstadter-M n) (if (= n 0) 0 (- n (hofstadter-V (hofstadter-M (- n 1)))))) (define (hofstadter-reeksen n) (do ((i 0 (+ i 1))) ((= i n)) (display (hofstadter-V i)) (display " ") (display (hofstadter-M i)) (newline)))
> (hofstadter-reeksen 10)
1 0
1 0
2 1
2 2
3 2
3 3
4 4
5 4
5 5
6 6
Merk op dat we tussen twee getallen precies één spatie laten. Verder komt er ook een (newline) na elk rij.
4.6 Reeksen: Het getal van Euler
Onderstaande reeksontwikkeling heeft als som het getal van Euler, \(e = 2,718281828...\).
\[e = \frac{1}{0!} +\frac{1}{1!} +\frac{1}{2!} +\frac{1}{3!} + ...\]
We kunnen in Scheme een procedure (calc-e n) definiëren die het getal \(e\) benadert door de som van de eerste \(n + 1\) termen van de reeks te berekenen:
(define (factorial n) (if (zero? n) 1 (* n (factorial (- n 1))))) (define (calc-e n) (if (= n 0) 1 (+ (/ 1 (factorial n)) (calc-e (- n 1)))))
Hierbij geeft (factorial n) het resultaat \(n!\), waarbij precies n vermenigvuldigingen worden gedaan (zie Abelson&Sussman blz. 32). Hoeveel vermenigvuldigingen neemt (calc-e n) dan in beslag? Verander de definitie van calc-e zodat je zo min mogelijk vermenigvuldigingen doet.
Hint: Verweef de definities van calc-e en factorial met elkaar en maak gebruik van een iteratief proces.
(define (calc-e n) (define (iter ctr res fac-prev) (define new-fac (* ctr fac-prev)) (if (> ctr n) res (iter (+ ctr 1) (+ res (/ 1 new-fac)) new-fac))) (iter 1 1 1))
> (exact->inexact (calc-e 10)) 2.7182818011463845
4.7 Reeksen: Het getal van Euler d.m.v. do
Onderstaande reeksontwikkeling heeft als som het getal van Euler, \(e = 2,718281828...\).
\[e = \frac{1}{0!} +\frac{1}{1!} +\frac{1}{2!} +\frac{1}{3!} + ...\]
We kunnen in Scheme een procedure (calc-e n) definiëren die het getal \(e\) benadert door de som van de eerste \(n + 1\) termen van de reeks te berekenen:
(define (factorial n) (if (zero? n) 1 (* n (factorial (- n 1))))) (define (calc-e n) (if (= n 0) 1 (+ (/ 1 (factorial n)) (calc-e (- n 1)))))
Verander de definitie van calc-e door de definities van calc-e en factorial met elkaar te verweven. Maak deze keer gebruik van een do-lus, zodat jouw calc-e-procedure een iteratief proces genereert.
(define (calc-e n) (do ((ctr 1 (+ ctr 1)) (res 1 (+ res (/ 1 (* ctr fac-prev)))) (fac-prev 1 (* ctr fac-prev))) ((> ctr n) res)))
> (exact->inexact (calc-e 10)) 2.7182818011463845
4.8 Recursiediepte: "weird"
De (wiskundige) functie weird is als volgt gedefinieerd:
\[weird(x) = \left\lbrace\begin{array}{ll} 1 & \mbox{als } x=1 \\ weird (x/2) & \mbox{als x even is}\\ weird (3*x+1) & \mbox{anders}\end{array}\right.\]
4.8.1 Recursiediepte: Implementeer de procedure "weird"
Schrijf de procedure (weird x) die de wiskundige functie van eerder implementeert. Genereert je oplossing een recursief of iteratief proces?
(define (weird x) (cond ((= x 1) 1) ((even? x) (weird (/ x 2))) (else (weird (+ (* 3 x) 1)))))
> (weird 15) 1
4.8.2 Recursiediepte: Bereken de recursiediepte van "weird"
Schrijf de procedure (depth-weird x) die het aantal recursieve oproepen (= de recursie-diepte) van weird voor een bepaalde x teruggeeft.
(define (depth-weird x) (cond ((= x 1) 0) ((even? x) (+ 1 (depth-weird (/ x 2)))) (else (+ (depth-weird (+ (* 3 x) 1)) 1))))
> (depth-weird 15) 17
4.9 Terugkeerpunten
Geef de output van de uitdrukking (count1 4) en (count2 4) indien count1 en count2 als volgt gedefinieerd zijn:
(define (count1 x) (cond ((= 0 x) (display x)) (else (display x) (count1 (- x 1))))) (define (count2 x) (cond ((= 0 x) (display x)) (else (count2 (- x 1)) (display x))))
> (count1 4) 43210
> (count2 4) 01234
4.10 Terugkeerpunten: Binaire vormen
Schrijf een procedure (display-as-binary n), die een positief geheel getal n neemt, en dit in binaire vorm afdrukt.
De meest rechtse bit is 1 als het getal oneven is, 0 als het getal even is.
Voor de tweede bit van rechts deel je het getal door 2 (met de functie (quotient n1 n2) die het geheel equivalent is van (/ n1 n2)), en je doet dezelfde test.
Voor de derde bit van rechts deel je het vorige quotiënt door 2
enz. ...
Je mag een recursief proces genereren. Gebruik (display "0") en (display "1") om de cijfers 0 en 1 af te drukken. Let op dat je het getal niet omgekeerd afdrukt. Enkele correcte voorbeelden zijn:
(define (display-as-binary n) (if (> n 1) (display-as-binary (quotient n 2))) (display (modulo n 2)))
> (display-as-binary 8) 1000
> (display-as-binary 5) 101
> (display-as-binary 0) 0
4.11 display-n met do
Schrijf een procedure (display-n x n) die twee parameters aanvaardt, een karakter en een positief geheel getal. Ze zal — gebruik makende van de standaard procedure display — het gegeven karakter zoveel maal afdrukken als de tweede parameter aangeeft. Maak gebruik van een do-lus om display-n te implementeren.
(define (display-n x n) (do ((i n (- i 1))) ((= i 0)) (display x)))
> (display-n "*" 4) ****
4.12 display-n: parasol met do
Schrijf een procedure (parasol n) (n is een geheel getal) die een parasolletje met gegeven hoogte op het scherm ’tekent’.
In het volgend voorbeeld heeft het driehoekje als hoogte 5 (de waarde van de parameter n) en als maximale breedte 9 (\( =(2 \times n) - 1\)). De hoogte van het stokje is altijd 3. Enkele sterretjes en spaties kan je op het scherm printen door gebruik te maken van respectievelijk (display "*") en (display " "). Gebruik uiteraard de display-n procedure als je meerdere sterretjes of spaties op het scherm moet printen. Om een nieuwe lijn te beginnen gebruik je (newline).
Implementeer de parasol-procedure op een iteratieve manier, door gebruik te maken van do-lussen.
(define (display-n x n) (do ((i n (- i 1))) ((= i 0)) (display x))) (define (parasol n) (do ((ctr 0 (+ ctr 1))) ((= ctr n)) (display-n " " (- n ctr 1)) (display-n "*" (+ (* ctr 2) 1)) (newline)) (do ((ctr 0 (+ ctr 1))) ((= ctr 3)) (display-n " " (- n 1)) (display "*") (newline)))
> (parasol 5)
*
***
*****
*******
*********
*
*
*
4.13 Extra Oefeningen
4.13.1 Multiply: Simulatie
Schrijf twee functies die door middel van simulatie berekenen hoeveel recursieve oproepen gebeuren in de procedures uit Multiply: Linear proces (Recursief & Iteratief) en Multiply: Logaritmisch proces (Recursief & Iteratief). Noem de functies (sim-multiply a b) en (sim-fast-multiply a b).
(define (sim-multiply a b) (if (zero? b) 1 (+ 1 (sim-multiply a (- b 1))))) (define (sim-fast-multiply a b) (cond ((zero? b) 1) ((even? b) (+ 1 (sim-fast-multiply (double a) (halve b)))) (else (+ 1 (sim-fast-multiply a (- b 1))))))
> (sim-multiply 14 2365) 2366
> (sim-fast-multiply 14 2365) 19
4.13.2 sinus
Onderstaande reeksontwikkeling berekent \(sin(x)\). \[sin(x)=\frac{x}{1!} - \frac{x^3}{3!} + \frac{x^5}{5!} - \frac{x^7}{7!} + ...\] Definieer een procedure (calc-sin x n), die de som van de eerste n termen berekent op een zo efficiënt mogelijke manier. Geef de formule die je het aantal vermenigvuldigingen oplevert voor n termen.
(define (calc-sin x n) (define (iter ctr acc fac xpow sign) (if (> ctr n) acc (let* ((i (- (* 2 ctr) 1)) (newfac (* fac (- i 1) i)) (newxpow (* xpow x x)) (newsign (- sign))) (iter (+ ctr 1) (+ acc (/ (* newsign newxpow) newfac)) newfac newxpow newsign)))) (iter 2 x 1 x 1))
> (calc-sin 0 10) 0
> (calc-sin (/ 3.1415 4) 10) 0.7070904020014415
> (calc-sin (/ 3.1415 2) 10) 0.9999999989269138
4.13.3 cosinus
Zelfde vraag voor de functie \(cos(x)\), met de procedure (calc-cos x n), die de volgende reeks-ontwikkeling heeft: \[cos(x)=\frac{x^0}{0!} - \frac{x^2}{2!} + \frac{x^4}{4!} - \frac{x^6}{6!} + ...\]
(define (calc-cos x n) (define (iter ctr acc fac xpow sign) (if (>= ctr n) acc (let* ((i (* 2 ctr)) (newfac (* fac (- i 1) i)) (newxpow (* xpow x x)) (newsign (- sign))) (iter (+ ctr 1) (+ acc (/ (* newsign newxpow) newfac)) newfac newxpow newsign)))) (iter 1 1 1 1 1))
> (calc-cos 0 10) 1
> (calc-cos (/ 3.1415 2) 10) 4.6326794876592664e-05
> (calc-cos 3.1415 10) -0.9999999992346591
4.13.4 Boog-sinus
Schrijf een functie die de reeksontwikkeling voor \(Bgsin(x)\) voor n termen berekent. \[bgsin(x) = x + \frac{1}{2.3}x^3 + \frac{1.3}{2.4.5}x^5 + \frac{1.3.5}{2.4.6.7}x^7+...\] (Opmerking: deze reeksontwikkeling is enkel geldig voor \(-\frac{\pi}{2} \leq bgsin(x) \leq \frac{\pi}{2}\))
Merk op dat de getallen die wegvallen in de noemer, de getallen zijn die in de teller staan. Zo is bijvoorbeeld de term \(\frac{1.3.5}{2.4.6.7}x^7\) gelijk aan \(\frac{1.1.3.3.5.5}{1.2.3.4.5.6.7}x^7\). Het is dit "trukje" dat we gebruiken in onze oplossing.
(define (bgsin x n) (define (iter i teller noemer macht som) (if (= i n) som (let* ((macht (* x x macht)) (2i+1 (+ (* 2 i) 1)) (2i+2 (+ (* 2 i) 2)) (2i+3 (+ (* 2 i) 3)) (teller (* teller 2i+1 2i+1)) (noemer (* noemer 2i+2 2i+3))) (iter (+ i 1) teller noemer macht (+ (* (/ teller noemer) macht) som))))) (iter 0 1 1 x x))
> (bgsin (sin 1) 50) 0.9999999999532735
4.13.5 Recursiediepte: Tabel
Schrijf een procedure (weird-table min max) die op het scherm een tabel afdrukt van de recursie-dieptes van weird voor alle getallen gelegen tussen min en max. Maak hiervoor gebruik van depth-weird uit een vorige oefening.
(define (depth-weird x) (cond ((= x 1) 0) ((even? x) (+ 1 (depth-weird (/ x 2)))) (else (+ (depth-weird (+ (* 3 x) 1)) 1))))
Onze eerste versie ziet er zo uit:
(define (weird-table min max) (define (hulp x) (cond ((< x max) (display x) (display " ") (display (depth-weird x)) (newline) (hulp (+ x 1))))) (hulp min))
(define (weird-table min max) (cond ((< min max) (display min) (display " ") (display (depth-weird min)) (newline) (weird-table (+ min 1) max))))
(define (weird-table min max) (cond ((< min max) (for-each display (list min " " (depth-weird min) "\n")) (weird-table (+ min 1) max))))
> (weird-table 1 10)
1 0
2 1
3 7
4 2
5 5
6 8
7 16
8 3
9 19
Merk op dat we tussen twee getallen precies één spatie laten. Verder komt er ook een (newline) na elk rij.
4.13.6 Examen Informatica 2eZit 1994
4.13.6.1 display-n
(define (display-n x n) (if (> n 0) (begin (display x) (display-n x (- n 1)))))
> (display-n '* 4) ****
4.13.6.2 squares
Schrijf een recursieve procedure squares die een positief geheel getal aanvaardt, en vier vierkanten (met als zijdelengte het gegeven getal) afdrukt, zodanig dat het geheel opnieuw een vierkant vormt. (Noot: je mag ervan uitgaan dat alle karakters even groot op het scherm worden afgedrukt.)
(define (squares n) (define (display-full-line) (display-n "*" (* n 2)) (newline)) (define (display-semi-semi-line) (display "*") (display-n " " (- n 2)) (display "*")) (define (displaysemi-line) (display-semi-semi-line) (display-semi-semi-line) (newline)) (define (semi-line-iter i) (if (< i (- n 2)) (begin (displaysemi-line) (semi-line-iter (+ i 1))))) (display-full-line) (semi-line-iter 0) (display-full-line) (semi-line-iter 0) (display-full-line))
> (squares 3)
******
* ** *
******
* ** *
******
> (squares 5)
**********
* ** *
* ** *
* ** *
**********
* ** *
* ** *
* ** *
**********
4.13.6.3 explain
Zeg voor elk van je oplossingen in (a) en (b) of ze een iteratief dan wel een recursief proces genereren. Argumenteer waarom.
4.13.7 Iteratie met een teller
4.13.7.1 power-close-to
Schrijf een procedure (power-close-to b n) die twee positieve integers b en n als argumenten heeft en de kleinste integer e teruggeeft waarvoor geldt dat \(b^e > n\). Doe dit door gebruik te maken van de Scheme-procedure expt.
> (expt 2 3) 8
> (* 2 2 2) 8
(define (power-close-to b n) (define (iter e) (if (> (expt b e) n) e (iter (+ e 1)))) (iter 0))
> (power-close-to 2 15) 4
> (power-close-to 2 16) 5
4.13.7.2 performantie
Wat is de performantie van deze procedure?
Het process dat beschreven wordt door de procedure iter wordt \(\frac{\log{n}}{\log{b}}\) keer uitgevoerd. Als we er van uitgaan dat (expt n e) in e stappend wordt uitgevoerd, dan is de performantie van onze expt-power-close-to \(O(\frac{\log{n}}{\log{b}}^2)\)
4.13.7.3 Efficiënter
(define (power-close-to++ b n) (define (iter e macht) (if (> macht n) e (iter (+ e 1) (* macht b)))) (iter 0 1))
> (power-close-to 2 1000) 10
> (power-close-to++ 2 1000) 10