Frage zu Rekursion
-
hättet ihr vielleicht noch eine einfachere programmier aufgabe für mich, die ich mit rekursion lösen muss? Die Summe der ersten n-zahlen hab ich allerdings grad selbst schon gemacht...
-
Ganz einfach: Gib einen String rückwärts aus.
-
bandchef schrieb:
Warum ist meine kompliziert?
fib(2) = 1
dieser Fall wird doch in der Musterlösung gar nicht abgefragt, oder?
Nicht explizit. Ist aber auch nicht nötig. Schau Dir in http://s1.directupload.net/images/110125/5mss6l8s.jpg doch mal den unteren, rechten Teibaum an.
-
Die Türme von Hanoi kann man mit Rekursion lösen.
http://de.wikipedia.org/wiki/Türme_von_Hanoi
-
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.
