Mehrfachrekursionen

Aus ProgrammingWiki

< Grundlagen der funktionsorientierten Programmierung mit SCHEME

Archivierte Version vom 2010-10-10T16:33:17+00:00. Aktuelle Version

Inhaltsverzeichnis

1 Die Fibonaccizahlen
2 Länge einer unverschachtelten bzw. verschachtelten Listen
3 Zählen eines Elements in einer unverschachtelten bzw. verschachtelten Listen
4 Aufgaben
5 Zum Weiterarbeiten
- 5.1 Superminimum

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:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

Definition:

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

Beschreibung:

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

Implementation:

(define fibo
  (lambda (n)
    (cond
      [(= n 1) 1]
      [(= n 2) 1]
      [else
       (+ (fibo (- n 1)) (fibo (- n 2)))])))

Hinweis: Testen Sie diese Prozedur mit kleinen Argumenten!

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 Binärbaum, zu den Fraktalen sowie zum "Turm von Hanoi" sind ebenfalls Mehrfachrekursionen.

Beachte:
Mehrfachrekursive Prozeduren können dann sehr uneffizient werden, wenn gleiche Operationen mehrfach ausgeführt werden.
Wir testen dazu die Prozedur im Trace-Modus:

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

Die nachfolgende Abbildung verdeutlicht die Abarbeitung des Prozeduraufrufs (fibo 6) in einer Baumstruktur:

Die nachfolgende Prozedur berechnet die n-te Fibonacci-Zahl und bestimmt dabei die Anzahl der Rekursionschritte.
Beide Werte werden als Paar (<ergebnis> . <aufwand>)</aufwand></ergebnis> ausgegeben:

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

Hinweis: Während mit let lokale Wertbeindungen vorgenommen werden, lassen sich mit letrec 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.
Vervollständigen Sie die entsprechende Hilfsprozedur.

(define fibo-it
  (lambda (n)
    (fibo-help n 1 1)))

(define fibo-help
  (lambda (n f1 f2)
    ...))

Es wäre nun falsch anzunehmen, dass Mehrfachrekursionen aus Effizienzgründen vermieden werden müssen. Im Gegenteil!
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):

(define laenge
  (lambda (ls)
    (if (null? ls)
        0
        (+ 1 (laenge (cdr ls))))))

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

Länge einer verschachtelten Liste:

(define superlaenge
  (lambda (ls)
    (cond
      [(null? ls) 0]
      [(list? (car ls)) (+ (superlaenge (car ls)) (superlaenge (cdr ls)))]
      [else
        (+ 1 (superlaenge (cdr ls)))])))

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

(define zaehlen
  (lambda (el ls)
    (cond
      [(null? ls) 0]
      [(eq? el (car ls)) (+ 1 (zaehlen el (cdr ls)))]
      [else
       (zaehlen el (cdr ls))])))

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

Elementanzahl in einer verschachtelten Liste:

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

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

Hinweis: equal?, eqv? und eq? sind allgemeine Vergleichsprädikate einfacher und höherer Datenstrukturen.

Aufgaben

Elementprüfer
Schreiben Sie zur Wiederholung das Prädikat element?, das entscheidet, ob ein vorgegebenes Element in einer unverschachtelten Liste enthalten ist.
(define element? (lambda (el ls) ...))

<eval id="4b0443d3b8631">(element? 'f '(a b c d e f g h i j))</eval>
Implementieren Sie nun das Prädikat superelement?, das sich in analoger Weise auf verschachtelte Listen anwenden lässt.
(define superelement? (lambda (el ls) ...))

<eval id="4b0443d3b95d1">(superelement? 'f '(a b (c (d e (f g)) h i) j))</eval>
Streichen eines Elements
Schreiben Sie zunächst nochmals die Prozeduren streiche-erstes und streiche-alle, die ein vorgegebenes Element in einer unverschachtelten Liste beim ersten bzw. bei jedem Auftreten streichen.
(define streiche-erstes (lambda (el ls) ...))

<eval id="4b0443d3ba56e"> (streiche-erstes 'b '(a b c a b c a b c)) </eval>
(define streiche-alle (lambda (el ls) ...))

<eval id="4b0443d3bb512"> (streiche-alle 'b '(a b c a b c a b c)) </eval>
Implementieren Sie nun die Prozedur superstreichen für die entsprechende Anwendung auf verschachtelte Listen.
(define superstreichen (lambda (el ls) ...))

<eval id="4b0443d3bc4b1"> (superstreichen 'b '(a b (c (a (b) c) a) (b) c)) </eval>
"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.
Implementieren Sie die Prozedur glaetten.
(define glaetten (lambda (ls) ...))

<eval id="4b0443d3bd44f"> (glaetten '(a b (c (a (b) c) a) (b) c)) </eval>

Zum Weiterarbeiten

Superminimum

Implementieren Sie das "Superminimum" einer verschachtelten Liste. Entwickeln Sie weitere Prozeduren für verschachtelte Listen.

Zur Problemlösung.

Mehrfachrekursionen

Inhaltsverzeichnis

Die Fibonaccizahlen

Länge einer unverschachtelten bzw. verschachtelten Listen

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

Aufgaben

Elementprüfer

Streichen eines Elements

"Glätten" einer verschachtelten Liste

Zum Weiterarbeiten

Superminimum

Suche