Rekursive Funktion

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.