Frage zu Rekursion

bandchef

Hi Leute!

Ich hab folgendes Programm geschrieben:

#include <stdio.h>

int fib(int n)
{
	if(n == 0)
	{
		return 0;
	}
	if((n == 1) || (n == 2))
	{
		return 1;
	}

	return fib(n-2)+fib(n-1);

}

int main()
{
	int n, ergebnis;

	printf("n eingeben: ");
	scanf("%i", &n);

	ergebnis = fib(n);

	printf("Fib(%i) = %i\n\n", n, ergebnis);

return 0;
}

Es berechnet mir die Fibonaccizahlen.

Ich hab jetzt aber ein Problem, wenn ich den Funktionsaufruf-Baum zeichnen möchte. Ich hab euch ein Bild anghängt http://s13.directupload.net/images/110125/axaqrwo5.jpg

Wenn ich nun die Funktion fib(n) mit n=3 starte, dann werden beiden if-Abfragen falsch und es wird die Funktion mit fib(3-2) = fib(1) gestartet. Hier ist doch aber nun das n=1 und die zweite if-Abfrage würde ja richtig werden, wodurch mir doch das return eine 1 zurückgeben sollte, oder? Warum wird aber dennoch fib(1-2 = fib(-1) aufgerufen?

Ich glaub ich hab das noch nicht so richtig verstanden...

Könnt ihr mir helfen?

314159265358979

int fib(int n) { return n <= 1 ? 1 : fib(n - 1) + fib(n - 2); }

mgaeckler

Deine Ausdrucksweise ist etwas durcheinander geraten. Ein Kontrollesen Deiner Mail wäre nicht unangebracht, wenn Du willst, daß man/frau Dir hilft.

Soweit ich Dein Gefasel verstanden habe, ist Dein Programm korrekt nur Deine Grafik ist falsch.

fib(1) und fib(2) liefern jeweils 1 zurück. Sie rufen nicht jedoch fib(-1), fib(0) bzw fib(1) auf, wie Deine Grafuk sugeriert.

mfg Martin

Sqwan

314159265358979 schrieb:

int fib(int n) { return n <= 1 ? 1 : fib(n - 1) + fib(n - 2); }

Du held. Der kriegt das selbst nicht hin, und du kommt mit so nem unleserlichen mist. Sieht vllt super aus, hilft ihm aber nicht.

@bandchef
return fib(n-2)+fib(n-1);

Tausch mal den aufruf, und gib bei jedem schritt den aktiellen stand aus...
Dann kann man dir leichter helfen...

Probiere es gleich auch mal schnell selber...

314159265358979

Ich wüsste nicht, was daran unleserlich ist.

bandchef

Sorry!

ich hätte es wirklich anders sagen müssen. Das Programm funktioniert, aber ich weiß nicht wie ich einen richtigen Baum dazu zeichne...

Als Musterlösung des Programms haben wir übrigens das hier bekommen:

#include <stdio.h>

int fib(int n)
{
	if(n == 0)
	{
		return 0;
	}
	if(n == 1)
	{
		return 1;
	}

	return fib(n-2)+fib(n-1);
}

int main()
{
	int n, ergebnis;

	printf("n eingeben: ");
	scanf("%i", &n);

	ergebnis = fib(n);

	printf("Fib(%i) = %i\n\n", n, ergebnis);

return 0;
}

In der Schule haben wir so einen Baum für dieses Programm gezeichnet. Das fib(1) eine 1 zurückliefert ist mir eigentlich klar. Das fib(2) ebenfalls eine 1 zurückliefert und sich diese zwei return-Werte zu 2 addieren ist auch klar. Wo und vor allem warum nun aber dieses fib(-1) und fib(0) in den letzten Verzweigungen herkommen verstehe ich nicht.

Meiner Ansicht nach ist das aber irgendwie falsch, denn fib(2) ist ja auch noch 1. Somit fehlt ja quasi eine dritte if-Abfrage oder eben das "oder". Zu dieser Lösung haben wir diesen Baum gezeichnet: http://s5.directupload.net/images/110125/7wq24ahd.jpg

Die roten durchstreichungen sollen auch irgendwie mit den rot hinterlegten zahlen korrespondieren. wie gesagt ich hab keine Ahnung...

SG1

Ob leserlich oder unleserlich ist irrelevant. Es war einfach keine Antwort auf die Frage.

SG1

bandchef schrieb:

In der Schule haben wir so einen Baum für dieses Programm gezeichnet. Das fib(1) eine 1 zurückliefert ist mir eigentlich klar. Das fib(2) ebenfalls eine 1 zurückliefert und sich diese zwei return-Werte zu 2 addieren ist auch klar. Wo und vor allem warum nun aber dieses fib(-1) und fib(0) in den letzten Verzweigungen herkommen verstehe ich nicht.

Sie kommen nirgendwoher, weil sie einfach falsch sind! Deshalb sind sie ja auch in den späteren Grafiken durchgestrichen.

bandchef

Tausch mal den aufruf, und gib bei jedem schritt den aktiellen stand aus...

du meinst also so: return fib(n-1)+fib(n-2);

Was ich auch nicht verstehe ist wo und was ich nach jedem schritt ausgeben soll...

Sie kommen nirgendwoher, weil sie einfach falsch sind! Deshalb sind sie ja auch in den späteren Grafiken durchgestrichen.

Danke, ich habs mir ja schon fast gedacht, denn so wie ich es gemacht habe hat das alles auch so schön funktioniert Aber: irgendeine Intention muss odch mal da gewesen sein, diese "falschen" zweige trotzdem hin zu malen... Woher kommen die dann?

D.h. also, so ist der Baum richtig: http://s1.directupload.net/images/110125/5mss6l8s.jpg

Sqwan

^^ Okay... hab ich falsch verstanden... Gehen also. Brauch ich die also nicht testen...

314159265358979 schrieb:

Ich wüsste nicht, was daran unleserlich ist.

Ein anfänger versteht es nicht. Am Anfang sieht man gerne viel und nicht so abkürzungen.

SG1

bandchef schrieb:

D.h. also, so ist der Baum richtig: http://s1.directupload.net/images/110125/5mss6l8s.jpg

Ja, bezogen auf die Musterlösung. Bezogen auf deine ursprüngliche Lösung wäre unten rechts auch schon bei Fib(2) Ende.

bandchef

Welche der beiden gecodeten Versionen des Programms ist nun richtig? Die Musterlösung, oder? Sonst wär sie ja keine Musterlösung geworden

314159265358979 schrieb:

int fib(int n) { return n <= 1 ? 1 : fib(n - 1) + fib(n - 2); }

Fibonacci fail.

SG1

Beide sind richtig, Deine nur unnötig kompliziert.

314159265358979

Da ist nichts kompliziert.

bandchef

Warum ist meine kompliziert?

fib(2) = 1

dieser Fall wird doch in der Musterlösung gar nicht abgefragt, oder?

bandchef

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.

SG1

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.

HighLigerBiMBam

Die Türme von Hanoi kann man mit Rekursion lösen.
http://de.wikipedia.org/wiki/Türme_von_Hanoi