kleine frage zu rekursion

[Evian]

Ich habe mich heute mit einem Kollegen gestritten und ganz langsam kommt so ein sehr ungutes Gefühl, dass ich mich vielleicht geirrt haben könnte. Meine Frage wäre: Gibt es ein Problem, dass sich nur rekursiv lösen lässt?

gruß

Phill

[MrKnogge]

Da letztendlich alles auf Assembler hinausläuft nein, du kannst alle Probleme die sich rekursiv lösen lassen auch anders lösen, allerdings oft aufwendiger und zum Teil sogar um einiges langsamer.

Gruß

[alzaimar]

Nein. Iterativ und Rekursiv ist untereinander austaschbar.

Selbst die Ackermannfunktion ist iterativ lösbar. Ich hab das hier mal gepostet, irgendwo.

[Tyrael Y.]

Rekursion und Iteration ist gegeneinander austauschbar....in jedem Falle.

Ich würde aber versuchen jedes Problem eher iterativ als rekursiv zu lösen, da Rekursionen, in der Regel, mehr Speicherplatz allokieren.

[Mr. Pink]

aber dafür sehr viel eleganter uns schöner sind! :wink:

für kommerzielle zwecke ist das zwar egal, aber ich finds immer sehr schön rekursive algorithmen einsetzen zu können, grade weil sie so unglaublich stark sind (ist doch iwie toll, wie 4 zeilen (effektiver) code über mehrere stunden ein kombinatorisches problem lösen), ich bin jedesmal stolz wenn ichs geschafft habe rekursionen geschickt einzusetzen, bei mir kommts aber auch nciht auf effektivität an, sondern es geht mir mehr und des programmierens willen, außerdem isses gur für die info-note :mrgreen:

[alzaimar]

... und man kommt einfach schneller ans Ziel, z.B. bei Permutationen: Mit Rekursion: 4 Zeilen, 5 min, ohne Rekursion:1-2 Std?. Keine Rechenzeit, sondern Entwickungszeit.

Aber es gilt eben auch hier: Für jedes Problem das richtige Werkzeug: Pattern-Matching würde ich kaum rekursiv lösen, TSP schon.

[3_of_8]

Zählt eine Stack-Lösung auch als iterativ? Irgendwie simuliert man damit ja praktisch eine Rekursion.

[Mr. Pink]

Zitat:

Zitat von alzaimar

... und man kommt einfach schneller ans Ziel, z.B. bei Permutationen: Mit Rekursion: 4 Zeilen, 5 min, ohne Rekursion:1-2 Std?. Keine Rechenzeit, sondern Entwickungszeit.

Aber es gilt eben auch hier: Für jedes Problem das richtige Werkzeug: Pattern-Matching würde ich kaum rekursiv lösen, TSP schon.

grade tsp find ich ist ein sehr schönes beispiel, wobei in der realttät man wohl eher mit schnittebenenverfahren arbeitet und entsprechenden heuristiken ;), aber elgent ist natürlich rekursives backtracking (von der progarmmierung her, sonst eher ineffektiv, aber ist ja acuh np-vollständig..)

@3_of_8: eher andersrum: rekursionen arbeiten mit nem stack, soweit ich weiß, 100% sincher bin ich mir nciht

[3_of_8]

Wir reden aneinander vorbei.

Rekursionen schmeißen ihre Parameter/Rücksprungadressen auf den Prozessstack.

Rekursionen lassen sich ohne rekursive Funktionsaufrufe realisieren, indem man das ganze emuliert: Man nimmt sich einen Stack und schmeißt die relevanten Variablen drauf und hat damit zwar keine klassische Rekursion, aber irgendwie doch. :mrgreen:

[Mr. Pink]

ist wohl ne definitionssache: eigtl. hat man eine rekursion, wenn eine _funktion_ sich _selber_ aufruft, in deinem fall braucht man aber wohl mehrere funktionen, eine die einliest, eine die ausliest, vllt noch anderes, kommt eben drauf an. bei einer klass. rekursion geht das ja alles in einem.
ich würd sagen, das ist iterativ und damit, wer hätte es gedacht, nicht rekursiv. vor allem isses nicht so genial :D