Fakultätsfunktion

Volvicer

Hallo

In dem Kurs Volkards c++ Kurs wird in Kapitel 16 die Rekursion behandel.

Als Programm ist gegeben:

Die Fakultätsfunktion:

fact(0)==1
fact(1)==1
fact(2)==12
fact(3)==1*2*3
fact(4)==1*2*34

Und sie ist in Mathematikbüchern wie folgt definiert:
fact(n)==1, wenn n==0
fact(n)==n*fact(n-1) sonst

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

Diesen Code verstehe ich so :

z.B. 4 also 4 ist nicht 1 => 4*fact(4-1) da ruft er die Funktion mit dem wert 3 auf danach also 3*fact(3-1) dann wird die Funktion mit 2*fact(2-1) aufgerufen und danach 1*fact(1-1) und der wert 1 wird zurückgegeben.

Also ist das ergebiss doch 1 und nicht 1*2*3*4 oder? Die Variable wird doch ständig überschrieben? Sie gibt doch nichts zurück oder sehe ich das falsch?

Also es funktioniert habe das in ein Programm geschrieben aber wieso?

Vielen dank im vorraus

virtuell Realisticer

Morgen,

das funktioniert, weil die einzelnen Ergebnis auf dem Stack abgelegt werden.

n*fact(n-1)

mit n = 4;

4 * fact(3) =>
  3 * fact(2) =>
    2 * fact(1) =>
      1 * fact(0) =>
            1;
          <=
      1 * 1
       <=
    2 * 1
     <=
  3 * 2
   <=
4 * 6

Jedes Teilergebnis landet auf den Stack. Kehrt die Funktion zurueck, wird das
letzte Ergebnis vom Stack geholt und verechnet.

mfg
v R

Du hast dir das eigentlich schon richtig hergeleitet und es ist schön, dass das auch so funktioniert, wäre schade wenn nicht. Der Grund ist folgender, wenn du eine Funktion mit Rückgabewert aufruftst, dann wird dieser Wert an die Stelle zurück gegeben, an der die Funktion aufgerufen wurde, somit wird der Teil fact(n-1) durch den jeweiligen Rückgabewert ersetzt.
Als erstes wird die 1 zurück gegeben ==>21
dann die 2, 32
dann die 6, 4*6
und so weiter, bis er ganz oben angekommen ist, das ist das prinzip der rekursion, einmal nach ganz unten und wieder zurück

Volvicer

Vielen Dank für die Antwort:

eine Frage hätte ich da noch bei dem Code

int fibRek(int n)
{
   if(n==1)
      return 1;
   else if(n==2)
      return 1;
   else
      return fibRek(n-1)+fibRek(n-2);
};

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

Habe ich noch eine Frage:

Bis zur Zahl 4 kann ich das nachrechnen und komme auf das selbe Ergebniss da die Abbruchbedinungen stimmen aber bei 5 komme ich auf was anderes:

return fibRek(5-1)+fibRek(5-2); das sind doch dann : fibRek(4) + fibRek(3)da das weder 1 noch 2 ergibt um retrun 1 zu bekommen wird doch 7 ausgegeben.

Ist es gewollt das diese Funktion solange läuft bis eine der beiden funktionen auf 2 steht um return 1 zu erhalten?

Vielen dank im Vorraus.

Bashar

Volvicer schrieb:

Bis zur Zahl 4 kann ich das nachrechnen und komme auf das selbe Ergebniss da die Abbruchbedinungen stimmen aber bei 5 komme ich auf was anderes:

return fibRek(5-1)+fibRek(5-2); das sind doch dann : fibRek(4) + fibRek(3)da das weder 1 noch 2 ergibt um retrun 1 zu bekommen wird doch 7 ausgegeben.

Versteh ich nicht. fibRek(4) ergibt 3 (du hast gerade gesagt, du hättest es nachgerechnet und es stimmt mit dem Ergebnis des Programms überein), fibRek(3) ergibt 2 (hast du auch nachgerechnet), was soll denn die Summe anderes sein als 5?

Ist es gewollt das diese Funktion solange läuft bis eine der beiden funktionen auf 2 steht um return 1 zu erhalten?

Ja. Nicht besonders effizient, das ist eben so bei einfachen Beispielen. Rekursion spielt ihre Stärke erst bei komplizierteren Sachen aus.