Echte und endständige Rekursionen

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: (define fak-rek (lambda (n) (if (= n 0) 1 (* n (fak-rek (- n 1)))))) Trace-Modus: <eval id="4c9e0cd390d96"> (trace 'fak-rek) (fak-rek 5) </eval>	Beispiel: (define fak-help (lambda (n fak) (if (= n 0) fak (fak-help (- n 1) (* n fak))))) (define fak-it (lambda (n) (fak-help n 1))) Trace-Modus: <eval id="4c9e0cd390ebb"> (trace 'fak-it) (trace 'fak-help) (fak-it 5) </eval>
Trichtermodell der internen Abläufe:	Trichtermodell der internen Abläufe:

Beachte: Die mitunter effizientere endständige Rekursion darf zu keinen Zwängen bei der rekursiven Beschreibung von Problemlösungen führen!

Aufgaben

1. Quadratzahlen

   Eine Liste mit n Quadratzahlen soll generiert werden.
   

   • Geben Sie eine echt rekursive Lösung an.
   (define quadzahlen-rek (lambda (n) ...))
   jetzt prüfen

   <eval id="4c9be4304065d"> (quadzahlen-rek 10) </eval>

   • Implementieren Sie nun eine endständig rekursive Prozedur.
   (define quadzahlen-help (lambda (n ls) ...)) (define quadzahlen-it (lambda (n) ...))
   jetzt prüfen

   <eval id="4c9be43040742"> (quadzahlen-it 10) </eval>

2. 

   Turm von Hanoi

   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 so bewegt werden, dass eine kleinere auf einer größeren Scheibe liegt.
   

   Gegeben Sei folgende Implementation:

   (define verschiebe (lambda (n start h ziel) (if (< n 1) 'ok (begin (verschiebe (- n 1) start ziel h) (display (string-append "Scheibe " (number->string n) ": " start " --> " ziel)) (newline) (verschiebe (- n 1) h start ziel))))) (define hanoi (lambda (n) (verschiebe n "A" "H" "B")))

   Hinweis: Testen Sie die Prozedur mit kleinen Argumenten!

   <eval id="4c9be43040866"> (hanoi 3) </eval>

   

   Turm von Hanoi mit 3 Scheiben
   • Beschreiben Sie die Spielstrategie (d.h. den Lösungsalgorithmus) verbal.
   • Entscheiden Sie, ob eine echt rekursive oder endständig rekursive Prozedur vorliegt.
   • Ermitteln Sie, wie viele Bewegungen notwendig sind, um einen Turm mit n Scheiben zu versetzen.