Rekursion VS Iteration.
-
Ich les' mir gerade das Anfänger-Tutorial eines Boardusers durch (hab' vergessen wessen es ist) und bin gerade bei der Lektion bzg. Rekursion und Iteration.
Dazu hätte ich eine Frage;
"Wir sehen, die Ausgabe auf dem Bildschirm sagt, dass Rekursion und Iteration das gleiche Ergebnis liefern. Doch man sollte bei Rekursion immer bedenken, sie ist langsam! Sehr langsam! Denn es muss jedesmal die Funktion aufgerufen und neue Variablen angelegt werden..."
Wie sieht dies aus, wenn ich einen Pointer verwende?
Es müsste keine Variable angelegt werden sondern nur verändert werden und dies muss auch bei der Iteration geschehen.
-
die adressen, die im zeiger stehen, müssten trotzdem kopiert werden.
außerdem kostet ein funktionsaufruf zeit!
argumente auf den stack, etc.
-
Klingt nach premature optimization. Rekursion bietet sich bei vielen komplizierteren Problemen direkt an, ist oft einfacher zu implementieren, und führt schneller zu funktionierendem Code als Iteration. Natürlich nur, wenn man Rekursion überhaupt verstanden hat und nicht von vornherein als langsam abtut! Wenn sich der entsprechende Code im nachhinein als performancetechnisches Nadelöhr herausstellt, kann man immer noch versuchen, daraus ne Iteration zu machen.
Man sollte sich nicht von den üblichen Anfängerbeispielen (Fakultät, Fibonacci, Länge einer einfach verketteten Liste, etc.), bei denen tatsächlich besser Iteration angebracht wäre, täuschen lassen.
-
aus dir spricht der CLer
-
@Bashar:
ich denke, es ist besser wenn man zuerst versucht das ganze iterativ zu bauen. stoesst man da auf schwierigkeiten, schaut man nach ob es rekursiv einfacher geht.geht es rekursiv und iterativ gleich schwer, nimmt man iterativ.
(das ist mein schema, an das ich mich halte)
-
Original erstellt von <Donald E. Knuth>:
aus dir spricht der CLerinwiefern?
-
er ist ja nichtmal bereit auf do zu verzichten, um tail-recursion nutzen zu können
-
to iterate is human, to recurse divine
sach ich nur
-
"divine" -- hehe, klingt nach religiöser Verblendung. Scheme-Fanatiker
-
hmm... _deshalb_ fällt es mir immer relativ schwer, prozeduren tail-recursive statt iterativ zu schreiben... hat jemand nen geisteraustreiber zu hand?
-
Hallo
Durch Rekursion kann häufig schöner, kompakter und intuitiv verständlicher Code erzeugt werden, vorausgesetzt natürlich das Problem lässt eine sinnvolle rekursive Definition zu. Leider wird sie immer als grundsätzlich schlecht weil langsam deklariert.
Wäre es nichtmal an der Zeit ein paar Tests bzgl. der Geschwindigkeit von rekursivem Code zu machen ? Solche Tests hatten wir ja schon häufiger hier.
Aber eben keine Fakultäten berechnen sondern etwas mit Bäumen oder Graphen.space
-
Wer sagt, dass Rekursion immer schlecht ist? Mal von Shade und dem OP - der sich auf Shade bezieht - abgesehen? Wenn ich nen Parser recd (recursive-descent) schreiben kann, dann tu ich das auch.