Grundlagen der funktionsorientierten Programmierung mit SCHEME/Rekursionen

Wiki-Quelltext dieser Seite.

<language>SchemeJS</language>
<code id="5ba128dc3e93b" hidden>
(define sqr
  (lambda (x)
    (* x x)))

(define pi (* 4 (atan 1)))

(define eps 1e-03)

(define runden
  (lambda (x anzahl)
    (/ (round (* x (expt 10 anzahl))) (expt 10 anzahl))))

(define grenzwert
  (lambda (r)
    (* (/ 1 2) (+ (sqrt 5) 1) r)))

(define char-downcase
  (lambda (z)
    (let ([nr (char->integer z)]) 
      (if (and (> nr 64) (< nr 91))
          (integer->char (+ nr 32))
          z))))

(define char-upcase
  (lambda (z)
    (let ([nr (char->integer z)]) 
      (if (and (> nr 96) (< nr 123))
          (integer->char (- nr 32))
          z))))
</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>

<run id="4c9e6014619b7">(zylindervolumen 5.5 12)</run>
</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 ==

=== Der Binärbaum ===

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" valign="top">
<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''.<br />

'''Hinweis:''' [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/Turtle-Befehle|Hier]] finden Sie die [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/Turtle-Befehle|Sprachelemente der Turtle-Grafik]].

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

<code id="5ba128dc3ea12">
(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))
        'ok)))

(define binaerbaum
  (lambda (len n)
    (clear canvas1)
    (move turtle1 200 300)
    (baum turtle1 len n)))
</code>

<run id="576464ea08e09">
(binaerbaum 100 6)
</run>
</td>
</tr>
</table>

=== Die "Quadratschnecke" ===

'''Beschreibung:'''
* Die einfachste Quadratschnecke besteht aus einer Strecke.
* Jede andere Quadratschnecke besteht aus einer Strecke, einer Drehung um 90° sowie einer etwas verkürzten Quadratschnecke.

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

<code id="576464ea08d3c">
(define schnecke
  (lambda (turtle len)
    (if (> len 0)
        (begin
          (forward turtle len)
          (right turtle 90)
          (schnecke turtle (- len 2)))
        'ok)))  

(define quadschnecke
  (lambda (len)
    (clear canvas2)
    (move turtle2 90 290)
    (schnecke turtle2 len)))
</code>

<run id="576464ea08e90">
(quadschnecke 200)
</run>
</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">
$n!=\prod^n_{i=1}i=1 \cdot 2 \cdot 3 \cdot ... \cdot n$
</td>
<td width="100" align="center">bzw. rekursiv:</td>
<td width="200" align="center">
$n!=\begin{cases}1,\mbox{wenn}\hspace{0.3em}n=0\\n \cdot (n-1)!\end{cases}$
</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>

<run id="4c8e9ce4be630">(fak 4)</run>
</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#Literatur|[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>
=== Summe natürlicher Zahlen ===

Ermitteln Sie die Summe einer beliebigen Anzahl natürlicher Zahlen:
$S=\sum^n_{i=0}i=1 + 2 + 3 + ... + n$.<br />	 
Im Gegensatz zu <b>Carl Friedrich Gauß</b> (* 30. April 1777; † 23. Februar 1855; deutscher Mathematiker, Astronom und Physiker) 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>

<run id="4c8f451c6982d">
(summe 100)
</run>
</li>
<li>

=== Summe ganzer Zahlen ===

Schreiben Sie nun eine Prozedur <tt>summe-von-bis</tt>, die die Summe ganzer Zahlen in einem abgeschlossenen Intervall bildet.

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

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

Überprüfen Sie das Prozedurergebnis mit einer Hilfsprozedur, die eine ''Summenformel ganzer Zahlen'' nutzt (Herleitung!).

<code id="5071eae8c4186">
(define berechne-von-bis
  (lambda (von bis)
    ...))
</code>

<check>
(and (= (berechne-von-bis -88 1213) (test-summe-von-bis -88 1213)) (= (berechne-von-bis 566 1724) (test-summe-von-bis 566 1724)))
</check>

<run id="5071eae8c4259">
(berechne-von-bis -99 100)
</run>
</li>
<li>

=== Vokalzähler ===

In einer Zeichenkette sollen alle Vokale unabhängig von ihrer Groß- oder Kleinschreibung gezählt werden.<br />
Vervollständigen Sie die entsprechende Prozedur.

<code id="5071ce079de20">
(define vokalzaehler
  (lambda (zk)
    ...))
</code>

<check>
(and (= (vokalzaehler "Teeei") 4) (= (vokalzaehler "krk") 0) (= (vokalzaehler "PUMA") 2))
</check>

<run id="5071ce079dedb">
(vokalzaehler "Amadeus")
</run>
</li>
<li>
=== Teilzeichenketten ===

In Datenbanksystemen gehört die Suche nach Teilen einer Zeichenkette zur Standardfunktionalität.<br />
Implementieren Sie das Prädikat <tt>(substring? <zk1> <zk2>)</tt>, das entscheiden soll, ob die Zeichenkette <tt>zk1</tt> in der Zeichenkette <tt>zk2</tt> enthalten ist.

'''Hinweis:'''

Zum Vergleich von Zeichenketten wird der Vergleichsoperator <tt>equal?</tt> benötigt. Weitere Informationen zu [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/Vergleichsoperatoren|Vergleichsoperatoren]] findet man [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/Vergleichsoperatoren|hier]].

<code id="5071e9c40bd8b">
(define substring?
  (lambda (zk1 zk2)
    ...))
</code>  

<check>
(and (substring? "info" "informatik") 
     (substring? "form" "informatik") 
     (not (substring? "informatik" "form"))
     (not (substring? "info" "physik")))
</check>

<run id="508d8dfa693f8">
(substring? "form" "Informatik") 
</run>
</li>
<li>
=== Widerstandsnetzwerk ===

Zunächst besteht eine einfache elektrische Grundschaltung aus 2 gleichgroßen Widerständen. Durch Anhängen weiterer dieser Grundschaltungen entsteht daraus ein komplexes Widerstandsnetzwerk:

<p>[[Bild:Widerstandsnetzwerk1.GIF]]</p><br />

Entwickeln Sie eine Prozedur, die den Gesamtwiderstand zwischen den Anschlussklemmen $A$ und $B$ berechnet, wenn $n$ Grundschaltungen zu diesem Widerstandsnetzwerk zusammengesetzt wurden. 

<code id="508d8b73b3b2b">
(define widerstand
  (lambda (r n)
    ...))
</code>

<check>
(and (< (abs (- (widerstand 123 10) (grenzwert 123))) eps) (< (abs (- (widerstand 1100 20) (grenzwert 1100))) eps))
</check>

<run id="5ba128dc3eb06">
(widerstand 100 10)
</run>

'''ZA: Grenzwert des Gesamtwiderstandes'''

Zeigen Sie, dass mit <math>n \rightarrow \infty</math> für den Grenzwert des Gesamtwiderstandes dieses Widerstandsnetzwerkes  gilt:

<math>R_{Ges} = \frac{\sqrt{5}+1}{2} R</math>

Überprüfen Sie die obige Widerstandsberechnung mit der Berechnung dieses Grenzwertes:

<code id="508e4d9bd0c2d">
(define widerstand-grenzwert
  (lambda (r)
    ...))
</code>

<run id="508e4d9bd0d9d">
(widerstand-grenzwert 100)
</run>
</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]].