Lektion 16:

Rekursion

 Bisher haben wir von einer Funktion, der main-Funktion, eine andere Funktion aufgerufen. Es ist natürlich möglich, daß diese wiederum noch andere aufruft, diese ganz andere, soviel man mag. Es darf aber auch sein, daß eine Funktion sich selbst aufruft. Das erscheint zunächst nicht sinnvoll, aber manchmal ist es doch gut. Das übliche Beispiel hierfür ist die Fakultätsfunktion. Sie ist auf natürlichen Zahlen wie folgt definiert:

fact(0)==1
fact(1)==1
fact(2)==1*2
fact(3)==1*2*3
fact(4)==1*2*3*4
usw.

Und sie ist in Mathematikbüchern wie folgt definiert:

fact(n)==1, wenn n==0
fact(n)==n*fact(n-1) sonst

Und das läßt sich einfach so auch in C++ hinschreiben:

int fact(int n)
{
   if(n==0)
      return 1;
   else
      return n*fact(n-1);
};

  Viele Sachen, die sich rekursiv lösen lassen, lassen sich auch iterativ, also mit einer Schleife, lösen:

int fact(int n)
{
   int result=1;
   do
   {
      result=result*n;
      n=n-1;
   }while(n>0);
   return result;
};

Beim Programmieren begegnet man der Rekursion ziemlich oft. Will man z.B. die Länge einer Liste herausfinden, kann man schreiben:

Die Länge der leeren Liste ist 0. Die Länge einer anderen Liste ist eins mehr als die Länge der Liste ohne das erste Element.

Oder wenn man etwas mit der vollständigen Induktion beweisen will, dann ist schon wieder Rekursion im Spiel. Das liegt wohl an der rekursiven Definition der natürlichen Zahlen.

1 ist eine natürliche Zahl. Der Nachfolger einer natürlichen Zahl ist auch eine natürliche Zahl.

 Sehr viele Sachen lassen sich rekursiv definieren. Ein Elefant ist jemand, dessen beide Eltern Elefanten sind.

Manche dieser Definitionen sind nicht sachdienlich. Mit dieser Definition läßt sich leider nicht feststellen, ob jemand ein Elefant ist, wenn man nicht irgendwelche anderen Definitionen auch noch kennt.

Es würde schon reichen, wenn man die ersten beiden Elefanten kennen würde. Ohne diese Zusatzinformation könnte man immer nur die Ahnenreihe eines Elefanten hinaufgehen, ohne zu einem Ende zu kommen.

 Diese Zusatzinformation nennt man Abbruchbedingung.

Im Beispiel mit der Fakultät war die Abbruchbedingung fact(0)==1.

Rekursive Funktionen brauchen eine Abbruchbedingung.

Übung (schwierig):

 Die Fibonacci-Zahlen sind wie folgt definiert:

F(1)=1
F(2)=1
F(n)=F(n-1)+F(n-2)

Die ersten Fibonacci-Zahlen sind 1, 1, 2, 3, 5, 8, ...

Programmieren Sie diese Funktion rekursiv und iterativ.

Einsendungen:

Lösungsvorschlag (iterativ):
Wie initialisiere ich mehrere Variablen gleichzeitig?
Lösungsvorschlag (rekursiv):
Ist die iterative Version schneller?


Falls Ihnen Fehler im Text auffallen oder Sie Verbesserungsvorschläge haben, dann schicken Sie mir bitte eine Mail. Ich werde mich dann sofort darum kümmern.
[aktuelle Version] [inhalt] [index]      [Fehlerkorrektur, Verbesserungsvorschlag]

© Volkard Henkel <volkard@normannia.de>, last update: 08/25/00