28 Nov 08 Rekursive Funktionen

Wie in der Übung versprochen ein Post über rekursive Funktionen.

Rekursive Funktionen sind Funktionen, die sich selbst aufrufen, und sind besonders in der funktionalen Programmierung das Mittel um Programme zu schreiben, da in der reinen funktionalen Programmierung keine Side Effects existieren.

Man kann generell rekursive Funktionen in zwei Klassen einteilen:

• terminierende rekursive Funktionen
• nicht-terminierende rekursive Funktionen

Wir wollen uns natürlich auf die terminierenden Funktionen beschränken, wobei es unmöglich ist vorab festzustellen, ob eine beliebige Funktion für alle Eingaben terminiert oder nicht (siehe Halte-Problem in der Theoretischen Informatik).

Deswegen möchte ich vorstellen, wie wir rekursive Funktionen schreiben können, die auch sicher terminieren und das machen, was wir wollen.

An sich ist es eine Art Schema F, aber trotzdem tut man sich am Anfang schwer damit, bis man richtig ‘reinkommt.

Das Schema F

Eine rekursive Funktion muss immer mindestens einen Parameter haben, der sich bei jeder Iteration einer Schranke (z.B. 0) weiter nähert und die Funktion terminiert genau dann, wenn diese Schranke getroffen wird, d.h. alle rekursiven Aufrufe übergeben einen kleineren Wert für diesen Parameter. Diesen Parameter will ich ab jetzt als Laufparameter oder Iterationsparameter bezeichnen.

Der kursiv geschriebene Teil ist besonders wichtig, denn daran erkennen wir sofort, ob eine rekursive Funktion sich daran hält und wir wissen auch, wie wir dies selbst bewerkstelligen können.

Beispiel:

int fib( int n ) {
  ensure( n >= 0 );

  if( n <= 1 ) {
    return n;
  else /* n >= 2 => n - 1, n - 2 >= 0 */
    return fib( n - 1 ) + fib( n - 2 );
}

Hier ist $$\text{n}$$ der Laufparameter und wie man sieht wird er bei jedem rekursiven Aufruf kleiner und nähert sich 0´ und bleibt auch immer $$ \ge 0 $$ (siehe Kommentar). Im Fall $$ n = 0 $$ wird die Rekursion beendet.
Bei einer Rekursion wird also die Ausführung auf Basisfälle zurückgeführt. Die Basisfälle der Fibonacci-Folge sind 0 und 1.
Frage: Wieso haben wir zwei Basisfälle?Antwort
Ich habe auch ensure verwendet um sicherzustellen, dass die Funktion nur mit gültigen Werten für n aufgerufen wird. Dadurch stelle ich sicher, dass sie immer terminiert.
Man kann hier schon unser Schema heraus folgern:
Schema F für Rekursionen
Besonders bei rekursive definierten Folgen in der Mathematik lässt sich diese Schema ganz von selbst anwenden´.
Als ein Beispiel können wir die Berechnung der folgenden Folge betrachten:
$$

a_n := \begin{cases}

0 & \text{ : } n=0  \\

a_{n-1} – 2n – 1& \text{ : } n \ge 1

\end{cases}

$$
Die Signatur der Funktion in FJava ist offensichtlich $$\text{int a( int n )}$$.

Als Laufparameter kommt nur $$\text{n}$$ in Frage, einen anderen Parameter gibt es ja nicht.

Der Basisfall ist mit $$n=0$$ klar und die Rekursion erfolgt dann analog zur Definition und der Laufparameter wird mit $$\text{n-1}$$ auch kleiner, “geht also gegen 0” 
Nun zum Code:
int a( int n ) {
  ensure( n >= 0 );
  if( n == 0 )
    return 0;
  else
    return a( n - 1 ) + 2*n - 1;
}

Frage: Was berechnet diese Folge/Funktion?Antwort
Rekursive Funktionen über Sequenzen
Ist der Laufparameter eine Sequenz, dann betrachten wir die Länge der Sequenz implizit als Laufparameter und müssen als Basisfall eine Sequenz der Länge $$n_0$$ benutzen. Meistens wählt man $$n_0 := 0$$ und prüft dann einfach, ob die Sequenz leer ist.

Manchmal weiß man aber, dass nur nicht-leere Sequenzen übergeben werden können oder Sequenzen einer Mindestlänge, dann müssen wir die Länge der Sequenz abfragen.
Beispiel:
<T> T last( Seq<T> seq ) {
  ensure( !isEmpty( seq ), "seq muss mindestens ein Element enthalten" );
  if( isEmpty(rest( seq )) ) // ist äquivalent zu: length( seq ) == 1
    return first(seq);

  return last(rest( seq ));
}

Man kann natürlich noch zusätzliche Basisfälle definieren – das kommt auf den Algorithmus an – aber man braucht mindestens einen Basisfall, damit die rekursive Funktion terminiert.´
Rückgabewerte im Basisfall
Oft ist der Basisfall eigentlich der Fall, in dem die Funktion nichts “tun” und der Wert des Ergebnisses vom Basisfall nicht beeinflusst werden soll.
Beispiele:
<T> int length( Seq<T> seq ) {
  if( isEmpty( seq ) )
    return 0;

  return 1 + length( rest( seq ) );
}

// gib jedes 2. Element zurück
// wir fangen an bei 0 zu zählen, wie bei Indizes üblich
<T> Seq<T> oddElements( Seq<T> seq ) {
  if( isEmpty( seq ) || isEmpty( rest( seq ) ) )
    return emptySeq();

  return concat( cons( first( rest( seq ) ) ), oddElements( rest( rest( seq ) ) ) );
}

/*
Testausgabe:
oddElements( cons( 0,1,2,3,4,5 ) )

[1, 3, 5]
*/

Was haben 0 und emptySeq() gemeinsam? Sie beeinflussen den Wert des Ergebnisses nicht.

Würden wir nicht addieren und konkatenieren, sondern im rekursiven Schritt multiplizieren, dann wäre unser Rückgabewert im Basisfall $$1$$.
Mathematische Begründung:

Alle Rückgabewerte im Basisfall waren neutrale Elemente ihrer jeweiligen Algebraischen Struktur über der Sorte und dem Operator, auf der im rekursiven Schritt operiert wurde.

In den Beispielen waren dies die Gruppen $$\left( \mathbb{Z}, + \right)$$ und $$\left( \mathrm{Seq}, \circ \right)$$.
Hieraus können wir auch noch eine Einsicht gewinnen:

Man kann keinen passenden Rückgabewert finden, der das Ergebnis nicht beeinflusst, wenn man zum Beispiel im rekursiven Schritt mit dem Rückgabewert addiert und multipliziert.
Rekursiv Denken
An sich sind wir jetzt mit allem technischen durch – das einzige, das noch fehlt, sind ein paar Anmerkungen, die einem helfen können, rekursive Funktionen zu erstellen. Dies folgt jetzt.
Rekursives Programmieren ist die Mutter aller Divide & Conquer-Strategien: man spaltet das Problem immer wieder in gleichartige Teilprobleme, mit deren Lösung man das ursprüngliche Problem lösen kann, auf, bis man ein “Basisproblem”´ erhält, das leicht zu lösen ist´.
Die meisten Rekursionen, die wir bisher programmiert haben, waren sehr “unbalanciert”:

Bei Sequenzen zum Beispiel teilen wir die Sequenz oft in das erste Element und den Rest auf und bearbeiten dann das Element direkt und lassen in der Rekursion die Funktion das Problem für den Rest der Sequenz lösen und setzen dann alles wieder zusammen – siehe length oder so gut wie alle Funktionen, die wir bisher geschrieben haben.
 
length( cons( "a","b","c","d" ) ) schematisch dargestellt
Wenn wir also rekursive Funktionen auf Sequenzen schreiben, müssen wir uns immer überlegen, wie wir mit der Lösung für ein Teilsequenz unserer Eingabesequenz und direktem Zugriff auf ein oder zwei Elemente, die Lösung des Problems für die ganze Sequenz finden.

Dies ist der Grundgedanke der meisten Aufgaben, die wir behandeln.
Hilfsfunktionen
Oft hilft es auch, zusätzliche Hilfsfunktionen zu definieren, die einem die Arbeit erleichtern oder erst möglich machen, wenn die Signatur der Funktion selber nämlich keine Rekursion zulässt.
Als Beispiel die Tower-Funktion´:
// berechnet n^(n^(...)) n-mal Potenzieren (wobei ^ für's Potenzieren steht - deswegen heißt sie Turmfunktion)
int tower( int n ) {
  ensure( n >= 0 );
  return _tower( n, n );
}

int _tower( int n, int k ) {
  ensure( k >= 0 );
  if( k == 0 )
    return 1;

  return pow( n, _tower( n, k - 1 ) );
}

int pow( int a, int n ) {
  ensure( n >= 0 );
  if( n == 0 )
    return 1;

  return a * pow( a, n - 1 );
}

Hier brauchen wir einige Hilfsfunktionen, wobei auffallen sollte, dass die eigentliche tower Funktion nur ein Stub (eng. für Stummel) ist und _tower die eigentliche Arbeit erledigt.
Also wenn man nicht wirklich weiter kommt:

Einfach schauen, ob man vielleicht Hilfsfunktionen geschickt benutzen kann.
Soweit zur Theorie – im nächsten Post habe ich ziemlich viele Aufgaben gesammelt, die man ohne weiteres lösen kann ´.
						
Tags: Divide-and-Conquer Strategien, FJava, rekursive Funktionen
			            

			
Filed in Zur Vorlesung with 0 Comments 

					
28 Nov 08 Aufgaben zu Rekursiven Funktionen
     

			
Hier noch einiges Übungsaufgaben, die jeder für sich lösen kannHinweis.
Operationen auf Sequenzen $$\mathrm{Seq} \langle T \rangle$$

Wiederhole generische Funktionen und Sequenzen auf dem Merkblatt zu FJava.
Schreibe die Funktionen <T> int length( Seq<T> seq ), <T> T last( Seq<T> seq ) ohne irgendwo nachzuschlagen.
Entwickle eine Funktion <T> Seq<T> reverse( Seq<T> seq ), die eine Sequenz umdreht – aus [1,2,3,4] würde [4,3,2,1] werden.
Entwickle eine Funktion <T> T _getNth( Seq<T> seq, int n ), die das n-te Element ($$n \ge 0$$) aus der Sequenz zurückgibt. Wir fangen an bei 0 zu zählen, also _getNth( [0,1,2,3,4], 3 ) = 3.
Entwickle eine Funktion <T> T getNth( Seq<T> seq, int n ), die das n-te Element aus der Sequenz zurückgibt. Ist $$n < 0$$, so gebe das $$-n$$-te Element vom Ende der Sequenz zurück, also getNth( [4,3,2,1], -2 ) = 2.
Schreibe eine Funktion <T> boolean isEqual( Seq<T> a, Seq<T> b ), die überprüft, ob alle Elemente in der Sequenz a gleich denen in b sind (in der gleichen Reihenfolge), also isEqual( [1,2,3], [1,2,3] ) = true, aber isEqual( [1,2,3], [3,2,1] ) = false und natürlich isEqual( [], [] ) = true und isEqual( [1,2], [1,2,3] ) = false.

Beachte hierbei, dass T auch String sein kann, also muss man vergleichen mit a.equals( b ) für a, b aus der Sorte T´.
Schreibe eine Funktion <T> boolean isPalindrome( Seq<T> a ), die überprüft, ob a ein Palindrom ist, d.h. a ist vorwärts und rückwärts gelesen gleich.
Schreibe eine Funktion <T> boolean inSeq( T element, Seq<T> seq ), die überprüft, ob element in der Sequenz seq vorkommt.

Beachte hierbei, dass T auch String sein kann, also muss man vergleichen mit a.equals( b ) für a, b aus der Sorte T.


Entwickle eine Funktion <T> int count( Seq<T> seq, T element ), die zurückgibt, wie oft element in der Sequenz seq vorkommt.

Beachte hierbei, dass T auch String sein kann, also muss man vergleichen mit a.equals( b ) für a, b aus der Sorte T.
Entwickle eine Funktion <T> int remove( Seq<T> seq, T element ), die alle Vorkommen von element aus seq löscht.

Sequenzen als Mengen
Mengen sind ein Spezialfall von Sequenzen, bei denen jedes Element höchstens einmal vorkommen darf und die Reihenfolge der Elemente egal ist (wenn man auf Gleichheit o.ä. prüfen will).

Schreibe eine Funktion <T> boolean isSet( Seq<T> seq ), die zurückgibt, ob seq eine Menge ist, also ob jedes Element höchstens einmal in seq vorkommt.
Schreibe eine Funktion <T> boolean inSet( T element, Seq<T> set ), die zurückgibt, ob element in set ist.´
Schreibe eine Funktion <T> Seq<T> insertIntoSet( Seq<T> set, T element ), die element zur Menge set hinzufügt. Wenn für set gilt: isSet( set ) = true, dann soll dies auf für den Rückgabewert von insertIntoSet gelten.
Schreibe analog eine Funktion removeFromSet.
Entwickle Funktionen union und intersect die analog Mengen vereinen und schneiden.
Entwickle eine Funktion <T> boolean isSubset( Seq<T> subSet, Seq<T> set ), die überprüft, ob $$ \mathbf{subSet} \subseteq  \mathbf{set} $$ gilt.
Entwickle eine Funktion <T> boolean isSetEqual( Seq<T> aSet, Seq<T> bSet ), die überprüft, ob die Mengen aSet und bSet gleich sind.

Wieso ist isSetEqual für Mengen weniger effizient als isEqual für Sequenzen?´
Entwickle eine Funktion <T> Seq<Seq<T>> powerSet( Seq<T> set ), welche die Potenzmenge der Menge set konstruiert. Für jedes Sequenz s aus dem Rückgabewert gilt also: isSet( s ) = true und isSubset( s, set ) = true.

Hinweis: Man entwickle zuerst eine Funktion <T> Seq<Seq<T>> setsWithoutOneElement( Seq<T> set ), welche alle Teilmengen von set zurückgibt, die ein Element weniger enthalten.´

Operationen auf Sequenzen von Sequenzen´

Entwickle eine Funktion <T> Seq<Seq<T>> expandFront( Seq<T> seq, Seq<T> choices ), die alle Sequenzen s zurückgibt, für die gilt: isEqual( rest( s ), seq ) = true und inSeq( first( s ), choices ) = true.´
Entwickle eine analoge Funktion <T> Seq<Seq<T>> expandBack( Seq<T> seq, Seq<T> choices ), für die obigen Bedingungen für reverse( s ) statt s gelten. Wie sehen dann Nachbedingungen für expandBack aus?´
Schreibe die Funktion <T> Seq<Seq<T>> expandAcyclicFront( Seq<T> seq, Seq<T> choices ), die nur Sequenzen s zurückgibt für die gilt: inSeq( first( s ), rest( s ) ) = false.
Schreibe analog zu expandBack, die Funktion expandAcyclicBack.
Entwickle eine Funktion <T> Seq<T> getNeighbors( Seq<Seq<T>> neighborSeq, T node ), die den Rest der Untersequenz zurückgibt, die als erstes Element node hat, oder die leere Sequenz, falls es keine solche Sequenz gibt, wobei jede Sequenz von neighborSeq ein anderes erstes Element besitzt, also wäre [[1,2],[1,2,3] keine gültige Sequenz.

Beispiel: getNeighbors( [[1,2,3], [2,1,4], [3,1]], 2 ) = [1, 4].

Reflexive, Transitive Hüllen
Die reflexive, transitive Hülle $$ \rightarrow ^{\star} $$ über einer Menge $$\mathbf{G}$$ und einer Relation $$ \rightarrow : \mathbf{G} \times \mathbf{G} \rightarrow \mathbf{G}, \left( a, b \right) \mapsto a \rightarrow b $$ (gelesen: “a zeigt zu b”) ist folgendermaßen definiert´:
$$ \\\\

\forall a, b \in \mathbf{G}:\\

\begin{array}{lcl}

a \rightarrow ^ 0 b & :\Leftrightarrow & \begin{cases}

true & \text{ : } a = b  \\

false & \text{ : } a \not = b
\end{cases} \\\\

a \rightarrow ^ 1 b & : \Leftrightarrow & a \rightarrow b \\\\

a \rightarrow ^{n+1} b & : \Leftrightarrow & \exists x \in \mathbf{G}: a \rightarrow ^{n} x \land x \rightarrow b\\

\\

\\

a \rightarrow ^ {\star} b & : \Leftrightarrow & \exists n \in \mathbb{N}: a \rightarrow ^ n b

\end{array}

$$
Wir können diese Konstruktion auch in FJava nachvollziehen, wenn wir die Relation in einer Adjanzentliste speichern, d.h. gilt:
$$

\mathbf{ G = \left \{ a, b, c, d, e \right \} }

$$

und

$$

\mathbf{

a \rightarrow b, a \rightarrow c, a \rightarrow d, b \rightarrow c, b \rightarrow d,

c \rightarrow a, d \rightarrow b, d \rightarrow  e }

$$

so speichern wir das als:

$$\mathbf{seq := \left[\left[a, b, c, d \right], \left[b, c, d \right], \left[c, a \right], \left[d, b, e \right], \left[ e \right] \right]}$$

Sprich: Jedes Element kommt genau einmal als erstes Element in einer Untersequenz vor und der Rest der jeweiligen Untersequenz gibt die Elemente an, auf die das erste Element “zeigt”.

Dann können wir aus $$\mathbf{seq}$$ sowohl $$\mathbf{G}$$, als auch $$\rightarrow$$ bestimmen, da diese durch die Adjazenzliste eindeutig festgelegt sind.
Außerdem können wir getNeighbors benutzen um aus solch einer Sequenz, alle Elemente zu finden, auf die ein bestimmes zeigt.

Im Folgenden sei mit neighborSeq immer die Adjazenzliste von $$ \rightarrow $$ bezeichnet.
In dem Beispiel von oben: getNeighbors( seq, “a” ) = [ “b”, “c”, “d” ].

Schreibe eine Funktion <T> Seq<Seq<T>> zeroHull( Seq<Seq<T>> neighborSeq ), die für die Relation, die durch die Adjazenzliste neighborSeq bestimmt ist, die Adjazenzliste aller Elemente bestimmt für $$ \rightarrow^0 $$.

Im Beispiel von oben wäre dies:

$$\mathbf{seq := \left[\left[a, a \right], \left[b, b \right], \left[c, c \right], \left[d, d\right], \left[ e, e \right] \right]}$$
Entwickle eine Funktion <T> Seq<T> squareHullForElement( Seq<Seq<T>> neighborSeq, T element ), die die Menge aller Elemente x enthält, die von element in zwei Schritten erreichbar sind, also: $$ \mathbf{ \exists y \in G: element \rightarrow y \rightarrow x }$$
Entwickle eine Funktion <T> Seq<Seq<T>> squareHull( Seq<Seq<T>> neighborSeq ), die $$ \rightarrow ^2 $$ von neighborSeq zurückgibt.
Entwickle eine Funktion <T> Seq<T> nthHull( Seq<Seq<T>> neighborSeq, int n ), die für $$ n \ge 0 $$ die n-te Hülle von $$\rightarrow$$ bestimmt, also $$ \rightarrow^n $$.

Hinweis:

Man schreibe zuerst eine Funktion <T> Seq<Seq<T>> concatenateRelation( Seq<Seq<T> neighborSeqN, Seq<Seq<T>> neighborSeq ), die zwei Relationen $$ \prec $$  und $$ \propto $$, die durch neighborSeqN bzw. neighborSeq beschrieben werden, auf $$ \mathbf{G}$$ hintereinanderausführt und die sich ergebende Relation $$ \sqsubset $$ als Adjanzenzliste zurückgibt, so dass für alle Teilsequenzen mit erstem Element e und restlichen Elementen x, gilt:

$$ \mathbf{ \exists y \in G: e \prec y \land y \propto x :\Leftrightarrow e \sqsubset x }$$.´
Schreibe eine Funktion <T> Seq<Seq<T>> transitiveHull( Seq<Seq<T>> neighborSeq ), die $$ \rightarrow ^{\star} $$ konstruiert. Die Funktion kann immer terminieren, da $$ \mathbf{G} $$ endlich ist.

						
Tags: Add new tag, Aufgaben, FJava, Mengen, Sequenzen, Transitive Hülle
			            

			
Filed in Aufgaben with 0 Comments