Echte und endständige Rekursionen

Aus ProgrammingWiki

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

Inhaltsverzeichnis 1 Rekursionsarten 2 Vorüberlegung: Das Sprachelement let 3 Aufgaben 3.1 Quadratzahlen 3.2 Glücksrad 3.3 Turm von Hanoi 4 Zum Weiterarbeiten 4.1 Der zerbrochene Stab

Rekursionsarten

Echte Rekursion	Endständige Rekursion
Eine Prozedur heißt echt rekursiv, wenn das Ergebnis erst im rekursiven Aufstieg ermittelt wird. Dazu müssen alle aktuellen Wertbindungen vor jedem neuen rekursiven Aufruf gespeichert werden (Stapel / Stack), damit sie im rekursiven Aufstieg zur Verfügung stehen.	Eine Prozedur heißt endständig rekursiv, wenn das Ergebnis bereits nach dem rekursiven Abstieg feststeht. Häufig wird das aktuelle Ergebnis in einer zusätzlichen Akkumulatorvariablen mitgeführt. Die aufwändige Stapelverwaltung entfällt. Endständige Rekursionen bezeichnet man deshalb auch als Iterationen.
Beispiel: (trace-define fak-rek (lambda (n) (if (= n 0) 1 (* n (fak-rek (- n 1)))))) Trace-Modus: (fak-rek 5) ausführen	Beispiel: (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))) Trace-Modus: (fak-it 5) ausführen
Trichtermodell der internen Abläufe:	Trichtermodell der internen Abläufe:

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 trace-Prozedur übergeben. Die Deaktivierung erfolgt über untrace:

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

Wir haben bereits lokale Wertbindungen beim Entwickeln allgemeiner zufällige Kfz-Kennzeichen mit dem Sprachelement let genutzt. Bei der Auswertung zufälliger Ereignisse wird es auch hier sehr nützlich sein, z.B.:

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

(wuerfeln)

ausführen

Hinweis: Mit lokalen Wertbindungen lassen sich unerwünschte Seiteneffekte in der globalen Scheme-Umgebung vermeiden.

Aufgaben

(define sqr (lambda (x) (* x x)))

1. Quadratzahlen

   Eine Liste mit $n$ Quadratzahlen soll generiert werden.
   Geben Sie eine echt rekursive Lösung an.

   (define quadzahlen-rek (lambda (n) ...))

    

   Quelltext überprüfen:

   jetzt prüfen

   (quadzahlen-rek 10)

   ausführen

   Implementieren Sie nun die endständig rekursive Prozedur.

   (define quadzahlen-help (lambda (n ls) ...)) (define quadzahlen-it (lambda (n) ...))

    

   Quelltext überprüfen:

   jetzt prüfen

   (quadzahlen-it 10)

   ausführen

2. Glücksrad

   Bei den Prozeduren mit Zeichenketten und Listen haben Sie die Prozedur (random <max>) mit $0 \le z < max$ kennen gelernt. Simulieren Sie mit dieser Prozedur ein Glücksrad, das aus 3 blauen, 4 gelben und 5 roten Feldern besteht. Implementieren Sie dazu eine nullstellige Prozedur, die einem einmaligen Drehen dieses Glücksrades entspricht und die entsprechende Farbe als Symbol zurückgibt. (define gluecksrad (lambda () ...)) (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)))))   Quelltext überprüfen: jetzt prüfen (gluecksrad) ausführen

   Kommerzielles mehrfarbiges Glücksrad

   Um die Verteilung der Farben zu ermitteln, soll nun das Glücksrad mehrfach gedreht werden.
   Mit der nachfolgenden echt rekursiven Prozedur wird dieser Vorgang simuliert:

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

   (gluecksrad-drehen-rek 1000)

   ausführen

   Entwickeln Sie eine endständig rekursive Prozedur, die das Gleiche leistet.

   (define gluecksrad-drehen-it (lambda (n) ...))

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

    

   Quelltext überprüfen:

   jetzt prüfen

   (gluecksrad-drehen-it 1000)

   ausführen

3. Turm von Hanoi

   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. 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. Wenn ihnen das gelungen sei, wäre das Ende der Welt gekommen.

   Turm von Hanoi

   Gegeben sei folgende Implementation:

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

   Hinweis: Testen Sie die Prozedur mit kleinen Argumenten!

   (hanoi 3)

   ausführen

   Beschreiben Sie die Spielstrategie (d.h. den 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?

   Turm von Hanoi mit 3 Scheiben

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.
Mit welcher Wahrscheinlichkeit lässt sich aus den Bruchstücken ein Dreieck legen?
Simulieren Sie diesen Vorgang in jeweils einer echtrekursiven bzw. endständig rekursiven Prozedur.

Zur Problemlösung.