Frage zu Rekursion
-
Ich hab jetzt mal die Fakultät Rekursiv gemacht. Jetzt hab ich allerdings wieder das Problem, dass ich mich mit dem Baum nicht mehr auskenne...
#include <stdio.h> int fak(int n) { if(n > 1) { return n*fak(n-1); } else { return 1; } } int main() { int ergebnis = 0, n; printf("n = "); scanf("%i", &n); ergebnis = fak(n); printf("Fak(%i) = %i", n, ergebnis); return 0; }fak(3) ruft doch 3*fak(2), 2*fak(1) gibt eine 1 an die mittlere Funktion zurück und jetzt?
-
Wenn es eins ist wird im else-zweig return 1 ausgeführt und die Rekursion endet. Die Funktion stimmt ja, wo ist da die Frage?
-
Sieht also bis her so aus: http://s5.directupload.net/images/110125/89c6td78.jpg
Ich weiß jetzt aber nicht, was die zweite Instanz von fak() mit den zweimaligen Rückgabewerten von 2 machen soll...
-
Ok, Du hast jetzt fak(1) ausgerechnet. Wo wurde fak(1) aufgerufen? Achja, bei der Berechnung von fak(2). Kannst Du jetzt fak(2) berechnen?
edit: Wieso 2x? Der Aufrufgraph ist eine Linie, kein Baum! Es gibt doch nur einen rekursiven Aufruf, nicht 2!
-
nein ich kann fak(2) nicht beenden, da ja jetzt durch fak(1) (also, 2*fak(1)) wieder ein 2 entstanden ist welche mir ja nochmal fak(1) aufruft, oder?
-
Steht da eine 2 oder steht da fak(2)?
-
3*fak(2) -> 2*fak(1) -> 1
3*2*1 = 6;
-
wo soll das stehen? neben dem pfeil?
-
was is na aber dann der rückgabewert 3*fak(2) an die eigentlich aufrufende Funktion fak(3)? ist das diese 6?
-
fak(3) gibt 3 * fak(2) zurück. Also 3 * 2 und das ist (oh Wunder) 6
-
Hm, ok!
Aber so richtig einleuchten (wie z.B. grad bei den Fibonaccis) tuts mir nicht...
-
Was müsste ich denn nun bei den zwei Fragezeichen hinschreiben?
-
fak(3) = 3 * fak(2) fak(2) = 2 * fak(1) fak(1) = 1 // per Definition. fak(2) = 2 * 1 fak(2) = 2 fak(3) = 3 * 2 fak(3) = 6
-
Danke, jetzt ist es mir klar. Ich hab mich gerade immer wieder einfach zu sehr auf das Fibonaccie Beispiel zurückerinnert und dabei vergessen, dass Fib(3) ja aus zwei Rückgabewerten zusammenaddiert wurde. Bei der Fakultät aber keine Addition dabei ist, sondern einfach fak(3) dem letzen Rückgabewert von 3*fak(2) entspricht.
