Grundlagen der funktionsorientierten Programmierung mit SCHEME/Echte und endständige Rekursionen
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>SchemeJS</language>
<code id="5ba5013a88261" hidden>
;-- M. Hielscher / V.Berger --
(define indent 0)
(define-macro (trace-define name expr)
`(define ,name
(lambda input
(set! indent (+ indent 1))
(print (make-string indent #\space) (quote ,name) " " input)
(let* ([f ,expr] [r (apply f input)])
(print (make-string indent #\space) r)
(set! indent (- indent 1))
r))))
(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? (cdr 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="5ba5013a88342">
(trace-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">
<run id="5ba5013a88612">
(fak-rek 5)
</run>
</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="5ba5013a88427">
(trace-define fak-help
(lambda (n fak)
(if (= n 0)
fak
(fak-help (- n 1) (* n fak)))))
(trace-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">
<run id="5ba5013a88691">
(fak-it 5)
</run>
</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>
'''Hinweis:''' Für den Trace-Modus in ''DrRacket'' muss zunächst das entsprechende Modul eingebunden werden. Zur Aktivierung wird anschließend die zu untersuchende Prozedur der <tt>trace</tt>-Prozedur übergeben. Die Deaktivierung erfolgt über <tt>untrace</tt>:
(require racket/trace)
(trace fak)
(fak 6)
(untrace fak)
'''Beachte:''' Die mitunter effizientere endständige Rekursion darf zu keinen Zwängen bei der rekursiven Beschreibung von Problemlösungen führen!
== Vorüberlegung: Das Sprachelement <tt>let</tt> ==
Wir haben bereits lokale Wertbindungen beim Entwickeln [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/Das allgemeine zufällige Kfz-Kennzeichen|allgemeiner zufällige Kfz-Kennzeichen]] mit dem Sprachelement <tt>let</tt> genutzt. Bei der Auswertung zufälliger Ereignisse wird es auch hier sehr nützlich sein, z.B.:
<code id="5fb7b73e81ba5">
(define wuerfeln
(lambda ()
(let ([z (+ 1 (random 6))])
(cond
[(= z 1) "eins"]
[(= z 2) "zwei"]
[(= z 3) "drei"]
[(= z 4) "vier"]
[(= z 5) "fünf"]
[else
"sechs"]))))
</code>
<run id="5fb7b73e81c70">
(wuerfeln)
</run>
'''Hinweis:''' Mit lokalen Wertbindungen lassen sich unerwünschte Seiteneffekte in der globalen Scheme-Umgebung vermeiden.
== Aufgaben ==
<code id="4c9be4304018c" hidden>
(define sqr
(lambda (x)
(* x x)))
</code>
<ol>
<li>
=== Quadratzahlen ===
Eine Liste mit $n$ 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 die ''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 $0 \le z < max$ 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="5ba50a4e47efd" 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 eine ''endständig rekursive Prozedur'', die das Gleiche leistet.
<code id="5641ae0d991e2">
(define gluecksrad-drehen-it
(lambda (n)
...))
</code>
<code id="5ba50a4e47fb1" 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 $A$ nach $B$ unter Nutzung des Hilfsplatzes $H$ 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="5ba50a4e48049">
(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))
(verschiebe (- n 1) h start ziel)))))
(define hanoi
(lambda (n)
(verschiebe n "A" "H" "B")
(display (string-append "--> " (number->string count) " Bewegung(en)"))
'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]].