Grundlagen der funktionsorientierten Programmierung mit SCHEME/Echte und endständige Rekursionen

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
== Rekursionsarten ==

<table border="1" cellspacing="1" cellpadding="4">
<tr>
<th width="500">Echte Rekursion</th>
<th width="500">Endständige Rekursion</th>
</tr>
<tr>
<td valign="top">
Eine Prozedur heißt ''echt rekursiv'', wenn das Ergebnis erst im ''rekursiven Aufstieg'' ermittelt wird.<br />
Dazu müssen alle aktuellen Wertbindungen vor jedem neuen rekursiven Aufruf gespeichert werden (Stapel / Stack),
damit sie im rekursiven Aufstieg zur Verfügung stehen.
</td>
<td valign="top">
Eine Prozedur heißt ''endständig rekursiv'', wenn das Ergebnis bereits nach dem ''rekursiven Abstieg'' feststeht.<br />
Häufig wird das aktuelle Ergebnis in einer zusätzlichen Akkumulatorvariablen mitgeführt.
Die aufwändige Stapelverwaltung entfällt.<br />
Endständige Rekursionen bezeichnet man deshalb auch als ''Iterationen''.
</td>
</tr>
<tr>
<td valign="top">

<table border="0" cellspacing="0" cellpadding="0">
<tr><td>'''Beispiel:'''</td></tr>
<tr>
<td width="500" height="180" valign="top">
<code id="4c97d4c0a508c">
(define fak-rek
  (lambda (n)
    (if (= n 0)
        1
        (* n (fak-rek (- n 1))))))
</code>
</td>
</tr>
<tr><td>'''Trace-Modus:'''</td></tr>
<tr>
<td width="500" height="100" valign="top">
<code id="4c9e0cd390903" hidden>
(import debugging)
</code>
<run id="4c9e0cd390d96">
(trace 'fak-rek)
(fak-rek 5)
</run>
<code id="4ca253a986689" hidden>
(import debugging) 
(define fak-rek
  (lambda (n)
    (if (= n 0)
        1
        (* n (fak-rek (- n 1))))))
(trace 'fak-rek) (untrace 'fak-rek)
</code>
</td>
</tr>
</table>

</td>
<td valign="top">

<table border="0" cellspacing="0" cellpadding="0">
<tr><td>'''Beispiel:'''</td></tr>
<tr>
<td width="500" height="180" valign="top">
<code id="4c97d4c0a51aa">
(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)))
</code>
</td>
</tr>
<tr><td>'''Trace-Modus:'''</td></tr>
<tr>
<td width="500" height="100" valign="top">
<code id="4c9e0cd390b7c" hidden>
(import debugging)
</code>
<run id="4c9e0cd390ebb">
(trace 'fak-it) (trace 'fak-help) 
(fak-it 5)
</run>
<code id="4ca253a9867c1" hidden>
(import debugging) 
(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 'fak-it) (trace 'fak-help) 
(untrace 'fak-it) (untrace 'fak-help)
</code>
</td>
</tr>
</table>

</td>
<tr>
<td valign="top">
'''Trichtermodell der internen Abläufe:'''<br />
<center>[[Bild:Echte_Rekursion1.gif]]</center>
</td>
<td valign="top">
'''Trichtermodell der internen Abläufe:'''<br />
<center>[[Bild:Endständige_Rekursion1.gif]]</center>
</td>
</tr>
</table>

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

== Aufgaben ==

<code id="4c9be4304018c" hidden>
(define sqr
  (lambda (x)
    (* x x)))
</code>

<ol>
<li>
=== Quadratzahlen ===

Eine Liste mit <math>n</math> Quadratzahlen soll generiert werden.<br />
* Geben Sie eine echt rekursive Lösung an.

<code id="4c9be430402be">
(define quadzahlen-rek
  (lambda (n)
    ...))
</code>

<check>(or (equal? (quadzahlen-rek 6) '(36 25 16 9 4 1)) (equal? (quadzahlen-rek 6) '(36 25 16 9 4 1 0)))</check>

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

* Implementieren Sie nun eine endständig rekursive Prozedur.

<code id="4c9be430403ed">
(define quadzahlen-help
  (lambda (n ls)
    ...))

(define quadzahlen-it
  (lambda (n)
    ...))
</code>

<check>(or (equal? (quadzahlen-it 6) '(1 4 9 16 25 36)) (equal? (quadzahlen-it 6) '(0 1 4 9 16 25 36)))</check>

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

=== Turm von Hanoi ===

<table border="0" cellspacing="0" cellpadding="0">
<tr>
<td valign="top">
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 <math>A</math> nach <math>B</math> unter Nutzung des Hilfsplatzes <math>H</math> umgesetzt werden soll. Dabei darf immer nur eine Scheibe so bewegt werden, dass eine kleinere auf einer größeren Scheibe liegt.<br />

'''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.
</td>
<td valign="top">
[[Bild:Tower_of_Hanoi.jpg|miniatur|hochkant=1.5|Turm von Hanoi]]
</td>
</tr>
</table>
Gegeben Sei folgende Implementation:

<code id="4c9be43040512">
(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")))
</code>

'''Hinweis:''' Testen Sie die Prozedur mit kleinen Argumenten!

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

[[Bild:Tower_of_Hanoi.gif|frame|Turm von Hanoi mit 3 Scheiben]]

* Beschreiben Sie die Spielstrategie (d.h. den [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/Der Algorithmusbegriff|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 <math>n</math> Scheiben zu versetzen.
</li>
</ol>