Mehrfachrekursionen

Aus ProgrammingWiki

< Grundlagen der funktionsorientierten Programmierung mit SCHEME

Archivierte Version vom 2013-12-10T22:48:11+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

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.

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.

Berechnung der "Kaninchenaufgabe" mit der Fibonacci-Folge

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!

(fibo 6)

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.

Aufwandsbetrachtungen

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

(trace 'fibo)
(fibo 6)

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

Die nachfolgende Prozedur berechnet die n-te Fibonaccizahl 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.

(fibo-aufwand 6)

Experimente

Wir wollen den Aufwand zur Bestimmung der n-ten Fibonaccizahl in einem Balkendiagramm visualisieren. Dazu müssen die Zählergebnisse der Prozedur fibo-aufwand in einer Liste gesammelt werden:

(define experiment
  (lambda (n schrittweite)
    (if (< n 1)
        ()
        (append (experiment (- n schrittweite) schrittweite)
                (list (cdr (fibo-aufwand n)))))))

(experiment 30 2)

Diese Liste wird der Prozedur balkendiagramm mit folgender Syntax übergeben:

(balkendiagramm <ls>) ; <ls> ... Liste mit Zahlenwerten</ls></ls>

Achtung! Beim Experimentieren ist etwas Geduld erforderlich!

(balkendiagramm (experiment 30 1))

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.
Vervollständigen Sie die entsprechende Hilfsprozedur.

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

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

(fibo-it 100)

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

(laenge '(a b c d e f g h i j k l m n))

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

(superlaenge '(a b (c (d e) (f (g (h i)) j) k l) m n))

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

Elementanzahl in einer unverschachtelten Liste:

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

(zaehlen 'b '(a b s d b c d a b b))

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)))]
      [(eqv? el (car ls)) (+ 1 (superzaehlen el (cdr ls)))]
      [else
       (superzaehlen el (cdr ls))])))

(superzaehlen 'b '(a (b (s (d b)) (c) d a b) b))

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) ...))
(element? 'f '(a b c d e f g h i j))
Implementieren Sie nun das Prädikat superelement?, das sich in analoger Weise auf verschachtelte Listen anwenden lässt.
(define superelement? (lambda (el ls) ...))
(superelement? 'f '(a b (c (d e (f g)) h i) j))
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) ...))
(streiche-erstes 'b '(a b c a b c a b c))
(define streiche-alle (lambda (el ls) ...))
(streiche-alle 'b '(a b c a b c a b c))
Implementieren Sie nun die Prozedur superstreichen für die entsprechende Anwendung auf verschachtelte Listen.
(define superstreichen (lambda (el ls) ...))
(superstreichen 'b '(a b (c (a (b) c) a) (b) c))
"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) ...))
(glaetten '(a b (c (a (b) c) a) (b) c))

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

Aufwandsbetrachtungen

Experimente

Endständig rekursive Bestimmung der n-ten Fibonaccizahl

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