Rekursive Funktion

Hey Leute,
lerne seit kurzem C++.
Bin nun bei rekursiven Funktionen angekommen.
Mir ist schon klar, dass sich eine Funktion selbst aufrufen muss,
um sich rekursiv schimpfen zu dürfen. Aber mein Problem ist folgendes:

int fak(int n)
{
	if(n <=1) return 1;
	return (fak(n-1) *n);
}

Dieser Code sollte ja jedem bekannt sein. Berechnung der Fakultät.
Frage:

Öffnet er solange die Funktion fak, bis n=1 ist?
Wenn ja warum ist bei 1 ende? Wo ist die Abbruchbedingung.
Wie kann ich mir das bildlich vorstellen?

Danke schon mal.

cooky451

Die Abbruchbedingung ist (n <=1), sie steht in Zeile 3

if(n <=1) return 1;

Edit: Die Fakultät rekursiv zu berechnen ist übrigens eine ziemlich blöde Idee - genau so wie die, das dauernd als Beispiel zu verwursten. Aber na ja, da kannst du wohl nichts für.

wahrscheinlich habe ich jetzt einen Denkfehler.
Aber wenn n=1 ist müsste er dann nicht 0 zurückgeben?

cooky451

Trainee schrieb:

wahrscheinlich habe ich jetzt einen Denkfehler.

Jop, wahrscheinlich.

Trainee schrieb:

Aber wenn n=1 ist müsste er dann nicht 0 zurückgeben?

Mal überlegen:
n ist gleich 1
ist n kleiner oder gleich 1? Ja. Dann gib 1 zurück.

Wie kommst du überhaupt auf 0?

Hab natürlich 1 als Rückgabe Wert gemeint

fak(4)
- fak(3) * 4
- fak(2) * 3 * 4
- fak(1) * 2 * 3 * 4
- 1 * 2 * 3 * 4

So sieht ja der logische Hintergrund aus oder?
Ist das irgendwo festgelegt, dass er bei 1 aufhört, und nicht bis
-1 oder so weitermacht?

Und wo ist geschrieben, dass die Ergebnisse der zuvor stehenden Funktion multipliziert werden?

icarus2

Das ist halt einfach die Definition der Fakultaet. Es gilt:
$n! = n\cdot(n - 1)\cdot(n-2)\cdot...\cdot 2 \cdot 1$
und man sieht daraus, dass
$n! = n \cdot (n-1)!$

Und dann etwas anders formuliert:

$factorial(n) = \begin{cases} \begin{matrix} n \cdot factorial(n-1) & ,falls \;\; n \geq 2 \\ 1, \quad & ,sonst \end{matrix} \end{cases}$

Auch gilt per Definition
$0! := 1$

Trainee schrieb:

Hab natürlich 1 als Rückgabe Wert gemeint
fak(4)
- fak(3) * 4
- fak(2) * 3 * 4
- fak(1) * 2 * 3 * 4
- 1 * 2 * 3 * 4
So sieht ja der logische Hintergrund aus oder?
Ist das irgendwo festgelegt, dass er bei 1 aufhört, und nicht bis
-1 oder so weitermacht?

Und wo ist geschrieben, dass die Ergebnisse der zuvor stehenden Funktion multipliziert werden?

Ich glaube, das ist genau der richtige Zeitpunkt, um Visual C++ 2010 Express zu installieren. Dann machst du ein neues C++ Projekt mit Win32 Konsole. Nun fügst du noch dein Quellcode ein und setzt Breakpoints. Du drückst F5 und kannst nun genau verflogen, was genau in deinem Programm passiert, Step für Step mittels F10/F11. Und tada, du hast die Rekursion mit Fakultät verstanden.

cooky451

@Trainee
Meinst du in der Funktion oder meinst du die Definition der Fakultät?
1. Hast du if Abfragen verstanden? oO
2. Kennst du Wikipedia? oO
Also sorry, aber ich verstehe wirklich nicht, wie man da noch Fragen zu haben kann.

pyhax

Wieso sollte man Fakultät eigentlich nicht rekursiv berechnen?

wollewausfander

Trainee schrieb:

Wie kann ich mir das bildlich vorstellen?

Ok,also hier mal ein laienhaftes Bild, aber sowas von, dass es sicherlich schon fast OffTopic hier ist...

Du stehst oben an einer Treppe. Sagen wir, die hat 15 Stufen (Du willst also die Fakultaet von 15 berechnen). Angenommen, die Stufennummern laegen als gleichwertige Anzahl Wuerfel auf den einzelnen Stufen. Die werden von allen Stufen 'eingesammelt' und multipliziert. Dein Onkel sagt nun, 'hol mir die 15. Fakultaet von der Treppe ab'. Du gehst zur 15. Stufe. Da das aber die Nr.15 und nicht die Nr. 1 ist, bekommst Du wegen return (fak(n-1) n); woertlich gesagt: 'Geh erstmal zur naechsten Stufe und bring mir deren Wuerfel, merke Dir, dass Du hier her zurueck kommst, und merke Dir, wieviele Wuerfel da lagen.' Das geht dann Stufe fuer Stufe so weiter. Wenn Du bei der letzten (Nr.1) angekommen bist, heisst es wegen if(n <=1) return 1; 'Mach gar nichts, nimm den Wuerfel und geh dahin, wo Du her kamst.'. Da Du von der vorhergehenden Stufe die Order hattest, zu merken, wohin Du zurueck musst und Dir ausserdem merken solltest, wieviel Wuerfel da lagen, kannst Du nun wegen return (fak*(n-1) n)**; die neue Anzahl der Wuerfel berechnen, naemlich den einen von der letzte Stufe, und die zwei von dieser Stufe, also 12=3. Diese 3 nimmst Du nun, und wegen return (fak(n-1) *n); sollst Du ausserdem wieder zurueck gehen. Du nimmst also die 3 gewonnen Wuerfel mit und gehst zur Stufe Nr.3. Hier wieder das Gleiche. 3 hattest Du zuletzt mitgebracht, usw.....
Ganz oben angekommen, werden die Wuerfel der letzten Stufe (naemlich 15) mit der zuletzt mit zurueck gebrachten Zahl multipliziert. Da Du nun auf der letzten Stufe bist, hast Du (da es keine weiteren Stufen mehr gibt) nur noch ein Ziel: zu Deinem Onkel (der hat naemlich die allererste fak(...) Funktion aufgerufen!) zu gehen und ihm alle Wuerfel in die Hand zu druecken.
Etwas technischer: Die Funktion ruft sich so lange selbst auf, bis sie auf 1 trifft, wo quasi 'nichts' zu machen ist, ausser dass die 1 zurueck gegeben wird. Der Abbruch ist aber erst erreicht, wenn sie 'rueckwaerts' (ueber den Returnstack) wieder all ihre Aufrufe bis zum ersten Aufruf abgeklappert hat. Saemtliche rekursiven Funkionen arbeiten nach diesem Prinzip, also woertlich 'mach erstmal weiter und berichte mir, wenn Du zurueck kommst'.
Ich hoffe, hier lacht nun Niemand, aber 'bildlicher' faellts mir wirklich nicht ein...

pyhax schrieb:

Wieso sollte man Fakultät eigentlich nicht rekursiv berechnen?

Zum einen ist es deutlich langsamer, zum anderen besteht eventuell die Gefahr eines Stack-Overflows?

wollewausfander

Gugelmoser schrieb:

pyhax schrieb:

Wieso sollte man Fakultät eigentlich nicht rekursiv berechnen?

Zum einen ist es deutlich langsamer, zum anderen besteht eventuell die Gefahr eines Stack-Overflows?

Die Gefahr eines Intergerueberlaufs der Produktvariablen waechst mit zunehmenden n jedoch deutlich schneller als die eines Stackueberlaufs (zumindest im Fall der Fakultaet). Geschwindigkeit, bzw. unnoetige Verschwendung von Ressourcen ist wahrlich ein guter Grund, es nicht so zu machen.

wollewausfander schrieb:

Die Gefahr eines Intergerueberlaufs der Produktvariablen waechst mit zunehmenden n

Ist doch bei der iterativen Version genauso, oder nicht?

Beide produzieren in dem Fall ein fehlerhafter Ergebnis, die explizit rekursive Variante birgt zusätzlich noch die Gefahr eines Absturzes... Im Falle eine falschen Ergebnisses vielleicht sogar vorzuziehen. Da man also testen sollte, ob das Argument im sinnvollen Bereich liegt, macht es also nur von der Perfomanz her einen Unterschied. Und selbst da könnten sich beide Varianten vielleicht nichts nehmen, wenn der Compiler nähmlich abhängig von Deiner Implementierung der Rekursion eine Tail-Rekursion erkennt und selbständig durch eine Schleife mit Abbruchbedingung ersetzt.

In anderen praktischen Fällen kann die Situation natürlich deutlich anders gelagert sein.

wollewausfander

Gugelmoser schrieb:

wollewausfander schrieb:

Die Gefahr eines Intergerueberlaufs der Produktvariablen waechst mit zunehmenden n

Ist doch bei der iterativen Version genauso, oder nicht?

Natuerlich ist das da auch so, aber Du hast meinen Satz abgeschnitten. Ich schrieb 'schneller als Stackoverflow'. Bei der iterativen Loesung hast Du ja das Stackproblem nicht.

Ich bin allerdings Neuling in Sachen C++, komme von Java. Aber solch grundlegende Dinge sollten sich in den verschiedenen Implementierungen nur unwesentlich unterscheiden.

icarus2

Stackoverflow duerfte nicht so ein Problem sein bei der Rekursion. Da n! asymptotisch exponentiell waechst bekommt man schon nach sehr wenigen rekursiven Aufrufen sehr grosse Zahlen. Da ist - wie schon gesagt - Overflow ein wesentlich groesseres Problem.

Es ist einfach sinnlos n! rekursiv zu berechen, da bei jedem rekursiven Aufruf ein Overhead (Callstack) entsteht und die iterative Implementierung extrem einfach ist.

Warum wird es trotzem oft als Beispiel fuer Rekursion gebraucht? Weil es so einfach ist, dass es jeder verstehen sollte. Auch wenn dem offenbar nicht immer so ist...

krümelkacker

cooky451 schrieb:

Edit: Die Fakultät rekursiv zu berechnen ist übrigens eine ziemlich blöde Idee

Warum? Ist es nicht so, dass moderne Compiler aus endrekursiven Funktionen von ganz allein iterative Versionen bauen?

Die Fakultätsfunktion, wie der TE sie angegeben hat, ist nicht endrekursiv (die letzte Operation in der Funktion ist die Multiplikation, nicht der rekursive Funktionsaufruf). Ich halte es aber für vorstellbar, dass ein Compiler sie in eine endrekursive Form umstellen und entsprechend optimieren kann.

Shade Of Mine

krümelkacker schrieb:

cooky451 schrieb:

Edit: Die Fakultät rekursiv zu berechnen ist übrigens eine ziemlich blöde Idee

Warum? Ist es nicht so, dass moderne Compiler aus endrekursiven Funktionen von ganz allein iterative Versionen bauen?

In C++ ist das leider tricky. Darauf verlassen würde ich mich nicht. Es gibt Sprachen wo Tail Recursion easy ist, aber in C++ gibts ne Menge Regeln die das erschweren und da es deshalb nicht gängig ist, ist der Support bei den Compilern auch nicht so toll.

knivil

Man kann die angegebene Funktion automatisch in eine endrekursive Funktion umwandeln. Die Fakulaetsfunktion ist ein fold-right ueber den natuerlichen Zahlen. Da die Multiplikation kommutativ ist, kann fold-right leicht (automatisch) in ein fold-left umgewandelt werden. fold-left ist endrekursiv. Daraus erstellt der Kompiler eine Schleife. D.h. sollte diese Funktion nie einen Stackoverflow im Release-Mode erzeugen. Das letzte Mal als ich es ausprobiert habe, funktionierte das mit dem gcc. Verlassen wuerde ich mich darauf auch nicht, aber ein kleiner Blick in den generierten Asm-Code genuegt.