endrekursion technisch möglich?
-
Hallo, ich bin Neuling in C, da ich C in Zukunft verwenden will um Microchips zu programmieren.
Nun schreibe ich gerade an einer Funktion die ich mal in ocaml geschrieben habe. Dort ist es so dass wenn bei einer rekursiven Funktion der letzte Aufruf die Funktion selber ist kein weiterer Speicher verbraten wird,da die Funktion nicht auf das return wartet.
Ist das bei C auch so? Oder liegt in C immer noch ein Vermerk auf dem Heap "Warte auf die Antwort deines Kindes?"
Danke
-
wenn ich micht nicht irre, und ich irre mich oft, werden rekursive funktionen auf den stack geladen, bzw. ihre parameter und rücksprungadressen.
das zeugt bleibt dort liegen, bis es eventuell von einer anderen funktion, die ihren kram auf den stack puscht, überschrieben wird. einen solchen vermerk gibt es meines wissens nach nicht; juckt ja auch keinen, was dort drinsteht.
-
In C wird normalerweise alles so gemacht, wie man es hinschreibt, ohne irgendwelche überraschenden Dinge im Hintergrund. Wenn da ein rekursiver Funktionsaufruf im Programm steht, wird die Funktion auch rekursiv aufgerufen, und braucht auch jedesmal Platz auf dem Stack.
Abgesehen von Optimierungen durch den Compiler. Es ist möglich, dass der Compiler so eine Endrekursion zu einer einfachen Schleife optimiert, der Standard verbietet es auch nicht (der sagt ja überhaupt nichts über irgendeinen Stack), aber verlassen sollte man sich darauf nicht.
Vor allem, wenn es so viele rekursive Aufrufe sind, dass der Stack überlaufen könnte, sollte man besser von Hand eine Schleife daraus machen.
-
namespace invader schrieb:
Vor allem, wenn es so viele rekursive Aufrufe sind, dass der Stack überlaufen könnte, sollte man besser von Hand eine Schleife daraus machen.
yo, und wenn's geschwindigkeitskritisch ist, dann auch.
am besten ganz auf rekursion verzichten, ausser in ausnahmefällen.
-
+fricky schrieb:
yo, und wenn's geschwindigkeitskritisch ist, dann auch.
*pflaum*
der hardwarestack ist im allgemeinen schneller als der softwarestack. wir haben es nicht hingekriegt, die tüme von hanoi iterativ schneller hinzukriegen als rekursiv. rekursion ist nicht automatisch lahm.volkard schrieb:
am besten ganz auf rekursion verzichten, ausser in ausnahmefällen.
*pflaum*
am besten nur logarithmisch beschränkte rekursion nehmen, also beim divide and conquer nur den kleineren abschnitt rekursiv machen, oder wo aus dem kontext heraus besonders tiefe rekursion quatsch ist (verzeichnisse).
-
danke,dann werd ichs wohl lieber in den imperativen Sytle umschreiben.
Hab mich wohl da oben vertippt,meinte natürlich Stack. Und das ist genau meine Angst, dass der bei dem kleinen Chip gern einfach mal überläuft.
-
Tail transfer macht meist nur in funktionalen Sprachen Sinn, da Rekursion dort das einzige Mittel fuer rekursive als auch iterative Prozesse ist. In imperativen Sprachen hat man explizite Mittel wie for oder while fuer Iterationen. Moeglich waere es trotzdem, jedoch wuerde dieses "Feature" nur selten Anwendung finden. Es gibt auch z.B. Lisp (or whatever you want) -> C Kompiler, die deinen Code automatisch in das entsprechende Konstrukt ueberfuehren.
-
volkard schrieb:
+fricky schrieb:
yo, und wenn's geschwindigkeitskritisch ist, dann auch.
der hardwarestack ist im allgemeinen schneller als der softwarestack. wir haben es nicht hingekriegt, die tüme von hanoi iterativ schneller hinzukriegen als rekursiv. rekursion ist nicht automatisch lahm.
klar, wenn du aufwändige strukturen benutzen musst, nur um rekursion zu umgehen, dann ist sicherlich die rekursive lösung die bessere.
-
hardwarestack ... softwarestack.
Ich frage mich gerade, was das wohl sein koennte :).
-
knivil schrieb:
Ich frage mich gerade, was das wohl sein koennte.
im ernst?
-
Oh, ich weiss schon was gemeint ist, aber die Wortwahl finde ich eher unguenstig.
-
knivil schrieb:
Oh, ich weiss schon was gemeint ist, aber die Wortwahl finde ich eher unguenstig.
sie ist sofort lesbar. und ich habe sie auch nur von meinem professor übernommen. welche würdest du denn vorschlagen?
-
volkard schrieb:
knivil schrieb:
Oh, ich weiss schon was gemeint ist, aber die Wortwahl finde ich eher unguenstig.
sie ist sofort lesbar. und ich habe sie auch nur von meinem professor übernommen. welche würdest du denn vorschlagen?
Darueber habe ich die letzten 3 Minuten nachgedacht ... mit wenig Erfolg :). Leider draengte sich immer ein Bild von einem Stapel aus Rechnern vs ein Stapel aus DVD-Scheibchen auf, die gegeneinander Sackhuepfen.
-
knivil schrieb:
Leider draengte sich immer ein Bild von einem Stapel aus Rechnern vs ein Stapel aus DVD-Scheibchen auf, die gegeneinander Sackhuepfen.
die DVDs sind auch hardware.
-
knivil schrieb:
Darueber habe ich die letzten 3 Minuten nachgedacht ... mit wenig Erfolg. Leider draengte sich immer ein Bild von einem Stapel aus Rechnern vs ein Stapel aus DVD-Scheibchen auf, die gegeneinander Sackhuepfen.
du hast nicht viel mit programmierung zu tun, stimmts?
-
Aber der Inhalt der DVDs ... um den geht es ja. Bei dem Stapel Rechnern ist eher z.B. der Prozessor ausschlaggebend. Und nein, ich habe 'ne Menge mit Software, Hardware und Programmierung zu tun.
-
knivil schrieb:
Und nein, ich habe 'ne Menge mit Software, Hardware und Programmierung zu tun.
dann wundert's mich, dass diese begriffe so ungewöhnliche assoziationen bei dir hervorrufen. 'computermenschen' denken dabei normalerweise automatisch an das richtige.
-
knivil schrieb:
Aber der Inhalt der DVDs ... um den geht es ja. Bei dem Stapel Rechnern ist eher z.B. der Prozessor ausschlaggebend.
gegenbeispiele1: bei meinem kameraserver ist die software ausschlaggebend. linux-installation, ftp-server und ein paar scripts, die die platte nur zu 95% voll werden lassen. dürfte bei den meisten jedem webservers auch so sein, daß die software ausschlaggebend ist, auch bei diesem hier, auf dem dieses forum läuft.
gegenbeispiel2: jede DVD, die teil eines mobiles ist.Und nein, ich habe 'ne Menge mit Software, Hardware und Programmierung zu tun.
dann kannste mich ja beraten, wie ich die keller nennen sollte.
-
Das mit dem ausschlaggebend meinte ich anders ... Wie wuerdest du denn einen Stapel Software beschreiben (keinen Softwarestack)? Sei es drum. Keine Ahnung wie ich Keller nennen wuerde ... Kellerautomaten ... ich behalte meine Assoziationen mal fuer mich.
-
knivil schrieb:
Keine Ahnung wie ich Keller nennen wuerde ... Kellerautomaten ...
knivil schrieb:
Keine Ahnung wie ich Keller nennen wuerde ... Kellerautomaten ...
ein keller ist noch lange kein automat. aber wie wär's mit souterrain-repositorium? nee, das klingt ja nur noch bescheuert.