Rekursive Programmierung sinnvoll? Wann und warum?

Beispiel:

foo()

Func foo()
foo()
EndFunc ;==>foo

Ausgabe:

Zitat

C:\temp\Rekursive.au3 (4) : ==> Recursion level has been exceeded - AutoIt will quit to prevent stack overflow.:
foo()

>Exit code: 1 Time: 0.234

Also mir gefällt die Idee überhaupt nicht.

Rekursiv selbst sagt erstmal nichts weiter aus das eine Funktion sich selbst mit veränderten Parameter nochmal aufruft.
Sinnvoll ist das ganze z.B. um dynamisch baumartige Strukturen durchzuarbeiten aber auch viele mathematische Berechnungen sind rekursiv.
Das Beispiel schlechthin für rekursive Programmierung ist ein Verzeichnisbaum durch alle Unterverzeichnisse bis zum letzten durchzugehen.
Eine generelle Aussage ob rekursive Programmierung sinnvoll ist oder nicht kann man nicht treffen - dies ist immer anwendungsabhängig.
Vorteile sind das diese Programmierung Programme vereinfachen kann und übersichtlicher gestalten können.
Negativ ist dagegen das jeder Rekursionsaufruf ein Funktionsaufruf darstellt und das bedeutet Overhead da für jede Funktion jeweils immer ein Stackframe erzeugt werden muss etc.
Ansonsten komme ich wieder auf meine Aussage zurück: eine generelle Aussage ist nicht mögich. Ist abhängig vom zu lösenden Problem.

Edit: Einleuchtend beschrieben ist das ganze >>Hier<<

Ich halte Rekursion soweit für sinnvoll, das kleinere mathematische Berechnungen und Algorhythmen rekursiv bearbeitet werden, z.B. die Berechnung der Fakultät. Allerdings sollte man darauf achten, dass Autoit meines Wissens nach nur ein Rekursionslevel von höchtens 4712 (bin mir nicht sicher) zulässt. Für Funktionen, die einen höheren Input haben, ist das meines Erachtens Schwachsinn, da man eine starke Begrenzung hat.
Außerdem lässt die Geschwindigkeit manchmal zu wünschen übrig.
Hier z.B. eine rekursive Additionsfunktion, die leider nur positive Ergebnisse zwischen 1 und 4712 zulässt:

Hi,
wie AspirinJunkie schon erklärt hat, bieten sich bei manchen Problemen iterative Lösungen an, oder auch rekursive, oder auch beide. Rekursionen bieten sich z.B. an, wenn man Code sparen möchte, das geht dann aus den angesprochenen Gründen (Stack, Verwaltung usw) auf kosten der Geschwindigkeit.

Ein schöner Thread zum Thema findet sich hier.

Zitat von ohforf

Also mir gefällt die Idee überhaupt nicht.

Kann ich nachvollziehen, du hast nämlich garkeine rekursive Funktion erstellt, sondern einen endlos-Speicherfüller! Eine rekursive Funktion enthält nämlich ein Rückkehr-Kriterium, irgendwie muss ja abgefragt werden, wann die Funktion zu ihrem Aufrufer zurückkehren soll...

foo()

Func foo()
if abbruchkriterium then return
foo()
EndFunc ;==>foo

Hi,
Wie stayawayknight schon erwähnte ist die Berechnung der Fakultät ein klassisches Beispiel für die Anwendung der rekursiven Programmierweise. Ein anderes Beispiel
hier für ist der QuickSort-Algorhitmus, der ja bekanntlich (auch nach meinen Feststellungen^^) der schnellste ist. Er 'belastet' zwar den Stack 'ziemlich', das sollte bei modernen Rechnern aber kein Hindernis sein. Wer mag, kann ja mal probieren, den QuickSort traditionell programmieren. Es wird sicherlich nicht schneller werden. Wer jedoch mit der rekursiven Programmierung Programmierung Mühe hat, kann im Bereich Sortierung z.B. auf den ShellSort zurückgreifen, der auch 'ziemlich schnell ist.
Es läßt sich aber auch so betrachten: Manch einer mag lieber For..Next-Schleifen, während andere eine Do..Until-Schleife oder While..Wend bevorzugen.
Es kommt eben ganz auf den Programmierer an und natürlich auf seine Art zu programmieren: This is a free language, program as you want..
Gruß
ytwinky

Zitat von Andy

du hast nämlich garkeine rekursive Funktion erstellt, sondern einen endlos-Speicherfüller!

Genau das ist der Knackpunkt.
Einfach ausgedrückt, wird bei jedem Funktionsaufruf die Rückkehradresse auf den Stack gelegt, stimmts ?
Die Sache wäre wohl eleganter, wenn man einen schlichten Sprungbefehl hätte ("GOTO").
Leider haben wir den nicht - und der Stack ist begrenzt. Deshalb gefällt mir die Idee nicht.

Zitat von ohforf

Die Sache wäre wohl eleganter, wenn man einen schlichten Sprungbefehl hätte ("GOTO").

Naja darüber lässt sich streiten. An manchen Stellen hätte ich mir zwar ein Goto gewünscht aber mann kann es auch anders lösen. z.B. mit einer While Schleife, ContinueLoop und Exitloop.

PS: Wenn man Batch gecodet hat, wie ich, der wird Sprungmarken und goto wahrlich hassen lernen :D.

Zitat

Die Sache wäre wohl eleganter, wenn man einen schlichten Sprungbefehl hätte ("GOTO").
Leider haben wir den nicht - und der Stack ist begrenzt. Deshalb gefällt mir die Idee nicht.

Das "GOTO" bringt dir nicht wirklich etwas, denn den Stack musst du so oder so "bereinigen". Solange nur die Rücksprungadressen auf dem Stack liegen und etwaige Variablen innerhalb der (dann sehr einfachen) Funktion benutzt werden, würde ein "GOTO" in der untersten Rekursionsebene gefolgt von einem "Schieb den Stackpointer XXXX Bytes nach oben, um den Speicher freizugeben" die Rekursion beenden.
Wenn du allerdings, und das kommt in diversen rekursiv aufgerufenen Funktionen häufig vor, das Ergebnis des Funktionsaufrufs innerhalb der Funktion (nach deren Rückkehr) weiterverarbeitest, bringt das GOTO nichts! Denn dann muss die Rekursion komplett vonn innen nach aussen abgearbeitet werden, Stichwort rekursive Dateisuche über alle Verzeichnisse.

*OT on*

Zitat von peethebee

Goto-Code ist einfach undebugbar

Da sage ich nur:"Beschissen dokumentierter Code ist undebugbar!", völlig unabhängig davon, ob nur ein einziges GOTO verwendet wurde!

Ich weiss nicht, wieso Gott und die Welt was gegen GOTO haben, ich habe weder mit den ersten BASIC-Dialekten noch mit meinem BASIC-programmierbaren Taschenrechner noch bei Batch-Dateien irgendwelche Probleme (damit gehabt). Es ist ein Sprungbefehl wie so viele andere auch, btw. kenne ich keinen einzigen Prozessor, der etwas anderes als ein GOTO (in Form eines Sprungbefehls) verwendet, wobei man fairerweise sagen muss, dass es auch etwas ähnliches wie do/loop gibt, langsamer allerdings

Wenn AutoIt ein GOTO hätte, wäre es dann eine "schlechtere" Programmiersprache?
*OT off*

Zitat von AspirinJunkie

Einleuchtend beschrieben ist das ganze >>Hier<<

Noch was wichtiges zu: >>GOTO<<

E

Zitat von ytwinky

hier für ist der QuickSort-Algorhitmus, der ja bekanntlich (auch nach meinen Feststellungen) der schnellste ist.

Ich bin noch auf dem Stand das es Introsort ist.
Das ist prinzipiell auch ein Quicksort bei dem aber immer abgeschätzt wird ob ein Worst-Case-Fall wahrscheinlich wird (wo Quicksort ja nicht so gut ist) und in dem Fall stattdessen auf einen Algorithmus mit besserer Laufzeit umspringt (meistens Heapsort glaube ich).
Dann hat man einen Quicksort ohne dessen Nachteile im Worst-Case-Szenario.
Kann aber durchaus sein das es mittlerweile noch schnellere Algorithmen gibt.

Andy, Pee & Sprenger
Nur mal völlig meinungsfrei in den Raum geworfen:
>>Was Linus Torvalds von Goto hält<<