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.<br />
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="5075ea5289eb8">
(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)) (newline)
          (verschiebe (- n 1) h start ziel)))))

(define hanoi
  (lambda (n)    
    (verschiebe n "A" "H" "B")
    (display (string-append "--> " (number->string count) " Bewegung(en)")) (newline)
    'ok))
</code>

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

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

<table border="0" cellspacing="0" cellpadding="0">
<tr>
<td valign="top">
* 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, welcher Zusammenhang zwischen der Anzahl der Scheiben und der Anzahl der erforderlichen Bewegungen besteht.
* In wie vielen Jahre "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?
</td>
<td>
[[Bild:Tower_of_Hanoi.gif|frame|Turm von Hanoi mit 3 Scheiben]]
</td>
</tr>
</table>
</li>
</ol>

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

Zur [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/Der zerbrochene Stab|Problemlösung]].