Fakultät

[konoha]

Kann mir jemand bitte den programmablauf erklären? Inbesondere die Stelle am ende n*fact(n-1). Wenn ich beispielsweise eine 5 für n habe, dann gilt doch folgende berechnung 5*(5-1) = 25-5 = 20 oder irre ich mich?

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

 

[Saheeda]

Das ist ne Rekursion. Fact() wird immer wieder mit kleineren Werten aufgerufen, bis n gleich 0 ist.

 

[Elenteria]

An der Stelle ist es nicht 5*(5-1) sondern 5*fact(5-1) also 5*fact(4) und fact(4) ist 4*fact(4-1). merkst bestimmt schon worauf das hinausläuft ;-)

 

[konoha]

Mir ist klar das die methode am ende die fakuktät der zahl n zurückgeben soll. Dennoch verstehe ich nicht wie das programm erkennt das der methodenaufruf eine fakultät ist?

Wieso wird bei n*fac(n-1) nicht ausmultipliziert? Also: n*n-n*1?
Gilt hier nicht die Regel punkt vor strich?

 

[konoha]

Das ist ne Rekursion. Fact() wird immer wieder mit kleineren Werten aufgerufen, bis n gleich 0 ist.

Wie wird der Wert n bitte kleine? Es findet am ende ja keine zuweisung fuer n statt. Wieso sollte er dann von anfaenglich 5 auf 1 runtergehen?

 

[VfL_Freak]

Moin,

Dennoch verstehe ich nicht wie das programm erkennt das der methodenaufruf eine fakultät ist?

So wie Du es ausdrückst, kann es das Programm auch nicht erkennen .....
Es wird einer Funktion, die mit 'fac' bezeichnet ist, aufgerufen, die als Parameter den Wert 'n-1' erhält !

Wieso wird bei n*fac(n-1) nicht ausmultipliziert? Also: n*n-n*1?
Gilt hier nicht die Regel punkt vor strich?

Natürlich gilt die Regel - aber scheinbar ist Dir nicht klar, was ein Methodenaufruf ist, oder ??
Bei "n*fac(n-1)" wird n-mal die Methode 'fac' mit dem Parameter 'n-1' aufgerufen !!
Du könntest ja auch sowas schreiben:

int x = n-1;
int Ergebnis = n * fac(x);

Ist es jetzt klarer ??

Mit Verlaub: wenn Dich solche Kleinigkeiten schon völlig aus dem Konzept bringen, wirst Du es beim programmieren sehr schwer haben

Gruß Klaus

 

[Elenteria]

Also gehen wir das mal zusammen durch.
wir haben n = 5. n == 0 ergibt false also springen wir in den else zweig. hier steht jetzt 5 * fact(5-1); 5-1 is 4 also steht dort 5 * fact(4). Es wir nun also 5 mit dem Ergebnis von fact(4) multipliziert. bei fact(4) gilt nun 4 == 0 ist false also gehen wir in den else zweig und rechen 4 * fact(4-1) also 4*fact(3). für fact(3) gilt nun 3 == 0 ist false also gehen wir in den else zweig und rechen 3 * fact(3-1) also 3*fact(1). für fact(2) gilt nun 2 == 0 ist false also gehen wir in den else zweig und rechen 2 * fact(2-1) also 2*fact(1). für fact(1) gilt nun 1 == 0 ist false also gehen wir in den else zweig und rechen 1 * fact(1-1) also 3*fact(0) für fact(0) gilt nun 0 == 0 ist true also geben wir 1 zurück. jetzt wird von hinten aufgelöst. Die zurückgegebene 1 von fact(0) wird mit der aus 1 aus fact(1) multipliziert das ist weiterhin 1. diese 1 wird jetzt mit der 2 aus fact(2) multipliziert und das ergibt 2. Diese zwei wird nun mit der 3 aus fact(3) multipliziert das ergibt dann 6. Diese 6 wird dann mit der 4 aus fact(4) multipliziert und ergibt dann 24. diese 24 wird dann an fact(5) weitergegeben und dort mit der 5 multipliziert und ergibt 120.

 

[VfL_Freak]

ist es wirklich so schwer eine solchen Text mal vernünftig zu formatieren ???
Davon bekommt man so ja Augenkrebs ...

BTW: eine Frage habe ich dem jetzt nicht wirklich entnehmen können !!

 

[konoha]

Danke für die Antwort. Jedoch habe ich immer noch ein Problem das zu verstehen. Nachdem Methodenaufruf am Ende fac(n-1). wird also der Methode durch den Aufruf ein neuer Wert im Form von n als Parameter übergeben. Ist das so richtig?

Was ich aber dann immer noch nicht verstehe ist. Wenn die Methode beim ersten durchlauf 5*fac(4) stehen hat, ergibt die Berechnung doch lediglich 20, was nicht 5Fakultät entsprechen würde.

 

[konoha]

für fact(0) gilt nun 0 == 0 ist true also geben wir 1 zurück. jetzt wird von hinten aufgelöst. Die zurückgegebene 1 von fact(0) wird mit der aus 1 aus fact(1) multipliziert das ist weiterhin 1. diese 1 wird jetzt mit der 2 aus fact(2) multipliziert und das ergibt 2. Diese zwei wird nun mit der 3 aus fact(3) multipliziert das ergibt dann 6. Diese 6 wird dann mit der 4 aus fact(4) multipliziert und ergibt dann 24. diese 24 wird dann an fact(5) weitergegeben und dort mit der 5 multipliziert und ergibt 120.

Hallo,
wieso wird denn wieder von hinten aufgelöst wenn die abbruchbedingung schon durch 0 == 0 erfüllt ist?

 

[Saheeda]

1. Durchlauf: 5*fac(4)
2. Durchlauf: 5* ( 4* fac(3) )
3. Durchlauf: 5* ( 4* ( 3* fac(2) ) )
4. Durchlauf: 5* ( 4* ( 3 * ( 2 * fac(1) ) ) )
5. Durchlauf: 5* ( 4* ( 3 * ( 2 * ( 1 * fac(0) ) ) ) )

fac(0) return 1
fac(1) return 1*fac(0) = 1*1
fac(2) return 2*fac(1)*fac(0) = 2 * 1 * 1
fac(3) return 3*fac(2)*fac(1)*fac(1) = 3 * 2 * 1 * 1
fac(4) return 4*fac(3)*fac(2)*fac(1)*fac(0) = 4 * 3 * 2 * 1 * 1
fac(5) return 5*fac(4)*fac(3)*fac(2)*fac(1)*fac(1) = 5 * 4 * 3 * 2 * 1 * 1

"return" heißt nicht, "Brich auf der Stelle alles ab.", sondern "Kehre an deinen Aufrufort zurück."

EDIT: Danke @Dompteur !
Ich sollte mir nen Kaffee organisieren.

 

[Dompteur]

1. Durchlauf: 5*fac(4)
2. Durchlauf: 5*fac(4)*fac(3)
3. Durchlauf: 5*fac(4)*fac(3)*fac(2)
4. Durchlauf: 5*fac(4)*fac(3)*fac(2)*fac(1)
5. Durchlauf: 5*fac(4)*fac(3)*fac(2)*fac(1)*fac(0)

@Saheda: Da hast du dich etwas vertan. Sollte es nicht so ausshen:

1. Durchlauf: 5*fac(4)
2. Durchlauf: 5* ( 4* fac(3) )
3. Durchlauf: 5* ( 4* ( 3* fac(2) ) )
4. Durchlauf: 5* ( 4* ( 3 * ( 2 * fac(1) ) ) )
5. Durchlauf: 5* ( 4* ( 3 * ( 2 * ( 1 * fac(0) ) ) ) )


Ich habe da eine Erklärung gefunden, die die Rekursion grafisch veranschaulicht. Vielleicht kann man es so besser nachvollziehen:
http://www.gym1.at/schulinformatik/...k/vk-01/jahresplan-pohlig/Tag29/Fakultaet.htm

 

[Joose]

Nachdem Methodenaufruf am Ende fac(n-1). wird also der Methode durch den Aufruf ein neuer Wert im Form von n als Parameter übergeben. Ist das so richtig?

Ja es wird der Wert übergeben, der sich durch die simple Rechnung von "n-1" ergibt

Was ich aber dann immer noch nicht verstehe ist. Wenn die Methode beim ersten durchlauf 5*fac(4) stehen hat, ergibt die Berechnung doch lediglich 20, was nicht 5Fakultät entsprechen würde.

Dein Verständnis Problem ist das du denkst hier steht 5*4 es steht aber hier : 5*fac(4)
Der Teil "fac(4)" ist aber keine Zahl sondern ein Methodeaufruf. Damit der Computer also die Rechnung ausführen kann muss er erstmal die Methode aufrufen. Die Methode liefert ihm eine Zahl zurück mit welcher er die Rechnung durchführen kann.

 

[konoha]

fac(0) return 1
fac(1) return 1*fac(0) = 1*1
fac(2) return 2*fac(1)*fac(0) = 2 * 1 * 1
fac(3) return 3*fac(2)*fac(1)*fac(1) = 3 * 2 * 1 * 1
fac(4) return 4*fac(3)*fac(2)*fac(1)*fac(0) = 4 * 3 * 2 * 1 * 1
fac(5) return 5*fac(4)*fac(3)*fac(2)*fac(1)*fac(1) = 5 * 4 * 3 * 2 * 1 * 1

EDIT: Danke @Dompteur !
Ich sollte mir nen Kaffee organisieren.

Danke! Zu meinem Bedauern muss ich leider wieder fragrn stellen. Wie kann das programm denn nach und nach eins dazu addieren? Zuvor gab es ja beim methodenaufruf fac(n-1). Nirgends steht aber jetzt fac(n+1). Wieso macht er das dann?

 

[Saheeda]

Hast du dir @Dompteur s Link angeschaut?
Es wird nichts hinzuaddiert. Die ersten Werten sind schlicht die übergebenen Parameter (die n in deiner Methode).

Hast du die Fakultät mal iterativ mit einer Schleife implementiert? Vielleicht hilft dir das beim Verständnis.
Hast du das mal im Debugger angeschaut? (z.B. Eclipse, links neben Zeilennummern nen Breakpoint setzen und dann oben statt "Run" auf "Debug" klicken).

 

[Joose]

Wie kann das programm denn nach und nach eins dazu addieren? Zuvor gab es ja beim methodenaufruf fac(n-1). Nirgends steht aber jetzt fac(n+1). Wieso macht er das dann?

Orientiere dich daran was Dompteur geschrieben hat, das ist korrekt!
Saheeda hat sich hier vertan.

 

[Neumi5694]

Danke! Zu meinem Bedauern muss ich leider wieder fragrn stellen. Wie kann das programm denn nach und nach eins dazu addieren? Zuvor gab es ja beim methodenaufruf fac(n-1). Nirgends steht aber jetzt fac(n+1). Wieso macht er das dann?

Das macht es nicht. Der zitierte Code hat einen Fehler, außerdem wird immer SUBTRAHIERT, nicht addiert. Es wird beim höchsten Wert gestartet.

Ich glaube, dir ist nicht klar, was eine Rekursion ist.
Der Grundsatz einer Rekursion ist, dass eine Funktion die gleiche Funktion noch mal aufruft.
Diese Fakultätsfunktion ist ein Paradebeispiel einer rekursiven Funktion.
Damit man Fakultät(n) berechnen kann, muss man erst mal den Wert von Fakultät(n-1) kennen.
Der Aufruf Fakultät(5) bewirkt also, dass zuerst Fakultät(4) aufgerufen wird, das Ergebnis wird mit 5 multipliziert.
Fakultät (4) wiederum lässt als ersts Fakultät(3) berechnen und multpliziert das Ergebnis mit 4
Fakultät (3) wiederum lässt als ersts Fakultät(2) berechnen und multpliziert das Ergebnis mit 3
...
Das geht so weiter, bis der Aufruf bei Fakultät(0) ankommt.
Die Funktion weiß, dass Fakultät(0) den Wert 1 hat (steht in den beiden Zeile if (n==0) und Folgezeile) und stoppt den rekursiven Aufruf an dieser Stelle.


Anmerkung: Natürlich könnte man die Fakultät auch einfach mit einer Schleife berechnen anstatt mit einem rekursiven Aufruf, aber hier soll dir wohl klar gemacht werden, wie eine Rekursion arbeitet.