# [C++] Wie funktioniert das mit der fakultät berechnen?



## Irgendjemand_1 (12. März 2006)

Hallo, ich habe mal eine Frage.
Bei dieser Funktion

```
#include <iostream>
int fak (int val) {
    if (val > 1) {
      return fak(val-1) * val;
    }
}
```
Wird ja die Fakultät einer Zahl, nehmen wir mal 5 (120), ausgerechnet.
Als ich so eine Funktion mal in PHP gesehen habe, kam mir alles logisch vor, aber hier kam jetzt irgendwie folgende Frage auf:
Warum gibt die Funktion am Ende 120 zurück?
Meiner Meinung nach sollte sie am Ende 2 zurückgeben.
So wie ich das sehe, müsste die Funktion 5*1, 4*1, 3*1, 2*1 rechnen. Nur wie kann sie dann beim letzten Mal (2*1) 120 ausgeben?

Danke schonmal dafür, dass ihr mir die Augen öffnen werdet  Vielleicht ist es einfach schon zu spät ...


----------



## C-Lerner (12. März 2006)

Fakultät 5 errechnet sich aus:

5*4*3*2*1

müsste eigentlich 160 rauskommen.


----------



## Irgendjemand_1 (12. März 2006)

C-Lerner hat gesagt.:
			
		

> Fakultät 5 errechnet sich aus:
> 
> 5*4*3*2*1
> 
> müsste eigentlich 160 rauskommen.


Neee ...
5*4 = 20
*3 = 60
*2 = 120


----------



## C-Lerner (12. März 2006)

Äh, jo...passt doch 
Wo liegts Problem?


----------



## kroesi (12. März 2006)

Hi !

Ich denke, daß du bei diesem Beispiel die Rekursion übersiehst ... Die Funktion fak() ruft sich in ihrem Rumpf selber auf !

Beispiel :


```
fak(5) = fak(4) * 5

=>fak(5) = fak(3) *  4 * 5
=>fak(5) = fak(2) * 3 *  4 * 5
=>fak(5) = fak(1) *  2 * 3 *  4 * 5
=>fak(5) = 1 *  2 * 3 *  4 * 5
```

Ist anfangs schwierig zu verstehen, allerdings gibt es dazu im Internet unheimlich viele Beispiele, da die Fakultätsberechnung das Standardbeispiel für Rekursionen ist.

Ansonsten : bei Fragen, fragen !  

Krösi


----------



## Irgendjemand_1 (12. März 2006)

Achso, die Returnanweisung wird gar nicht verlassen?
Also direkt nach bzw in dem return wird en Rücksprung gemacht und wenn val bei 1 angekommen ist, gibt es das Ergebnis aus, oder wie?

Ich hab ja kein Problem damit rekursion an sich zu verstehen, so eine art Schleife könnte ich ja auch noch als Funktion schreiben  Irgendwie bereitet mir das mit der Fakultät schwierigkeiten


----------



## kroesi (12. März 2006)

Hi !

Also in der Return-Anweisung wird die Funtkion fak(x) aufgereufen, die dann je nach dem wieder sich selbst aufruft etc. ( bis val = 1).


>> ...wenn val bei 1 angekommen ist, gibt es das Ergebnis aus, oder wie?

genau !

Ich hab auch länger gebraucht .... ist im ersten Moment nich unbedingt trivial, aber wenn der Groschen einmal gefallen ist... wie Fahrradfahren halt.

Krösi


----------



## Curly060 (13. März 2006)

Hi!



			
				Irgendjemand_1 hat gesagt.:
			
		

> ```
> #include <iostream>
> int fak (int val) {
> if (val > 1) {
> ...



Nein, das wäre Zufall! So wie die Funktion da steht, ist sie fehlerhaft und das Ergebnis hängt vermutlich vom Compiler ab.
Nach dem if Konstrukt fehlt in jedem Fall "return 1;". Denn die Funktion soll ja auch noch etwas definiertes zurückgeben, wenn sie mit val=1 aufgerufen wurde.

Ansonsten wurde ja schon recht schön erklärt, warum die Funktion das tut, was sie tut (wenn sie denn korrekt gewesen wäre). Falls es immer noch nicht klar ist, lies dir mal durch, was ein "Kellerautomat" ist und auch ein Stapel (Stack). Das hilft meiner Meinung nach auch beim Verständnis.

Ich hab mit meinem Kumpel mal ne extrem krasse rekursive Routine gebastelt. Ich glaube, die verstehen wir selbst nicht mehr. Wenn ich die finde, kann ich die ja mal posten. 

Cheers, Ingo =;->


----------



## kroesi (13. März 2006)

Uups ...

Ingo hat natürlich vollkommen recht ....  

Und Kellerautomaten bzw. Stacks können wirklich hilfreich sein. Darauf basierend führt ein Programm nämlich Rekursionen aus. 

Man sollte halt nicht unrasiert und verpennt zu solchen Themen Antworten  bringen  

Krösi


----------



## Irgendjemand_1 (13. März 2006)

Curly060 hat gesagt.:
			
		

> Hi!
> 
> 
> 
> ...


Naja, aber wer die Fakultät von 1 ausrechnen lassen will ... 
Aber ansonsten hast du natürlich Recht. Aber ich wollte ja nur schnell zeigen, was ich meinte, also nicht so tragisch 

Mal nach diesem "Kellerautomat" und Stack suchen 
Und wenn du deine rekusrsive Routine da gefunden hast, kannst du das von mir aus gerne Posten, ich bin aber in C++ noch eher am Anfang, hab mich vorher nur mit PHP (was ich Recht gut kann, finde ich) rumgeschlagen.


----------



## Curly060 (13. März 2006)

Hi!



			
				Irgendjemand_1 hat gesagt.:
			
		

> Naja, aber wer die Fakultät von 1 ausrechnen lassen will ...



Lass es mich nochmal betonen:
Die Zeile "return 1;" nach dem if Konstrukt ist absolut essenziell und darf unter keinen Umständen fehlen, denn sonst tut deine fak Funktion ganz sicher nicht das, was du willst!

Ich glaube, ich mach es nochmal ganz deutlich, indem ich für fak(4) den Programmablauf darlege:

1) if 4>1
2) return fak(3)*4
Diese Return-Zeile kann erst einmal nicht vollständig ausgeführt werden. Warum? Weil ja zunächst mal der wert von fak(3) berechnet werden muss, bevor man ihn mit 4 multiplizieren kann. Was ist also zu tun? Nun, das Programm merkt sich einfach mal den aktuellen Zustand (das geschieht mit Hilfe eines Stacks. Das macht der Compiler für dich) und ruft die Funktion fak auf, diesmal mit dem Wert 3.
3) if 3>1
4) return fak(2)*3
Schon wieder kann die Zeile nicht ausgeführt werden, denn erstmal muss fak(2) berechnet werden. Also wieder den aktuellen Zustand merken und weiter:
5) if 2>1
6) return fak(1)*2
Und auch diese Zeile kann nicht direkt ausgeführt werden, bevor nicht der Wert von fak(1) ermittelt ist.
7) if 1>1
8) return 1
Aber jetzt! Endlich mal ne Zeile, die simpel ist! Die kann direkt und vollständig ausgeführt werden. Return heißt ja nix anderes als "zurückkehren" bzw. "zurückgeben". Beides trifft ja zu:
"return x;" bewirkt, dass zu einem vorigen Zwischenzustand zurückgekehrt wird und dabei der Wert x an den Zwischenzustand zurückgegeben wird.
Genau das passiert jetzt. Zeile 8 liefert eine 1 an den Zwischenzustand von Zeile 6 zurück. Damit ist Zeile 6 endlich vollständig ausführbar:
return 1*2;
Dieses return kehrt jetzt zum Zwischenzustand von Zeile 4 und liefert 1*2=2. Jetzt kann auch diese Zeile ausgeführt werden:
return 2*3;
Das kehrt jetzt zurück zu Zeile.... na, ich denke, es ist klar, wie es weitergeht.

Jetzt sollte auch klar sein, warum das "return 1;" so essentiell ist! Schau dir deinen Code nochmal an. Was passiert denn, wenn die if-Bedingung unwahr wird? Dann wird die Funktion beendet, ohne eine "return" gemacht zu haben. Der Compiler macht eine automatisches "return". Aber mit welchem Wert ...

So, ab jetzt sind Rekursionen kein Thema mehr, oder? ;-)

Cheers, Ingo =;->


----------



## Tasm-Devil (17. März 2006)

Hi, mir war langweilig. Ich hab dir mal n Programm für die Fakultät geschrieben:


```
#include <iostream.h>
#include <conio.h>

int main()
{
cout << "Geben Sie eine Zahl ein: ";
int Zahl;
cin >> Zahl;
int x = Zahl-1;
int Res = Zahl;
  while (x > 1)
  {
  cout << Res << " * " << x << " = " << Res * x << endl;
  Res *= x;
  x--;
  }  
cout << "Die Fakultaet von " << Zahl << " ist: " << Res;
getch();
return 0;    
}
```


----------

