Grundlagen der funktionsorientierten Programmierung mit SCHEME/Mehrfachrekursionen
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>SchemeJS</language>
<code id="5ba5f21090a96" 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 listequal?
(lambda (ls1 ls2)
(cond
[(and (null? ls1) (null? ls2)) #t]
[(or (null? ls1) (null? ls2)) #f]
[(and (list? (car ls1)) (list? (car ls1)))
(and (listequal? (car ls1) (car ls2)) (listequal? (cdr ls1) (cdr ls2)))]
[else
(and (equal? (car ls1) (car ls2)) (listequal? (cdr ls1) (cdr ls2)))])))
</code>
== Die Fibonaccizahlen ==
<table border="0">
<tr>
<td valign="top">
Einer der bedeutendsten Mathematiker des Mittelalters, '''Leonardo Fibonacci di Pisa''' (* um 1180; † 1241), beschrieb die Fortpflanzung von Kaninchen mit der Zahlenfolge:
<blockquote>$1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...$</blockquote>
'''Definition:'''
<blockquote>
$\mbox{fibo}(n)=\begin{cases}1,\mbox{wenn}\hspace{0.3em}n=1\\1,\mbox{wenn}\hspace{0.3em}n=2\\\mbox{fibo}(n-1)+\mbox{fibo}(n-2),\mbox{sonst}\end{cases}$
</blockquote>
'''Beschreibung:'''
* Die ersten beiden Glieder der Zahlenfolge sind jeweils $1$.
* Jedes weitere Glied ergibt sich aus der Summe seiner beiden Vorgänger.
<br/>
Das explizite Bildungsvorschrift wurde übrigens unabhängig voneinander von den französischen Mathematikern '''Abraham de Moivre''' (* 26. Mai 1667; † 27. November 1754) erst im Jahr 1718 und '''Jacques Philippe Marie Binet''' (* 2. Februar 1786; † 12. Mai 1856) sogar erst im Jahr 1843 entdeckt.
</td>
<td valign="top">
[[Bild:Fibonacci1.jpg|miniatur|Berechnung der "Kaninchenaufgabe" mit der Fibonacci-Folge]]
</td>
</tr>
</table>
'''Implementation:'''
<code id="4cb06a831ff3c">
(define fibo
(lambda (n)
(cond
[(= n 1) 1]
[(= n 2) 1]
[else
(+ (fibo (- n 1)) (fibo (- n 2)))])))
</code>
'''Hinweis:''' Testen Sie diese Prozedur mit kleinen Argumenten!
<run id="4cb06a8320240">
(fibo 6)
</run>
In dieser echt rekursiven Prozedur erfolgt der rekursive Aufruf zweimal.
Rekursionen, in denen der rekursive Aufruf mehrfach erfolgt, heißen ''Mehrfachrekursionen''.
Unsere Problemlösungen zum [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/Rekursionen|Binärbaum]], zu den [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/Fraktale|Fraktalen]] sowie zum [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/Echte und endständige Rekursionen|"Turm von Hanoi"]] sind ebenfalls Mehrfachrekursionen.
=== Aufwandsbetrachtungen ===
Mehrfachrekursive Prozeduren können dann sehr uneffizient werden, wenn ''gleiche'' Operationen mehrfach ausgeführt werden.<br />
Wir testen dazu die Prozedur im Trace-Modus:
<code id="5ba5f21090b79" hidden>
(trace-define fibo
(lambda (n)
(cond
[(= n 1) 1]
[(= n 2) 1]
[else
(+ (fibo (- n 1)) (fibo (- n 2)))])))
</code>
<run id="5ba5f21090d36">
(fibo 6)
</run>
Die nachfolgende Abbildung verdeutlicht die Abarbeitung des Prozeduraufrufs <tt>(fibo 6)</tt> in einer Baumstruktur:
<blockquote>[[Bild:FiboBaum1.GIF]]</blockquote>
Die nachfolgende Prozedur berechnet die n-te Fibonaccizahl und bestimmt dabei die Anzahl der Rekursionschritte. Beide Werte werden als Paar <tt>(<Ergebnis> . <Aufwand>)</tt> ausgegeben:
<code id="5ba5f21090c29" hidden>
(define fibo
(lambda (n)
(cond
[(= n 1) 1]
[(= n 2) 1]
[else
(+ (fibo (- n 1)) (fibo (- n 2)))])))
</code>
<code id="4cb0638bb0896">
(define fibo-aufwand
(lambda (n)
(letrec
([aufwand
(lambda (n count)
(cond
[(= n 1) (cons 1 (+ count 1))]
[(= n 2) (cons 1 (+ count 1))]
[else
(let ([f1 (aufwand (- n 1) count)] [f2 (aufwand (- n 2) count)])
(cons (+ (car f1) (car f2)) (+ (cdr f1) 1 (cdr f2))))]))])
(aufwand n 0))))
</code>
'''Hinweis:''' Während mit <tt>let</tt> ''lokale Wertbindungen'' vorgenommen werden, lassen sich mit <tt>letrec</tt> ''lokale rekursive Programmstrukturen'' definieren.
<run id="4cb0638bb0e11">
(fibo-aufwand 6)
</run>
=== Experimente ===
Wir wollen den Aufwand zur Bestimmung der n-ten Fibonaccizahl in einem Balkendiagramm visualisieren.
Dazu müssen die Zählergebnisse der Prozedur <tt>fibo-aufwand</tt> in einer Liste gesammelt werden:
<code id="50d63f490b3a4">
(define experiment
(lambda (n schrittweite)
(if (< n 1)
()
(append (experiment (- n schrittweite) schrittweite)
(list (cdr (fibo-aufwand n)))))))
</code>
<run id="5ba5f21090dda">
(experiment 15 1)
</run>
Diese Liste wird der Prozedur <tt>balkendiagramm</tt> mit folgender Syntax übergeben:
(balkendiagramm <ls>) ; <ls> ... Liste mit Zahlenwerten
'''Achtung!''' Beim Experimentieren ist etwas Geduld erforderlich!<br />
<canvas w="400" h="300"></canvas>
<code id="50d63f490b4bb" hidden>
(define rand 50)
(define maxbreite (- 400 (* 2 rand)))
(define maxhoehe (- 300 (* 2 rand)))
(define minmax
(lambda (ls)
(letrec
([extremsuche
(lambda (extrem ls op)
(cond
[(null? ls) extrem]
[(op extrem (car ls)) (extremsuche (car ls) (cdr ls) op)]
[else
(extremsuche extrem (cdr ls) op)]))])
(cons (extremsuche 0 ls >)
(extremsuche 0 ls <)))))
(define balken
(lambda (hoehe breite)
(forward turtle breite) (left turtle 90)
(forward turtle hoehe) (left turtle 90)
(forward turtle breite) (left turtle 90)
(forward turtle hoehe) (left turtle 90)
(forward turtle breite)))
(define balkendiagramm
(lambda (ls)
(let* ([breite (/ maxbreite (length ls))]
[extremwerte (minmax ls)]
[min (car extremwerte)] [max (cdr extremwerte)])
(letrec
([zeichnen
(lambda (min max ls)
(if (null? ls)
'ok
(begin
(balken (floor (* (/ (car ls) (- max min)) maxhoehe)) (floor breite))
(zeichnen min max (cdr ls)))))])
(clear canvas)
(hide turtle)
(move turtle rand (+ rand (* (/ max (- max min)) maxhoehe))) (right turtle 90)
(zeichnen min max ls)))))
</code>
<run id="5ba5f21090e6c">
(balkendiagramm (experiment 15 1))
</run>
=== Endständig rekursive Bestimmung der n-ten Fibonaccizahl ===
Um den erheblichen Mehraufwand zu vermeiden, könnte sich in diesem Fall eine endständig rekursive Problemlösung (Iteration) anbieten.<br />
Vervollständigen Sie die entsprechende Hilfsprozedur.
<code id="4cb06be0583c8">
(define fibo-it
(lambda (n)
(fibo-help n 1 1)))
(define fibo-help
(lambda (n f1 f2)
...))
</code>
<check>
(and (= (fibo-it 10) 55) (= (fibo-it 55) 139583862445))
</check>
<run id="4cb06be058580">(fibo-it 100)</run>
Es wäre nun falsch anzunehmen, dass Mehrfachrekursionen aus Effizienzgründen vermieden werden müssen. Im Gegenteil!<br />
Mehrfachrekursionen können auch eine ''universelle Lösungsstrategie'' spezieller Probleme darstellen.
== Länge einer unverschachtelten bzw. verschachtelten Listen ==
'''Länge einer unverschachtelten Liste (Anzahl aller Listenelemente):'''
<code id="4b0443d3a8c2b">
(define laenge
(lambda (ls)
(if (null? ls)
0
(+ 1 (laenge (cdr ls))))))
</code>
<run id="4b0443d3b47ae">(laenge '(a b c d e f g h i j k l m n))</run>
'''Länge einer verschachtelten Liste:'''
<code id="4b0443d3a9bcc">
(define superlaenge
(lambda (ls)
(cond
[(null? ls) 0]
[(list? (car ls)) (+ (superlaenge (car ls)) (superlaenge (cdr ls)))]
[else
(+ 1 (superlaenge (cdr ls)))])))
</code>
<run id="4b0443d3b5753">(superlaenge '(a b (c (d e) (f (g (h i)) j) k l) m n))</run>
== Zählen eines Elements in einer unverschachtelten bzw. verschachtelten Listen ==
'''Elementanzahl in einer unverschachtelten Liste:'''
<code id="50c61d66330a0">
(define zaehlen
(lambda (el ls)
(cond
[(null? ls) 0]
[(eqv? el (car ls)) (+ 1 (zaehlen el (cdr ls)))]
[else
(zaehlen el (cdr ls))])))
</code>
<run id="4b0443d3b66f1">(zaehlen 'b '(a b s d b c d a b b))</run>
'''Elementanzahl in einer verschachtelten Liste:'''
<code id="50c61d6633150">
(define superzaehlen
(lambda (el ls)
(cond
[(null? ls) 0]
[(list? (car ls)) (+ (superzaehlen el (car ls))
(superzaehlen el (cdr ls)))]
[(eqv? el (car ls)) (+ 1 (superzaehlen el (cdr ls)))]
[else
(superzaehlen el (cdr ls))])))
</code>
<run id="4b0443d3b768e">(superzaehlen 'b '(a (b (s (d b)) (c) d a b) b))</run>
'''Hinweis:''' <tt>equal?</tt>, <tt>eqv?</tt> und <tt>eq?</tt> sind allgemeine [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/Vergleichsoperatoren|Vergleichsprädikate]] einfacher und höherer Datenstrukturen.
== Aufgaben ==
<ol>
<li>
=== Elementprüfer ===
Schreiben Sie zur Wiederholung das Prädikat <tt>element?</tt>, das entscheidet, ob ein vorgegebenes Element in einer ''unverschachtelten'' Liste enthalten ist.
<code id="4b0443d3acaac">
(define element?
(lambda (el ls)
...))
</code>
<check>
(and (element? 4 '(1 2 3 4 5 6 7 8 9)) (not (element? 'z '(a b c d e f g h i j))))
</check>
<run id="4b0443d3b8631">(element? 'f '(a b c d e f g h i j))</run>
Implementieren Sie nun das Prädikat <tt>superelement?</tt>, das sich in analoger Weise auf
''verschachtelte'' Listen anwenden lässt.
<code id="4b0443d3ada4c">
(define superelement?
(lambda (el ls)
...))
</code>
<check>
(and (superelement? 4 '(1 2 (3 (4) 5 6 7 8) 9))
(superelement? 'j '(a b (c (d) e f g h) i j))
(not (superelement? 'z '(a (b (c (d)) e f g h) i j))))
</check>
<run id="4b0443d3b95d1">(superelement? 'f '(a b (c (d e (f g)) h i) j))</run>
</li>
<li>
=== Streichen eines Elements ===
Schreiben Sie zunächst nochmals die Prozeduren <tt>streiche-erstes</tt> und <tt>streiche-alle</tt>, die ein vorgegebenes Element in einer ''unverschachtelten'' Liste beim ersten bzw. bei jedem Auftreten streichen.
<code id="4b0443d3ae9ec">
(define streiche-erstes
(lambda (el ls)
...))
</code>
<check>
(listequal? (streiche-erstes 'b '(a b c a b c a b c)) '(a c a b c a b c))
</check>
<run id="4b0443d3ba56e">
(streiche-erstes 'b '(a b c a b c a b c))
</run>
<code id="4b0443d3af9da">
(define streiche-alle
(lambda (el ls)
...))
</code>
<check>
(listequal? (streiche-alle 'b '(a b c a b c a b c)) '(a c a c a c))
</check>
<run id="4b0443d3bb512">
(streiche-alle 'b '(a b c a b c a b c))
</run>
Implementieren Sie nun die Prozeduren <tt>superstreichen-erstes</tt> bzw. <tt>superstreichen-alle</tt> für die entsprechenden Anwendungen auf ''verschachtelte'' Listen.
<code id="567181a72e70f">
(define superstreichen-erstes
(lambda (el ls)
...))
</code>
<check>
(and
(listequal? (superstreichen-erstes 'b '()) '())
(listequal? (superstreichen-erstes 'b '(a (a (a (a) b) b) b)) '(a (a (a (a)) b) b))
(listequal? (superstreichen-erstes 'b '(a b b (c (a (b) c) a b) (b) c)) '(a b (c (a (b) c) a b) (b) c)))
</check>
<run id="567181a72e7f0">
(superstreichen-erstes 'b '(a b (c (a (b) c) a) (b) c))
</run>
<code id="567182f3006a8">
(define superstreichen-alle
(lambda (el ls)
...))
</code>
<check>
(and
(listequal? (superstreichen-alle 'b '()) '())
(listequal? (superstreichen-alle 'b '(a (a (a (a) b) b) b)) '(a (a (a (a)))))
(listequal? (superstreichen-alle 'b '(a b b (c (a (b) c) a b) (b) c)) '(a (c (a () c) a) () c)))
</check>
<run id="567182f300793">
(superstreichen-alle 'b '(a b (c (a (b) c) a) (b) c))
</run>
</li>
<li>
=== "Glätten" einer verschachtelten Liste ===
Manchmal ist ist es sinnvoll, eine verschachtelte Liste in eine unverschachtelte Liste umzuwandeln. Wir wollen diese Konvertierung als "Glätten" bezeichnen. Dabei muss natürlich jedes Element aus jeder beliebigen Verschachtelungstiefe übernommen werden.<br />
Implementieren Sie die Prozedur <tt>glaetten</tt>.
<code id="4b0443d3b18df">
(define glaetten
(lambda (ls)
...))
</code>
<check>
(listequal? (glaetten '(a b (c (a (b) c) a) (b) c)) '(a b c a b c a b c))
</check>
<run id="4b0443d3bd44f">
(glaetten '(a b (c (a (b) c) a) (b) c))
</run>
</li>
</ol>
== Zum Weiterarbeiten ==
=== Superminimum ===
Implementieren Sie das [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/Superminimum|"Superminimum"]] einer verschachtelten Liste.
Entwickeln Sie weitere Prozeduren für verschachtelte Listen.<br />
Zur [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/Superminimum|Problemlösung]].