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 
            
            

                
« Aufgaben zu Rekursiven Funktionen
                
Blatt 6, Aufgabe 1 »
            

			



   
		

	 





Leave a Comment

You must be logged in to post a comment.