Diskussion:C-Programmierung: Rekursion
Letzter Kommentar: vor 10 Jahren von Sirrus in Abschnitt Beseitigung der Rekursion
Beseitigung der Rekursion
Bearbeiten"dass für jeden Funktionsaufruf verhältnismäßig hohe Kosten anfallen" Welche hohen Kosten fallen für jeden Funktionsaufruf an? --Sirrus 16:01, 9. Sep. 2014 (CEST)
- Speicherplatzkosten (Jeder Aufruf hat einen neuen Datenblock auf dem Stack zur Folge), aber auch Laufzeitkosten. Begriffe wie "Kosten" und "teuer" tauchen bei der Erörterung von Programmierlösungen ständig auf. Hier würde man sagen: "Die Eleganz mittels Rekursion ist teuer erkauft". Und irgendwo schlägt sich so was natürlich auch tatsächlich monetär nieder. --Buchfreund 16:19, 9. Sep. 2014 (CEST)
- Welcher 'Datenblock' abgesehen von der Rücksprungadresse wird denn bei einer rekursiven Funktion anders als bei einer Schleife auf den Stack abgelegt? Wobei auch eine Schleife, egal welcher Art eine Rücksprungadresse auf ihren Start auf den Stack ablegen muß, um nach jedem Durchlauf wieder an den Anfang springen zu können. Wenn bei jedem rekursiven Aufruf der Funktion ein neuer Speicherbereich mit Daten reserviert und initialisiert werden muß, wäre dies für jeden Schleifendurchlauf einer die Rekursion ersetzenden Schleife ebenfalls der Fall. Wenn jedoch in einer Schleife in jedem Durchlauf der gleiche Speicherbereich genutzt wird, sollte es auch in C kein Problem sein, jeder Rekursion einen Zeiger auf den gleichen Speicherbereich zu übergeben. Ich sehe daher keinen Grund, bei jedem Aufruf einen neuen Datenblock auf den Stack zu legen, wenn das bei einer Schleife nicht der Fall wäre. --Sirrus 15:22, 10. Sep. 2014 (CEST)
- Siehe w:Aufrufkonvention. Bei jedem Funktionsaufruf werden die Parameter auf den Stack gepackt. Dann muss man noch den Stackpointer zurücksetzen. 4 Takte alleine, um eine Funktion aufzurufen. Das ist teuer. Bei einer Schleife hat man aber schlimmere Probleme. Also besser kein if, keine Schleifen, und keine Funktionen verwenden.... -- Qwertz84 16:41, 10. Sep. 2014 (CEST)
- Wenn man keine Bedingungen, keine Schleifen und keine Funktionen verwendet, wird ein Programm unnötig lang, weil man das, was man normalerweise in Schleifen bzw. in Funktionen oder Rekursionen schreibt dann mehrmals nacheinander in das Programm schreiben müßte. Abgesehen davon wurde hier die "Beseitigung der Rekursion" mit einer For-Schleife gemacht. Wenn man aber bei einer Schleife schlimmere Probleme hat, sollte man doch besser die Rekursion beibehalten, als sie duch eine Schleife zu ersetzen. --Sirrus 00:04, 11. Sep. 2014 (CEST)
- Das mit dem
ifwar natuerlich ein Scherz. Es ist unmoeglich anspruchsvolle Programme zu schreiben, ohne bedingte Verzweigung zu benutzen. Auf Microcontrollern beispielsweise kann man es sich nicht aussuchen, ob man Rekursion benutzt oder Iteration. Man findet dort zumeist einen Stack vor, der gerade mal eine "Rekursionstiefe" von n erlaubt, wobei n sehr klein ist, zum Beispiel 4. Da muss man mit Iteration arbeiten. Das Problem mitifist teilweise hier beschrieben: w:Sprungvorhersage. Absolut richtig ist: Wenn man sich Muehe gibt, Bedingte Verzweigung, Schleifen und Funktionsaufrufe zu vermeiden dann wird der Code schneller. Das haben Compilerhersteller erkannt und setzen daher als eine von vielen Techniken "loop enrollment" ein, wo es geht. Man braucht sich also nicht drum zu kuemmern, sondern laesst das den Compiler machen. Hat Blitz Basic auch so eine Optimierungseinstellung? -- Qwertz84 08:28, 11. Sep. 2014 (CEST)- Funktionsaufrufe und Schleifen zu vermeiden halte ich für absoluten Blödsinn, da dadurch das Programm unnötig aufgebläht wird und die eingesparte Zeit bei der Ausführung von Programmen wird mit erheblich längeren Ladezeiten bezahlt. Eine Einsparung von Ausführungszeiten halte ich darum nur für Programme / Funktionen sinnvoll, die ohne Benutzereingaben laufen und eine sehr hohe Ausführungsgeschwindigkeit benötigen. Sobald irgend welche Eingaben erforderlich sind, verbringt ein Programm 99,99% seiner Ausführungszeit in einer Warteschleife.
- Das BlitzBasic (wird zusammen geschrieben) auf Funktionen oder Schleifen verzichtet halte ich für unwahrscheinlich, da jede Abarbeitung einer Basic-Anweisung bereits ein Funktionsaufruf ist. Dazu kommen dann noch Funktionen, die für Basicprogramme vom Benutzer eingegeben werden. In der Dokumentation wird außerdem empfohlen, für jeden mehrfach ausgeführten Programmteil Funktionen zu nutzen. Um eine hohe Kompatibilität der Programme zu erreichen, arbeitet BlitzBasic mit DirectX7 und verzichtet auf möglicherweise schnellere Funktionen späterer DirectX-Versionen. Dadurch sind aber mit BlitzBasic erstellte Programme ohne Einschränkungen oder Anpassungen auf allen Windows-Versionen seit Windows98 lauffähig, was nicht einmal auf microsoft-Programme zutrifft. Trotzdem ist BlitzBasic schnell genug um 3D-Programme mit zig-tausenden Dreiecken ruckelfrei anzuzeigen, ist aber trotzdem leicht (auch von Kindern) erlernbar und programmierbar.
- Also der Name "BlitzBasic" aus "Blitz" (für schnell) und "Basic" (für leicht erlernbar) ist durchaus berechtigt. --Sirrus 11:09, 11. Sep. 2014 (CEST)
- Das mit dem
- Wenn man keine Bedingungen, keine Schleifen und keine Funktionen verwendet, wird ein Programm unnötig lang, weil man das, was man normalerweise in Schleifen bzw. in Funktionen oder Rekursionen schreibt dann mehrmals nacheinander in das Programm schreiben müßte. Abgesehen davon wurde hier die "Beseitigung der Rekursion" mit einer For-Schleife gemacht. Wenn man aber bei einer Schleife schlimmere Probleme hat, sollte man doch besser die Rekursion beibehalten, als sie duch eine Schleife zu ersetzen. --Sirrus 00:04, 11. Sep. 2014 (CEST)
- Siehe w:Aufrufkonvention. Bei jedem Funktionsaufruf werden die Parameter auf den Stack gepackt. Dann muss man noch den Stackpointer zurücksetzen. 4 Takte alleine, um eine Funktion aufzurufen. Das ist teuer. Bei einer Schleife hat man aber schlimmere Probleme. Also besser kein if, keine Schleifen, und keine Funktionen verwenden.... -- Qwertz84 16:41, 10. Sep. 2014 (CEST)
- Welcher 'Datenblock' abgesehen von der Rücksprungadresse wird denn bei einer rekursiven Funktion anders als bei einer Schleife auf den Stack abgelegt? Wobei auch eine Schleife, egal welcher Art eine Rücksprungadresse auf ihren Start auf den Stack ablegen muß, um nach jedem Durchlauf wieder an den Anfang springen zu können. Wenn bei jedem rekursiven Aufruf der Funktion ein neuer Speicherbereich mit Daten reserviert und initialisiert werden muß, wäre dies für jeden Schleifendurchlauf einer die Rekursion ersetzenden Schleife ebenfalls der Fall. Wenn jedoch in einer Schleife in jedem Durchlauf der gleiche Speicherbereich genutzt wird, sollte es auch in C kein Problem sein, jeder Rekursion einen Zeiger auf den gleichen Speicherbereich zu übergeben. Ich sehe daher keinen Grund, bei jedem Aufruf einen neuen Datenblock auf den Stack zu legen, wenn das bei einer Schleife nicht der Fall wäre. --Sirrus 15:22, 10. Sep. 2014 (CEST)