Grundlagen der funktionsorientierten Programmierung mit SCHEME/Mehrfachrekursionen

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
<code id="4cb030a0e5cbc" hidden>
(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>

[[Bild:Fibonacci1.jpg|miniatur|Berechnung der "Kaninchenaufgabe" mit der Fibonacci-Folge]]

== Die Fibonaccizahlen ==

Einer der bedeutendsten Mathematiker des Mittelalters, '''Leonardo Fibonacci di Pisa''' (* um 1180; † 1241), beschrieb die Fortpflanzung von Kaninchen mit der Zahlenfolge:

<blockquote><math>1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...</math></blockquote>

'''Definition:'''
<blockquote>
<math>\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}</math>
</blockquote>

'''Beschreibung:'''

* Die ersten beiden Glieder der Zahlenfolge sind jeweils 1.
* Jedes weitere Glied ergibt sich aus der Summe seiner beiden Vorgänger.

'''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!

<eval id="4cb06a8320240">
(fibo 6)
</eval>

In dieser echt rekursiven Prozedur erfolgt der rekursive Aufruf zweimal.
Rekursionen, in denen der rekursive Aufruf mehrfach erfolgt, heißen ''Mehrfachrekursionen''.<br />
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.

'''Beachte:'''<br />
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="4cb072a35c415" hidden>
(import debugging) 
(define fibo
  (lambda (n)
    (cond
      [(= n 1) 1]
      [(= n 2) 1]
      [else
       (+ (fibo (- n 1)) (fibo (- n 2)))])))
</code>

<eval id="4cb072a35c71e">
(trace 'fibo)
(fibo 6)
</eval>

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 Fibonacci-Zahl und bestimmt dabei die Anzahl der Rekursionschritte.<br />
Beide Werte werden als Paar <tt>(<Ergebnis> . <Aufwand>)</tt> ausgegeben:

<code id="4cb072a35c578" hidden>
(import debugging) 
(define fibo
  (lambda (n)
    (cond
      [(= n 1) 1]
      [(= n 2) 1]
      [else
       (+ (fibo (- n 1)) (fibo (- n 2)))])))
(trace 'fibo) (untrace 'fibo)
</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 Wertbeindungen'' vorgenommen werden, lassen sich mit <tt>letrec</tt> ''lokale rekursive Datenstrukturen'' definieren.

<eval id="4cb0638bb0e11">
(fibo-aufwand 6)
</eval>

Eine Alternative könnte in diesem Fall die endständig rekursive Problemlösung (Iteration) darstellen.<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>

<eval id="4cb06be058580">(fibo-it 100)</eval>

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>
<eval id="4b0443d3b47ae">(laenge '(a b c d e f g h i j k l m n))</eval>

'''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>
<eval id="4b0443d3b5753">(superlaenge '(a b (c (d e) (f (g (h i)) j) k l) m n))</eval>

== Zählen eines Elements in einer unverschachtelten bzw. verschachtelten Listen ==

'''Elementanzahl in einer unverschachtelten Liste:'''
<code id="4b0443d3aab6c">
(define zaehlen
  (lambda (el ls)
    (cond
      [(null? ls) 0]
      [(eq? el (car ls)) (+ 1 (zaehlen el (cdr ls)))]
      [else
       (zaehlen el (cdr ls))])))
</code>
<eval id="4b0443d3b66f1">(zaehlen 'b '(a b s d b c d a b b))</eval>

'''Elementanzahl in einer verschachtelten Liste:'''
<code id="4b0443d3abb0b">
(define superzaehlen
  (lambda (el ls)
    (cond
      [(null? ls) 0]
      [(list? (car ls)) (+ (superzaehlen el (car ls))
                           (superzaehlen el (cdr ls)))]
      [(eq? el (car ls)) (+ 1 (superzaehlen el (cdr ls)))]
      [else
       (superzaehlen el (cdr ls))])))
</code>

<eval id="4b0443d3b768e">(superzaehlen 'b '(a (b (s (d b)) (c) d a b) b))</eval>

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

<eval id="4b0443d3b8631">(element? 'f '(a b c d e f g h i j))</eval>

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)) (not (superelement? 'z '(a (b (c (d)) e f g h) i j))))
</check>

<eval id="4b0443d3b95d1">(superelement? 'f '(a b (c (d e (f g)) h i) j))</eval>
</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>

<eval id="4b0443d3ba56e">
(streiche-erstes 'b '(a b c a b c a b c))
</eval>

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

<eval id="4b0443d3bb512">
(streiche-alle 'b '(a b c a b c a b c))
</eval>

Implementieren Sie nun die Prozedur <tt>superstreichen</tt> für die entsprechende Anwendung auf ''verschachtelte'' Listen.

<code id="4b0443d3b092d">
(define superstreichen
  (lambda (el ls)
    ...))
</code>

<check>
(listequal? (superstreichen 'b '(a b (c (a (b) c) a) (b) c)) '(a (c (a () c) a) () c))
</check>

<eval id="4b0443d3bc4b1">
(superstreichen 'b '(a b (c (a (b) c) a) (b) c))
</eval>
</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>  

<eval id="4b0443d3bd44f">
(glaetten '(a b (c (a (b) c) a) (b) c))
</eval>
</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]].