Grundlagen der funktionsorientierten Programmierung mit SCHEME/Echte und endständige Rekursionen
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Scheme</language>
<code id="5641ae0d98f31" hidden>
;-- M. Hielscher / Chr. Wagenknecht --
(define random-maker
(let* ((multiplier 48271)
(modulus 21474836)
(apply-congruence
(lambda (current-seed)
(let ((candidate (modulo (* current-seed multiplier) modulus)))
(if (zero? candidate)
modulus
candidate))))
(coerce
(lambda (proposed-seed)
(if (integer? proposed-seed)
(- modulus (modulo proposed-seed modulus))
19860617))))
(lambda (initial-seed)
(let ((seed (coerce initial-seed)))
(lambda args
(cond ((null? args)
(set! seed (apply-congruence seed))
(/ (- modulus seed) modulus))
((null? (cdr args))
(let* ((proposed-top
(ceiling (abs (car args))))
(exact-top
(if (inexact? proposed-top)
(inexact->exact proposed-top)
proposed-top))
(top
(if (zero? exact-top)
1
exact-top)))
(set! seed (apply-congruence seed))
(inexact->exact (floor (* top (/ seed modulus))))))
((eq? (cadr args) 'reset)
(set! seed (coerce (car args))))
(else
(display "random: unrecognized message")
(newline))))))))
(require-library 'sisc/libs/srfi/srfi-19)
(import srfi-19)
(define random (random-maker (time-nanosecond (current-time))))
(define sortieren
(lambda (ls)
(letrec
([streichen
(lambda (el ls)
(cond
[(null? ls) ls]
[(equal? el (car ls)) (cdr ls)]
[else
(cons (car ls) (streichen el (cdr ls)))]))]
[sort
(lambda (ls)
(if (null? ls)
ls
(let ([z (apply min ls)])
(cons z (sort (streichen z ls))))))])
(sort ls))))
(define eps 0.1)
</code>
== Rekursionsarten ==
<table border="1" cellspacing="1" cellpadding="4">
<tr>
<th width="500">Echte Rekursion</th>
<th width="500">Endständige Rekursion</th>
</tr>
<tr>
<td valign="top">
Eine Prozedur heißt ''echt rekursiv'', wenn das Ergebnis erst im ''rekursiven Aufstieg'' ermittelt wird.<br />
Dazu müssen alle aktuellen Wertbindungen vor jedem neuen rekursiven Aufruf gespeichert werden (Stapel / Stack),
damit sie im rekursiven Aufstieg zur Verfügung stehen.
</td>
<td valign="top">
Eine Prozedur heißt ''endständig rekursiv'', wenn das Ergebnis bereits nach dem ''rekursiven Abstieg'' feststeht.<br />
Häufig wird das aktuelle Ergebnis in einer zusätzlichen Akkumulatorvariablen mitgeführt.
Die aufwändige Stapelverwaltung entfällt.<br />
Endständige Rekursionen bezeichnet man deshalb auch als ''Iterationen''.
</td>
</tr>
<tr>
<td valign="top">
<table border="0" cellspacing="0" cellpadding="0">
<tr><td>'''Beispiel:'''</td></tr>
<tr>
<td width="500" height="180" valign="top">
<code id="4c97d4c0a508c">
(define fak-rek
(lambda (n)
(if (= n 0)
1
(* n (fak-rek (- n 1))))))
</code>
</td>
</tr>
<tr><td>'''Trace-Modus:'''</td></tr>
<tr>
<td width="500" height="100" valign="top">
<code id="4c9e0cd390903" hidden>
(import debugging)
</code>
<run id="4c9e0cd390d96">
(trace 'fak-rek)
(fak-rek 5)
</run>
<code id="4ca253a986689" hidden>
(import debugging)
(define fak-rek
(lambda (n)
(if (= n 0)
1
(* n (fak-rek (- n 1))))))
(trace 'fak-rek) (untrace 'fak-rek)
</code>
</td>
</tr>
</table>
</td>
<td valign="top">
<table border="0" cellspacing="0" cellpadding="0">
<tr><td>'''Beispiel:'''</td></tr>
<tr>
<td width="500" height="180" valign="top">
<code id="4c97d4c0a51aa">
(define fak-help
(lambda (n fak)
(if (= n 0)
fak
(fak-help (- n 1) (* n fak)))))
(define fak-it
(lambda (n)
(fak-help n 1)))
</code>
</td>
</tr>
<tr><td>'''Trace-Modus:'''</td></tr>
<tr>
<td width="500" height="100" valign="top">
<code id="4c9e0cd390b7c" hidden>
(import debugging)
</code>
<run id="4c9e0cd390ebb">
(trace 'fak-it) (trace 'fak-help)
(fak-it 5)
</run>
<code id="4ca253a9867c1" hidden>
(import debugging)
(define fak-help
(lambda (n fak)
(if (= n 0)
fak
(fak-help (- n 1) (* n fak)))))
(define fak-it
(lambda (n)
(fak-help n 1)))
(trace 'fak-it) (trace 'fak-help)
(untrace 'fak-it) (untrace 'fak-help)
</code>
</td>
</tr>
</table>
</td>
<tr>
<td valign="top">
'''Trichtermodell der internen Abläufe:'''<br />
<center>[[Bild:Echte_Rekursion1.gif]]</center>
</td>
<td valign="top">
'''Trichtermodell der internen Abläufe:'''<br />
<center>[[Bild:Endständige_Rekursion1.gif]]</center>
</td>
</tr>
</table>
'''Beachte:''' Die mitunter effizientere endständige Rekursion darf zu keinen Zwängen bei der rekursiven Beschreibung von Problemlösungen führen!
== Aufgaben ==
<code id="4c9be4304018c" hidden>
(define sqr
(lambda (x)
(* x x)))
</code>
<ol>
<li>
=== Quadratzahlen ===
Eine Liste mit <math>n</math> Quadratzahlen soll generiert werden.<br />
Geben Sie eine echt rekursive Lösung an.
<code id="4c9be430402be">
(define quadzahlen-rek
(lambda (n)
...))
</code>
<check>(or (equal? (quadzahlen-rek 6) '(36 25 16 9 4 1)) (equal? (quadzahlen-rek 6) '(36 25 16 9 4 1 0)))</check>
<run id="4c9be4304065d">
(quadzahlen-rek 10)
</run>
Implementieren Sie nun eine endständig rekursive Prozedur.
<code id="4c9be430403ed">
(define quadzahlen-help
(lambda (n ls)
...))
(define quadzahlen-it
(lambda (n)
...))
</code>
<check>(or (equal? (quadzahlen-it 6) '(1 4 9 16 25 36)) (equal? (quadzahlen-it 6) '(0 1 4 9 16 25 36)))</check>
<run id="4c9be43040742">
(quadzahlen-it 10)
</run>
</li>
<li>
=== Glücksrad ===
<table border="0" cellspacing="0" cellpadding="0">
<tr valign="top">
<td>
Bei den [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/Komplexe Anwendungen: Prozeduren mit Zeichenketten und Listen|Prozeduren mit Zeichenketten und Listen]] haben Sie die Prozedur <tt>(random <max>)</tt> mit <math>0 \le z < max</math> kennen gelernt.<br />
Simulieren Sie mit dieser Prozedur ein Glücksrad, das aus 3 blauen, 4 gelben und 5 roten Feldern besteht.<br />
Implementieren Sie dazu eine nullstellige Prozedur, die einem einmaligen Drehen dieses Glücksrades entspricht und die entsprechende Farbe als Symbol zurückgibt.
<code id="56420f1b4ddba">
(define gluecksrad
(lambda ()
...))
</code>
<code id="5641ae0d990c1" hidden>
(define gluecksrad-test
(lambda (n)
(do ((i 1 (+ i 1))
(ls '(0 0 0)
(let ([farbe (gluecksrad)])
(cond
[(eqv? farbe 'blau) (list (+ 1 (car ls)) (cadr ls) (caddr ls))]
[(eqv? farbe 'gelb) (list (car ls) (+ 1 (cadr ls)) (caddr ls))]
[else
(list (car ls) (cadr ls) (+ 1 (caddr ls)))]))))
((> i n) ls))))
(define gluecksrad-korrekt?
(lambda (n)
(let ([ls (sortieren (gluecksrad-test n))])
(and (< (abs (- 1 (/ (car ls) n 3/12))) eps)
(< (abs (- 1 (/ (cadr ls) n 4/12))) eps)
(< (abs (- 1 (/ (caddr ls) n 5/12))) eps)))))
</code>
<check>
(gluecksrad-korrekt? 1000)
</check>
<run id="5641ae0d99329" >
(gluecksrad)
</run>
</td>
<td>
[[Datei:Glücksrad1.jpg|miniatur||hochkant=0.8|Kommerzielles mehrfarbiges Glücksrad]]
</td>
</tr>
</table>
Um die Verteilung der Farben zu ermitteln, soll nun das Glücksrad mehrfach gedreht werden.<br />
Mit der nachfolgenden ''echt rekursiven Prozedur'' wird dieser Vorgang simuliert:
<code id="5641ae0d99150">
(define gluecksrad-drehen-rek
(lambda (n)
(if (= n 0)
(list 0 0 0)
(let ([farbe (gluecksrad)] [ls (gluecksrad-drehen-rek (- n 1))])
(cond
[(equal? farbe 'blau) (list (+ 1 (car ls)) (cadr ls) (caddr ls))]
[(equal? farbe 'gelb) (list (car ls) (+ 1 (cadr ls)) (caddr ls))]
[else
(list (car ls) (cadr ls) (+ 1 (caddr ls)))])))))
</code>
<run id="5641ae0d993ae">
(gluecksrad-drehen-rek 1000)
</run>
Entwickeln Sie nun eine ''endständig rekursive Prozedur'', die das Gleiche leistet.
<code id="5641ae0d991e2">
(define gluecksrad-drehen-it
(lambda (n)
...))
</code>
<code id="5641ae0d99273" hidden>
(define gluecksrad-it-korrekt?
(lambda (n)
(let ([ls (sortieren (gluecksrad-drehen-it n))])
(and (< (abs (- 1 (/ (car ls) n 3/12))) eps)
(< (abs (- 1 (/ (cadr ls) n 4/12))) eps)
(< (abs (- 1 (/ (caddr ls) n 5/12))) eps)))))
</code>
<check>
(gluecksrad-it-korrekt? 1000)
</check>
<run id="5641ae0d9942d">
(gluecksrad-drehen-it 1000)
</run>
</li>
<li>
=== Turm von Hanoi ===
<table border="0" cellspacing="0" cellpadding="0">
<tr>
<td valign="top">
Vermutlich stammt dieses Spiel von dem französischen Mathematiker '''Édouard Lucas''' (* 4. April 1842; † 3. Oktober 1891), bei dem ein Turm aus einzelnen Scheiben von <math>A</math> nach <math>B</math> unter Nutzung des Hilfsplatzes <math>H</math> umgesetzt werden soll. Dabei darf immer nur eine Scheibe bewegt werden. Außerdem darf nie eine größere Scheibe auf einer kleineren liegen.<br />
'''Lucas''' dachte sich dazu die Geschichte aus, dass indische Mönche im großen Tempel zu Benares, im Mittelpunkt der Welt, einen Turm aus 64 goldenen Scheiben versetzen müssten.<br />
Wenn ihnen das gelungen sei, wäre das Ende der Welt gekommen.
</td>
<td valign="top">
[[Bild:Tower_of_Hanoi.jpg|miniatur|hochkant=1.5|Turm von Hanoi]]
</td>
</tr>
</table>
Gegeben sei folgende Implementation:
<code id="5075ea5289eb8">
(define count 0)
(define verschiebe
(lambda (n start h ziel)
(if (> n 0)
(begin
(verschiebe (- n 1) start ziel h)
(set! count (+ count 1))
(display (string-append "Scheibe " (number->string n) ": " start " --> " ziel)) (newline)
(verschiebe (- n 1) h start ziel)))))
(define hanoi
(lambda (n)
(verschiebe n "A" "H" "B")
(display (string-append "--> " (number->string count) " Bewegung(en)")) (newline)
'ok))
</code>
'''Hinweis:''' Testen Sie die Prozedur mit kleinen Argumenten!
<run id="4c9be43040866">
(hanoi 3)
</run>
<table border="0" cellspacing="0" cellpadding="0">
<tr>
<td valign="top">
* Beschreiben Sie die Spielstrategie (d.h. den [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/Der Algorithmusbegriff|Lösungsalgorithmus]]) verbal.
* Entscheiden Sie, ob eine echt rekursive oder endständig rekursive Prozedur vorliegt.
* Ermitteln Sie, welcher Zusammenhang zwischen der Anzahl der Scheiben und der Anzahl der erforderlichen Bewegungen besteht.
* In wie vielen Jahren "droht" das Ende der Welt, wenn die indischen Mönche im Tempel zu Benares für die Bewegung jeder einzelnen Scheibe eine Sekunde benötigen würden?
</td>
<td>
[[Bild:Tower_of_Hanoi.gif|frame|Turm von Hanoi mit 3 Scheiben]]
</td>
</tr>
</table>
</li>
</ol>
== Zum Weiterarbeiten ==
=== Der zerbrochene Stab ===
Ein Stab mit der Länge von einem Meter fällt vom Tisch und zerbricht millimetergenau in höchstens drei Teile.<br />
Mit welcher Wahrscheinlichkeit lässt sich aus den Bruchstücken ein Dreieck legen?<br />
Simulieren Sie diesen Vorgang in jeweils einer echtrekursiven bzw. endständig rekursiven Prozedur.
Zur [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/Der zerbrochene Stab|Problemlösung]].