rekursiv vs iterativ

[pumuckl]

tail-rekursive funktionen können in iterative Funktionen umgewandelt werden, die meisten Compiler machen das -> kein Performanceverlust.
Andere Rekursionen können zum Teil erheblich optimiert werden. Im Normalfall ist aber die Leserlichkeit um so vieles wichtiger, dass die Frage nur wenns nötig ist von einem Profiler beantwortet werden sollte, und zwar von Fall zu Fall.

[Icematix]

Können nicht rekursive Funktionen recht schnell den Stack überlaufen lassen?

[freakC++]

Klar können die das. Das liegt dann aber eher an dir, weil deine Abbruchbedingung nicht ausgereift genug ist. Iterativ ist oft performancer, weil nicht so viel Speicher benötigt wird. So stehts im meinem Buch

lg, freakC++

[blurry333]

die rekursive Funktion lassen den Stack überlaufen, da die zwischenergebnisse auf dem stack abgelegt werden .

[unskilled]

blurry333 schrieb:

die rekursive Funktion lassen den Stack überlaufen, da die zwischenergebnisse auf dem stack abgelegt werden .

Sehr schönes aktuelles Beispiel:
Warcraft 3
Dort wird das abgehen der Wegpunkte rekursiv berechnet - da bekommt man es auch hin, den Stack zum Überlaufen zu bekommen - wenn es um Usereingaben geht, würde ich rekursive Funktionen auf jeden Fall meiden...

bb

[Nexus]

Ich würde Rekursionen nicht prinzipiell meiden, nur weil sie Stackoverflows verursachen können. Sie kommen generell selten vor, aber für gewisse Dinge wie Baum-Datenstrukturen (wo die Rekursionstiefe nur logarithmisch wächst) ist eine rekursive Vorgehensweise sicher gerechtfertigt. Unter Umständen kann eine äquivalente iterative Lösung viel mühsamer sein, bringt aber nicht wesentliche Vorteile.

unskilled schrieb:

Sehr schönes aktuelles Beispiel:
Warcraft 3
Dort wird das abgehen der Wegpunkte rekursiv berechnet - da bekommt man es auch hin, den Stack zum Überlaufen zu bekommen

Würde ich gern mal ausprobieren, kannst du etwas konkreter werden?

[SeppJ]

Nexus schrieb:

unskilled schrieb:

Sehr schönes aktuelles Beispiel:
Warcraft 3
Dort wird das abgehen der Wegpunkte rekursiv berechnet - da bekommt man es auch hin, den Stack zum Überlaufen zu bekommen

Würde ich gern mal ausprobieren, kannst du etwas konkreter werden?

Ich dachte da kommt vorher immer ein Meldung die sagt, dass die Wegepunkteliste voll sei.

[Bashar]

Kóyaánasqatsi schrieb:

blurry333 schrieb:

klar zum Implementieren ist rekursiv oftmals leichter und schöner zu lesen.

Äh, finde ich überhaupt nicht, was soll daran schöner sein?

Wirst du schon noch merken, wenn du mal eine schreibst.

blurry333 schrieb:

Aber gilt das auch für die Performance. Was ist allgemein besser ?

Keine Ahnung, sollte aber beides gleich "schnell" sein.

Isses aber nicht. Allgemein dürfte die iterative Variante schneller sein, wobei das davon abhängt ob 1) überhaupt beide Algorithmen äquivalent sind und 2) ob der manuell verwaltete Stack in der iterativen Version effizient implementiert ist.

SeppJ schrieb:

ein Meldung die sagt, dass die Wegepunkteliste voll sei

Die würde bei einem Stackoverflow nicht kommen, klarer Fall von Iteration.

[drakon]

Bashar schrieb:

SeppJ schrieb:

ein Meldung die sagt, dass die Wegepunkteliste voll sei

Die würde bei einem Stackoverflow nicht kommen, klarer Fall von Iteration.

Kann überhaupt gescheit rausfinden, wie viele Aufrufe man höchstens machen darf? Mir fällt so spontan nicht wirklich was gutes ein.

blurry333 schrieb:

die rekursive Funktion lassen den Stack überlaufen, da die zwischenergebnisse auf dem stack abgelegt werden .

Nicht nur. Auch Argumente, lokale Variablen usw. werden wahrscheinlich auf den Stack gepusht. Ich habe mal ein wenig damit rumgespielt und mehr als ein paar Tausend rekursive Aufrufe lagen nicht drin. (Man kann das bestimmt noch einstellen, dass man mehr Speicher zur Verfügung hat o.ä, aber das ist auch nicht das wahre).

Kóyaánasqatsi schrieb:

Äh, finde ich überhaupt nicht, was soll daran schöner sein?

Rekursion ist in einem gewissen Sinn viel mathematischer, als Iteration und daher können mathematisch rekursiv elegang formulierte Fälle wirklich schön beinahe 1:1 in Code übernommen werden. (Implementier mal z.b Towers of Hanoi, eine Funktion, die dir die Fibonacci Zahlen oder eine, die dir die Fakultät ausgibt, dann wirst du sehr schnell merken, dass das iterativ einges mehr an Denk/Programmierarbeit abverlangt, als die rekursive Version. Oder aber auch das füllen eines Baumes ist ein gutes Beispiel).

[unskilled]

SeppJ schrieb:

Nexus schrieb:

unskilled schrieb:

Sehr schönes aktuelles Beispiel:
Warcraft 3
Dort wird das abgehen der Wegpunkte rekursiv berechnet - da bekommt man es auch hin, den Stack zum Überlaufen zu bekommen

Würde ich gern mal ausprobieren, kannst du etwas konkreter werden?

Ich dachte da kommt vorher immer ein Meldung die sagt, dass die Wegepunkteliste voll sei.

Ne, da kommt eine Zugriffsverletzung und dein WC3 schmiert ab - der andere freut sich, weil er nen Hack hat, der das nicht nur halb automatisch für ihn erledigt sondern auch noch so im Programmspeicher rumpfuscht, dass er selbst keine Probleme hat...

bb

[hustbaer]

Kóyaánasqatsi schrieb:

blurry333 schrieb:

klar zum Implementieren ist rekursiv oftmals leichter und schöner zu lesen.

Äh, finde ich überhaupt nicht, was soll daran schöner sein?

alles? schonmal was programmiert? nö? naja dann kannst dus auch nicht wissen...

blurry333 schrieb:

Aber gilt das auch für die Performance. Was ist allgemein besser ?

Keine Ahnung, sollte aber beides gleich "schnell" sein.

es ist das schneller, was man besser implementiert. üblicherweise ist das die rekursive variante, da einem der compiler/die CPU viel arbeit abnimmt, und das besser, als man es selbst machen würde.

[siecpp]

hustbaer schrieb:

üblicherweise ist das die rekursive variante, da einem der compiler/die CPU viel arbeit abnimmt, und das besser, als man es selbst machen würde.

Da müsste der Compiler ja die ganzen rekursiven Funktionsaufrufe wegoptimieren, da diese ja einen gewissen Overhead produzieren. Ist das tatsächlich der Fall?

[hustbaer]

siecpp schrieb:

hustbaer schrieb:

üblicherweise ist das die rekursive variante, da einem der compiler/die CPU viel arbeit abnimmt, und das besser, als man es selbst machen würde.

Da müsste der Compiler ja die ganzen rekursiven Funktionsaufrufe wegoptimieren, da diese ja einen gewissen Overhead produzieren. Ist das tatsächlich der Fall?

Nein, das ist nicht der Fall, Compiler können Rekursionen nur sehr bedingt optimieren, nämlich eigentlich nur sog. "Tail Recursion". Also Rekursive Aufrufe ala "return myself(param);". Wenn du etwas wie z.B. QuickSort implementierst, kommst du mit Tail Recursion nicht aus, und der Compiler wird keine Chance haben, sämtliche rekursiven Aufrufe wegzuoptimieren.

Aber wieso gehst du davon aus, dass ein rekursiver Funktionsaufruf Overhead wäre? Oder besser: mehr Overhead, als eine selbst gewurstelte iterative Implementierung hätte.
Eine iterative Implementierung ist ja nicht einfach die Rekursive minus den rekursiven Aufrufen. Statt den rekursiven Aufrufen musst du ja eigenen Code schreiben, der dann diverse Dinge auf selbst gemanagten Stacks speichert etc.

Aber du kannst es ja einfach mal ausprobieren, und uns dann deine Ergebnisse mitteilen.

[life]

unskilled schrieb:

SeppJ schrieb:

Nexus schrieb:

unskilled schrieb:

Sehr schönes aktuelles Beispiel:
Warcraft 3
Dort wird das abgehen der Wegpunkte rekursiv berechnet - da bekommt man es auch hin, den Stack zum Überlaufen zu bekommen

Würde ich gern mal ausprobieren, kannst du etwas konkreter werden?

Ich dachte da kommt vorher immer ein Meldung die sagt, dass die Wegepunkteliste voll sei.

Ne, da kommt eine Zugriffsverletzung und dein WC3 schmiert ab - der andere freut sich, weil er nen Hack hat, der das nicht nur halb automatisch für ihn erledigt sondern auch noch so im Programmspeicher rumpfuscht, dass er selbst keine Probleme hat...

--------------------------------------------------------------------------
WARCRAFT III: THE FROZEN THRONE VERSION HISTORY
--------------------------------------------------------------------------

--------------------------------------------------------------------------
Patch 1.24d
--------------------------------------------------------------------------

FIXES

- Fixed a client crash related to queuing too many invalid build commands
("crash hack").

============================

[Badestrand_]

VS 2008 optimiert die Tail Recursion meiner Fakultät nicht weg. Die Fibanocci-Folge zu bestimmen dürfte iterativ auch performanter sein. Schöner nicht.

[hustbaer]

Badestrand_ schrieb:

VS 2008 optimiert die Tail Recursion meiner Fakultät nicht weg.

hast du das im release probiert? hast du dir den assembler-code angesehen?

Die Fibanocci-Folge zu bestimmen dürfte iterativ auch performanter sein. Schöner nicht.

vermutlich, ja. und natürlich sind alle anderen dinge auch so einfach iterativ zu implementieren wie die fibanocci folge.

[Badestrand_]

hustbaer schrieb:

Badestrand_ schrieb:

VS 2008 optimiert die Tail Recursion meiner Fakultät nicht weg.

hast du das im release probiert? hast du dir den assembler-code angesehen?

Ja, und es hat mich auch gewundert.

hustbaer schrieb:

Die Fibanocci-Folge zu bestimmen dürfte iterativ auch performanter sein. Schöner nicht.

vermutlich, ja. und natürlich sind alle anderen dinge auch so einfach iterativ zu implementieren wie die fibanocci folge.

Danach sollte mein Post eigentlich nicht klingen

[siecpp]

hustbaer schrieb:

Aber wieso gehst du davon aus, dass ein rekursiver Funktionsaufruf Overhead wäre? Oder besser: mehr Overhead, als eine selbst gewurstelte iterative Implementierung hätte.
Eine iterative Implementierung ist ja nicht einfach die Rekursive minus den rekursiven Aufrufen. Statt den rekursiven Aufrufen musst du ja eigenen Code schreiben, der dann diverse Dinge auf selbst gemanagten Stacks speichert etc.

Natürlich braucht man bei iterativen Implementierungen zusätzlichen Code. Ein Funktionsaufruf hat aber dennoch meistens Kosten, die ich bei einer iterativen Implementierung vermeiden kann. Wie "teuer" ein Funktionsaufruf ist, hängt natürlich stark von der verwendetet Architektur ab. Bei x86 sind Fuktionsaufrufe leider relativ langsam. Ich muss Register sichern, Argumente über den Stack austauschen, Rücksprungadresse sichern Registerinhalte wiederherstellen etc. Das brauche ich alles bei der iterativen Implementierungen nicht in dieser Weise.

hustbaer schrieb:

Aber du kannst es ja einfach mal ausprobieren, und uns dann deine Ergebnisse mitteilen.

Das wäre natürlich das Beste. Vielleicht finde ich am Wochenende Zeit das zu tuen.

[life]

siecpp schrieb:

hustbaer schrieb:

Aber du kannst es ja einfach mal ausprobieren, und uns dann deine Ergebnisse mitteilen.

Das wäre natürlich das Beste. Vielleicht finde ich am Wochenende Zeit das zu tuen.

Implementiere doch mal Tiefensuche (http://de.wikipedia.org/wiki/Tiefensuche) rekursiv und iterativ, wobei jeweils auch die "Discovery- und Finishing-Times" berechnet werden (siehe "Algorithmusbeispiel: Erzeugen des Tiefensuchwaldes (rekursiv)" Abschnitt bei Wikipedia).

Prinzipiell lohnt sich da nämlich die Umwandlung rekursiv->iterativ, da die Anzahl der rekursiven Aufrufe linear mit der Größe des Graphen ansteigen kann. Andererseits braucht man bei der iterativen Variante einen expliziten Stack, so dass der Vergleich fair bleibt. Außerdem sieht man durch die Berechnung der Discovery- und Finishing-Times, dass es durchaus kompliziert werden kann einen rekursiven Algorithmus in einen iterativen Algorithmus umzuformen (selbst mit expliziten Stack).

[drakon]

hustbaer schrieb:

vermutlich, ja. und natürlich sind alle anderen dinge auch so einfach iterativ zu implementieren wie die fibanocci folge.

Das glaube ich nicht. Gehent tut es afaik immer, aber das es immer einfach ist bezweifle ich sehr stark. (aber ich nehme mal an, dass du das ironisch gemeint hast?)