Programmieren

Entwurf von endrekursiven Funktionen

 aufwärts

In der funktionalen Pro­grammierung werden Funktionen vielfach rekursiv definiert. Manchmal jedoch ist die rekursive Berechnung nicht effizient, wie etwa das Beispiel der Berechnung der Fibonacci-Zahlen zeigt. In derartigen Fällen lassen sich Funktionen auch auf bestimmte Weise endrekursiv (engl.: tail recursive) definieren; die Berechnung wird dann gleichsam iterativ durchgeführt.

In imperativen Programmier­sprachen wird für den Entwurf von Iterationen in Form von While-Schleifen das Konzept eines (seqentiellen) Iterations­schemas verwendet. Die Aufstellung eines ähnlichen Iterations­schemas ist auch für den Entwurf von end­rekursiven Funktionen geeignet, allerdings in Form eines parallelen Iterations­schemas. Im Folgenden wird dieses Konzept anhand von Beispielen in der funktionalen Programmier­sprache Haskell vorgestellt.

Darüber hinaus gibt es die Möglichkeit, in bestimmten Fällen durch formale Manipulationen eine Umwandlung von Rekursion in Endrekursion vorzunehmen.

Iterationsschema

Ein Iterations­schema ist eine Tabelle, die für jede Iteration die Werte der beteiligten Variablen enthält. Für jede Variable, die während der Iteration ihren Wert ändert, ist eine Tabellen­zeile vorgesehen.

Beispiel:  Ein mögliches Iterations­schema für die Berechnung von an ist das folgende:

i01234...n
p1aa·aa·a·aa·a·a·a...an

Die Variable i dient zum Zählen der Iterationen, die Variable p enthält das jeweilige Zwischen­ergebnis nach jeder Iteration. Für die Variable a ist keine Zeile im Iterations­schema vorgesehen, da sie ihren Wert im Verlauf der Berechnung nicht ändert. Das Ergebnis der Berechnung ist der Wert von p in der Spalte, in der i = n ist.

Iterationsgleichungen

Aus dem Iterations­schema werden Iterations­gleichungen abgeleitet. Für jede Variable des Iterations­schemas wird eine Iterations­gleichung aufgestellt. Diese gibt an, wie der Wert der Variablen in jeder Spalte des Schemas ab der zweiten Spalte zu berechnen ist. Die Werte in der ersten Spalte werden durch Initialisierung festgesetzt.

Beispiel:  Die Iterations­gleichungen für das obige Iterations­schema lauten

Hierbei bezeichnen Variablen "mit Strich" die Werte der ent­sprechenden Variablen in der vorherigen Spalte.

So ergibt sich der Wert von i in jeder Spalte als Wert von i in der vorherigen Spalte plus 1. Der Wert von p ergibt sich als Wert von p in der vorherigen Spalte mal a.

Die Iterations­gleichungen gelten in diesem Beispiel für alle Spalten des Iterations­schemas außer der ersten Spalte. Die Werte der ersten Spalte werden durch Initialisierung festgesetzt:

Sequentielles und paralleles Iterationsschema

Ein Iterations­schema, das sich für den Entwurf von While-Schleifen in der imperativen Pro­grammierung eignet, wird als sequentielles Iterations­schema bezeichnet. In einem sequentiellen Iterations­schema werden die Werte aller Variablen in einer Spalte sequentiell, also einer nach dem anderen von oben nach unten berechnet. Die sequentielle Berechnung hat zur Folge, dass sobald eine Variable v in der aktuellen Spalte einen neuen Wert erhalten hat, der alte Wert dieser Variablen, also deren Wert v' aus der vorherigen Spalte, nicht mehr zur Verfügung steht.

Definition:  Ein Iterations­schema wird als sequentielles Iterations­schema bezeichnet, wenn sich für jede darin auf­tretende Variable v eine Iterations­gleichung ableiten lässt, die auf der rechten Seite nur folgende Variablen enthält:

Im Gegensatz zum sequentiellen Iterations­schema steht das parallele Iterations­schema. In einem parallelen Iterations­schema werden die Werte der Variablen in einer Spalte parallel berechnet. Demzufolge stehen für die Berechnung dieser Werte aus­schließ­lich die Werte der Variablen aus der vorherigen Spalte zur Verfügung (dafür aber alle).

Definition:  Ein Iterations­schema wird als paralleles Iterations­schema bezeichnet, wenn sich daraus Iterations­gleichungen ableiten lassen, die für jede Variable v auf der rechten Seite nur folgende Variablen enthalten:

 

Anschaulich gesehen können für die Berechnung des Wertes einer Variablen an Position X im Iterations­schema alle Werte herangezogen werden, die im Iterations­schema an den Positionen x stehen (Bild 1: sequentielles Iterations­schema (a), paralleles Iterations­schema (b)).

   x 
   x 
  xX 
  x  
  x  
 
  x  
  x  
  xX 
  x  
  x  
(a) (b)
Bild 1: Zugriff auf Werte an Position x: sequentielles Iterationsschema (a), paralleles Iterationsschema (b).

Ein Iterations­schema kann gleichzeitig ein sequentielles und ein paralleles Iterations­schema sein, nämlich dann, wenn für die Berechnung des Wertes einer Variablen an Position X nur Werte herangezogen werden, die in der vorherigen Spalte auf gleicher Höhe oder unterhalb von Position X stehen, also an Positionen x aus dem Durchschnitt der Positionen x von Bild 1 a und 1 b.

Für die Entwicklung von iterativen Haskell-Funktionen verwenden wir das parallele Iterations­schema. Den Wert einer Variablen v aus der vorherigen Spalte bezeichnen wir mit v'. In den Iterations­gleichungen, die wir in den folgenden Beispielen entwickeln, dürfen auf der rechten Seite also nur Variablen "mit Strich" vorkommen (jedenfalls wenn es sich um Variablen des Iterations­schemas und nicht um sonstige Variablen handelt).

Anwendung

Das Iterations­schema zur Berechnung von an aus dem obigen Beispiel ist ein paralleles Iterations­schema, denn in den Iterations­gleichungen kommen auf der rechten Seite nur Variablen "mit Strich" vor, es werden also nur Werte aus der vorherigen Spalte verwendet:

i  =  i' + 1

p  =  p' · a

mit den Anfangs­werten

i = 0

p = 1

Das Iterations­schema lässt sich unmittelbar in folgendes Haskell-Programm überführen:

 

power a n = iterate 0 1
    where
    iterate i p | i==n      = p
                | otherwise = iterate (i+1) (p*a)

 

Die Funktion iterate bildet genau die Iterations­gleichungen nach. Der Aufruf von iterate zu Beginn enthält die Anfangswerte für i und p. Die Iteration endet, wenn der Spaltenindex i = n erreicht ist; dann wird als Ergebnis der Wert von p in dieser Spalte zurück­geliefert. Ansonsten ruft die Funktion iterate sich rekursiv selber auf, mit Parametern, die den rechten Seiten der Iterations­gleichungen entsprechen. Somit werden in den jeweiligen Aufrufen der Funktion iterate die Werte des Iterations­schemas von links nach rechts berechnet: iterate 0 1, iterate 1 a, iterate 2 a·a usw.

Weitere Beispiele

Das folgende Beispiel berechnet die Fakultäts­funktion.

Beispiel:  (Fakultäts­funktion n!)

In folgendem Iterations­schema ergibt sich das Ergebnis n! als Wert der Variablen p in der Spalte, in der i = n gilt.

i0123...
p11·11·1·21·1·2·3...

 

Die Iterations­gleichungen für i und p lauten:

 

Das Iterations­schema erfüllt die Bedingungen eines parallelen Iterations­schemas. Auf der rechten Seite der Iterations­gleichungen kommen nur Variablen "mit Strich" vor, es werden also nur Werte aus der vorherigen Spalte verwendet. Das Iterations­schema lässt sich unmittelbar in folgendes Haskell-Programm überführen:

 

fac' n = iterate 0 1
    where
    iterate i p | i==n      = p
                | otherwise = iterate (i+1) (p*(i+1))

 

Die Funktion iterate bildet genau die Iterations­gleichungen nach. Der Aufruf von iterate zu Beginn enthält die Anfangswerte für i und p. Die Iteration endet, wenn der Spaltenindex i = n erreicht ist; dann wird als Ergebnis der Wert von p in dieser Spalte zurück­geliefert. Ansonsten ruft sich die Funktion iterate rekursiv selber auf, mit Parametern, die den rechten Seiten der Iterations­gleichungen entsprechen. In den Aufrufen der Funktion iterate werden somit die Werte des Iterations­schemas von links nach rechts berechnet.

 

Beispiel:  (n-te Fibonacci-Zahl)

Die Folge der Fibonacci-Zahlen f  =  1, 1, 2, 3, 5, 8, 13, ... ist definiert durch die Rekursions­gleichungen

f0  =  1

f1  =  1

fn  =  fn-2 + fn-1

 

Es ist ein Leichtes, diese Rekursions­gleichungen in einer rekursiven Funktion zu implementieren. Es stellt sich jedoch heraus, dass für die Berechnung der n-ten Fibonacci-Zahl auf diese Weise mindestens fn Schritte erforderlich sind, also exponentiell viele. Bei iterativer Berechnung sind dagegen höchstens n Schritte erforderlich, also nur linear viele. Gesucht ist daher eine endrekursive Funktion, die diese iterative Berechnung nachbildet. Hierbei hilft wiederum die Aufstellung eines Iterations­schemas.

 

Ein Iterations­schema für die Berechnung der Fibonacci-Zahlen ist das folgende:

i0123456...
f11235813...
g0112358...

 

Die Iterations­gleichungen für i, f und g lauten:

 

Dies führt zu folgendem Haskell-Programm:

 

fib n = iterate 0 1 0
    where
    iterate i f g | i==n      = f
                  | otherwise = iterate (i+1) (f+g) f

 

Die Funktion iterate bildet die Iterations­gleichungen nach. Der Aufruf von iterate zu Beginn enthält die Anfangswerte für i, f und g. Die Iteration endet, wenn der Spaltenindex i = n erreicht ist; dann wird als Ergebnis der Wert von f in dieser Spalte zurück­geliefert. In den Aufrufen der Funktion iterate werden somit die Werte des Iterations­schemas von links nach rechts berechnet.

 

Beispiel:  (Binomial­koeffizienten)

Der Binomial­koeffizient n über k ist definiert als

Binomialkoeffizient Klammer auf nBinomialkoeffizient Klammer zu
 k
  =  
n!
k! · (n-k)!

Da der Bruch durch (n-k)! gekürzt werden kann, gilt

Binomialkoeffizient Klammer auf nBinomialkoeffizient Klammer zu
 k
  =  
n · ... · (n-k+1)
1 · ... · k

Als Beispiel ist etwa

Binomialkoeffizient Klammer auf49Binomialkoeffizient Klammer zu
6
  =  
49 · 48 · 47 · 46 · 45 · 44
1· 2 · 3 · 4 · 5 · 6
  =  13983816

 

Ein Iterations­schema für dieses Beispiel ist das folgende:

i494847464544 
j1234567
p1· 49/1· 48/2· 47/3· 46/4· 45/5· 44/6

 

Die Schreibweise beispiels­weise · 49/1 bedeutet, dass der Wert in der vorherigen Spalte dieser Zeile mit 49 multi­pliziert und dann durch 1 geteilt wird. Das Ergebnis n über k ergibt sich als der Wert von p in der Spalte, in der j = k+1 gilt.

 

Aus dem Iterations­schema lassen sich folgende Iterations­gleichungen ableiten:

 

Die Iterations­gleichungen lassen sich unmittelbar in ein ent­sprechendes iteratives Haskell-Programm umsetzen:

binom n k = iterate n 1 1
    where
    iterate i j p | j==k+1    = p
                  | otherwise = iterate (i-1) (j+1) (p*i `div` j)

Bemerkung:  Das Progamm lässt sich noch optimieren, indem j==k+1 durch j==min k (n-k) + 1 ersetzt wird , denn es gilt, dass binom n k gleich binom n (n-k) ist.

 

Beispiel:  (Sinus­funktion)

Ein etwas komplizierteres Beispiel ist die Berechnung der Sinus­funktion nach folgender Formel:

sin(x)  =   Summe n = 0, ..., unendlich  (-1)n
x2n+1
(2n+1)!

 

Das ent­sprechende Iterations­schema enthält Variablen für den Index i = 2n+1, für den jeweiligen Summanden s und das zugehörige Vorzeichen v sowie für die jeweilige Partialsumme p.

 

i1357...
v1-11-1...
sx1/1!x3/3!x5/5!x7/7!...
p0+ s'- s'+ s'...

 

Die Schreibweise + s' bedeutet, dass s' zum Wert in der vorherigen Spalte dieser Zeile addiert wird.

 

Die Iterations­gleichungen lauten:

 

Dies führt zu folgendem Haskell-Programm (die Funktion ist zur Unter­scheidung von der Standard­funktion sin mit sin' bezeichnet).

 

sin' x = iterate 1 1 x 0
    where
    iterate i v s p | s<1e-14   = p
                    | otherwise = iterate (i+2) (-v) (s*x^2/(i+1)/(i+2)) (p+v*s)

 

Die Berechnung wird abgebrochen, sobald der neu hinzu­kommende Summand s kleiner als 10-14 geworden ist.

 

Zusammenfassung

Die Abfolge der Schritte bei einer Iteration lässt sich mithilfe eines Iterations­schemas anschaulich darstellen. Aus diesem Iterations­schema lassen sich Iterations­gleichungen ableiten. Und diese Iterations­gleichungen schließlich lassen sich durch rein formale Manipulation in ein ent­sprechendes Programm überführen.

Der schwierigste dieser drei Schritte ist der erste, die Aufstellung des Iterations­schemas. Welche Variablen werden für Zwischen­ergebnisse gebraucht? In welcher Reihenfolge sind sie zu berechnen? Diese Überlegungen sind im Zusammenhang damit anzustellen, dass sich aus dem Iterations­schema geeignete Iterations­gleichungen ableiten lassen. Der letzte Schritt, die Überführung der Iterations­gleichungen in ein Programm, ist der einfachste, denn er ist gleichsam rein mechanisch durch­zuführen.

Aufgaben

Aufgabe 1:  (Berechnung von π/4)

Die Leibniz-Reihe konvergiert (allerdings sehr langsam) gegen den Grenzwert π/4:

π/4  =  1 – 1/3 + 1/5 – 1/7 + 1/9 – 1/11 + 1/13 – ...

Stellen Sie ein paralleles Iterations­schema für die Berechnung von π/4 auf. Leiten Sie daraus die zugehörigen Iterations­gleichungen und Initialisierungen ab und setzen Sie diese in ein iteratives Haskell-Programm um. Brechen Sie die Berechnung ab, wenn der neu hinzu­kommende Summand betragsmäßig kleiner als 10-4 ist.

 

Aufgabe 2:  (Berechnung von ln(2))

Eine schnell kon­vergierende Reihe zur Berechnung des natürlichen Logarithmus von 2 ist folgende:

ln(2)  =  
2
1 · 31
  +  
2
3 · 33
  +  
2
5 · 35
  +   ...

Entwerfen Sie ein paralleles Iterations­schema für die Berechnung. Leiten Sie daraus die Iterations­gleichungen und Initialisierungen ab. Programmieren Sie eine ent­sprechende iterative Haskell-Funktion zur Berechnung von ln(2).

 

 

 

up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   Datenschutz   ©  
Valid HTML 4.01 Transitional

Hochschule Flensburg
Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik