Grundlagen der funktionsorientierten Programmierung mit SCHEME/Rekursionen

Wiki-Quelltext dieser Seite.

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

(define pi (* 4 (atan 1)))
</code>

== Abgestützte Prozeduren ==

Wir wissen: Neue Objekte können mit bereits definierten Prozeduren beschrieben werden.<br />

'''Beispiel:''' Volumen eines geraden Kreiszylinders:

<table>
<tr>
<td width="300" align="center" valign="top">[[Bild:Zylinder1.gif]]</td>
<td width="1000" align="left">
<code id="4c9e601461861">
(define kreisflaeche
  (lambda (r)
    (* pi (sqr r))))

(define zylindervolumen
  (lambda (r h)
    (* (kreisflaeche r) h)))
</code>

<eval id="4c9e6014619b7">(zylindervolumen 5.5 12)</eval>
</td>
</tr>
</table>

Man sagt: Die Definition von <tt>zylindervolumen</tt> wird auf der Definition von <tt>kreisflaeche</tt> ''abgestützt''.<br />
Wie sinnvoll ist es, Prozeduren ''auf sich selbst'' abzustützen? 

== Selbstähnlichkeiten ==

Zunächst betrachten wir das nachfolgende Grafikobjekt, das wir als Binärbaum bezeichnen wollen.
Dabei fällt auf, dass jeder Ast wieder ein kleiner Binärbaum ist.<br />
Wir wollen diese ''Selbstähnlichkeit'' zu seiner Beschreibung ausnutzen:<br /> 

<table>
<tr>
<td width="380" align="center" valign="top">[[Bild:Binärbaum1.gif]]</td>
<td width="920" align="left">
<blockquote>
'''Beschreibung:'''
* Der einfachste Binärbaum besteht aus einem Stamm.
* Jeder andere Binärbaum besteht aus einem Stamm sowie einem vereinfachten linken und einem vereinfachten rechten Binärbaum.
</blockquote>
</td>
</tr>
</table>

Wir stellen fest, dass es durchaus sinnvoll sein kann, Objekte mit sich selbst zu beschreiben.<br />
Mit der Turtle-Grafik wollen wir eine gleichwertige Implementation vornehmen. Dazu definieren wir den Baum ''mit sich selbst''.

<table>
<tr>
<td width="380" align="center" valign="top">
<canvas w="380" h="400"></canvas>
</td>
<td width="920" align="left" valign="top">

<code id="4c9ef44680ea2">
(define baum
  (lambda (turtle len n)
    (if (> n 0)
        (begin
          (forward turtle len)
          (left turtle 45)
          (baum turtle (* 2/3 len) (- n 1))
          (right turtle 90)
          (baum turtle (* 2/3 len) (- n 1))
          (left turtle 45)
          (backward turtle len)))))

(define binarbaum
  (lambda (len n)
    (clear canvas)
    (move turtle 190 300)
    (baum turtle len n)))
</code>

<eval id="4c9ef4c9dad4c">
(binarbaum 100 6)
</eval>
</td>
</tr>
</table>

Prozeduren, die mit sich selbst definiert werden, heißen ''rekursive''<sup>1)</sup> ''Prozeduren''.<br />
Rekursionen stellen ein ''leistungsstarkes und universelles Konzept'' zur Problemlösung dar.<br />

<sup>1)</sup> recurrere (lat.): "zurücklaufen"

== Rekursive Fakultätsfunktion ==

Nun analysieren wir die mathematische Definition der Fakultätsfunktion:

<blockquote>
<table>
<tr>
<td width="200" align="center">
<math>n!=\prod^n_{i=1}i=1 \cdot 2 \cdot 3 \cdot ... \cdot n</math>
</td>
<td width="100" align="center">bzw. rekursiv:</td>
<td width="200" align="center">
<math>n!=\begin{cases}1,\mbox{wenn}\hspace{0.3em}n=0\\n \cdot (n-1)!\end{cases}</math>
</td>
</tr>
</table>
</blockquote>

Auch hier ist die Definition mit sich selbst offensichtlich.

'''Beschreibung:'''
* Die Fakultät einer Zahl ist 1, wenn die Zahl 0 ist,
* anderenfalls berechnet sie sich aus dem Produkt dieser Zahl mit der Fakultät ihres Vorgängers.

'''Implementation:'''

<table>
<tr>
<td width="300" align="center" valign="top">[[Bild:Fakultät1.gif]]</td>
<td width="1000" align="left">
<code id="4c8e9ce4be4fd">
(define fak
  (lambda (n)
    (if (= n 0)
        1
        (* n (fak (- n 1))))))
</code>

<eval id="4c8e9ce4be630">(fak 4)</eval>
</td>
</tr>
</table>

'''Beachte:''' Rekursive Prozeduren enthalten neben dem rekursiven Prozeduraufruf immer eine ''Elementarbedingung''! 

== Das Affenmodell ==

Eine schöne Interpretation des rekursiven Prozeduraufrufes finden wir bei W<small>AGENKNECHT</small> in [[Grundlagen der funktionsorientierten Programmierung mit SCHEME|[8], S. 42]]:

<blockquote>
[[Bild:Affenmodell1.gif]]
</blockquote>
''"Der Auftrag, der von außen dem höchsten Oberaffen übergeben wurde, wird von diesem nicht vollständig bearbeitet, sondern in etwas abgeschwächter Form dem untergebenen Affen übergeben. Dieser verhält sich ebenso zu seinem Untergebenen. Der letzte Affe in dieser Hierarchie kann den ihm übergebenen Auftrag erfüllen und dem übergeordneten Affen übergeben. Jeder weitere Affe hat die Pflicht, das Resultat der Erledigung seines Auftrages seinem Auftraggeber zu übergeben. Schließlich kann der Ranghöchste sein Ergebnis abliefern.<br /> Parallelen zu Einrichtungen, Ämtern und Institutionen unserer Gesellschaft sind unbeabsichtigt oder rein zufällig."''

== Aufgaben ==

<code id="4c8f451c695c8" hidden>
(define test-summe
  (lambda (n)
    (if (= n 0)
        0
        (+ (test-summe (- n 1)) n))))

(define test-summe-von-bis
  (lambda (von bis)
    (if (= von bis)
        von
        (+ bis (test-summe-von-bis von (- bis 1))))))
</code>

<ol>
<li>
Ermitteln Sie die Summe einer beliebigen Anzahl natürlicher Zahlen:
<math>S=\sum^n_{i=0}i=1 + 2 + 3 + ... + n</math>.<br />	 
Im Gegensatz zu <b>C. F. Gauß</b> soll (noch) keine Summenformel benutzt werden!
* Beschreiben Sie die rekursive Definition einer Summenfunktion.
* Skizzieren Sie das entsprechende Trichtermodell.
* Implementieren Sie die Summenfunktion <tt>summe</tt> als rekursive Prozedur.
<code id="4c8f451c696f0">
(define summe
  (lambda (n)
    ...))
</code>

<check>
(and (= (summe 123) (test-summe 123)) (= (summe 1024) (test-summe 1024)))
</check>

<eval id="4c8f451c6982d">
(summe 100)
</eval>
</li>
<li>
Schreiben Sie nun eine Prozedur <tt>summe-von-bis</tt>, die die Summe ganzer Zahlen in einem abgeschlossenen Intervall bildet.<br />
Überprüfen Sie das Prozedurergebnis mit einer Hilfsprozedur, die eine "Summenformel ganzer Zahlen" nutzt (Herleitung!).
<code id="4c8f4925af99d">
(define summe-von-bis
  (lambda (von bis)
    ...))
</code>

<check>
(and (= (summe-von-bis -45 123) (test-summe-von-bis -45 123)) (= (summe-von-bis 566 1024) (test-summe-von-bis 566 1024)))
</check>

<eval id="4c8f4925afadf">
(summe-von-bis -99 100)
</eval>
</li>
</ol>

== Zum Weiterarbeiten ==

=== Fraktale ===

Mit selbstähnlichen Figuren bzw. Objekten beschäftigt sich heute ein ganzes Teilgebiet der Mathematik, die ''fraktale Geometrie''. Ihre Untersuchungsergebnisse reichen in die Funktions- und Berechnbarkeitstheorie hinein und haben einen wesentlichen Einfluss auf die ''Chaosforschung'' komplexer dynamischer Systeme.<br />
Klassische selbstähnliche oder fraktale Figuren sind das Sierpinski-Dreieck und die Koch-Schneeflocke:

<blockquote>[[Bild:Sierpinski_Koch1.GIF]]</blockquote>

Beschreiben Sie beide [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/Fraktale|Fraktale]] verbal und implementieren Sie diese mit der Turtle-Grafik.<br />

Zur [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/Fraktale|Problemlösung]].