Frage zu Rekursion
-
Beide sind richtig, Deine nur unnötig kompliziert.
-
Da ist nichts kompliziert.
-
Warum ist meine kompliziert?
fib(2) = 1
dieser Fall wird doch in der Musterlösung gar nicht abgefragt, oder?
-
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
