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.

> (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.

> (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).

> (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))

> (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.

> (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.

> (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.

> (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.

> (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?

> (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.

> (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))))

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:

> (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.

> (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.

> (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).

> (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.

> (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!} + ...\]

> (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}\))

> (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.

> (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

Schrijf een recursieve 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.

> (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.)

> (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.

4.13.7.2 performantie

Wat is de performantie van deze procedure?

4.13.7.3 Efficiënter

Schrijf de procedure efficiënter door haar iteratief te schrijven en aan elke nieuwe stap de macht uit de vorige stap door te geven. Noem deze versie (power-close-to++ b n).

> (power-close-to 2 1000)

10

> (power-close-to++ 2 1000)

10