| Vorheriges Thema anzeigen :: Nächstes Thema anzeigen |
| Autor |
Nachricht |
Georg
Administrator
Anmeldungsdatum: 15.02.2005
Beiträge: 57
Wohnort: Aachen
|
 Verfasst am: 22. Apr 2005 00:50 Titel: Jede iterative Lösung ist besser als eine rekursive? |
 |
|
Die Aussage wurde von meinem ADS-Prof bei jeder Gelegenheit runtergebetet, allerdings nie wirklich begründet. Rein von meinem gesunden Menschenverstand her würde ich sagen, dass die rekursiven Lösungen in den meisten Fällen, wo sie sich anbieten, einfacher und logischer zu programmieren sind. Allerdings sind sie durch die Anhäufung des Callstacks, Sprünge, Rücksprünge nicht unbedingt performant.
Was meint ihr? |
|
| Nach oben |
|
 |
|
|
kurellajunior
Administrator
Anmeldungsdatum: 14.02.2005
Beiträge: 214
Wohnort: Berlin-Pankow
|
| Verfasst am: 22. Apr 2005 09:15 Titel: |
|
|
Ich kenne eine ähnliche Aussage, die besagt, dass jede rekursive Lösung auch iterativ lösbar ist. Allerdings steht auch hier der Beweis noch aus.
Es gibt meiner Meinung nach ein paar Dinge zu beachten: Iterative Lösungen brauchen immer ein zu Beginn der Iteration bekanntes Ende. Beispiele:
[table:d13ff81118][h:d13ff81118][hc:d13ff81118]Typ[hc:d13ff81118]Bsp[hc:d13ff81118]Begrenzung[/h:d13ff81118][r:d13ff81118][cl:d13ff81118]Determinierte
Schleife[cl:d13ff81118]For-Schleife mit inkrementiertem Iterator[cl:d13ff81118]Anzahl der Durchläufe (modifizierbar)[/r:d13ff81118][r:d13ff81118][cl:d13ff81118]Endlosschleife[cl:d13ff81118]while (true) o.ä.[cl:d13ff81118]Abprüfung auf Endebedingung mit Ausbruch[/r:d13ff81118][/table:d13ff81118]
Rekursive Lösungen können ihr Ende suchen 
zweites Problem mit Iterative Lösungen: Variablen die (aus Performancegründen) innerhalb der Schleife definiert werden, sind beim nächsten Schleifendurchlauf nicht mehr existent!
Untersuchungen von Teilmengen mit dem selben Algorithus sind so sehr aufwendig. Bestes Beispiel Baum: Ein Baum unbekannter Größe unbekannter kardinalität der Äste pro Blatt soll durchlaufen werden... Mach mir das iterativ perfomant und ich lad Dich auf ein Eis ein.
Ich denke, dass allgemein iterative Lösungen für zur kompilationszeit unbekannt große dynamische Objekte nicht sinnvoll sind, da man, um sie iterativ bearbeiten zu können zur Laufzeit Informationen über ihre Dimensionen mitschleppen müsste, wer will das schon?
Jan
_________________
 |
|
| Nach oben |
|
|
Tobias
Anmeldungsdatum: 15.02.2005
Beiträge: 149
|
| Verfasst am: 22. Apr 2005 14:14 Titel: |
|
|
| Zitat: | | Ich kenne eine ähnliche Aussage, die besagt, dass jede rekursive Lösung auch iterativ lösbar ist. Allerdings steht auch hier der Beweis noch aus. |
Der Beweis wird doch auf der Maschinencode Ebene erbracht. Man kann sich vorstellen, dass der Maschinencode sog. "straight line code" ist und ein Konzept wie Rekursion existiert hier nicht wirklich. Allerdings wird es sehr gut simuliert über einen Stack und Sprungbefehle.
Ob das als Beweis ausreicht muss jeder selbst entscheiden. Allerdings ist es meines Erachtens so, dass jede Rekursive Lösung auch ein iteratives Pendant hat (welches auf dynamische Strukturen zugreift).
| Zitat: | | Variablen die (aus Performancegründen) innerhalb der Schleife definiert werden, sind beim nächsten Schleifendurchlauf nicht mehr existent! |
Auch hier ist das Konzept der Rekursion wieder durch dynamische Speicherbbereiche implementierbar. Gibt man jeder Schleife seinen eigenen privaten Bereich, ist auch hier iterative Implementation möglich.
Ihr kennt bestimmt auch alle die funktionalen Programmiersprachen. Diese benutzen nur Rekursion und kennen keine Iterationen. Diese sind viel näher an mathematischen Konventionen und sind somit auch recht übersichtlich (Nach einer Eingewöhnungszeit).
Das ändert aber nichts daran, dass bestimmte Rekursionen iterativ sehr viel effektiver implementiert werden können, während Rekursionen meist zur Programmierzeit sehr schick sind. |
|
| Nach oben |
|
|
mr. black
Anmeldungsdatum: 20.02.2005
Beiträge: 39
Wohnort: Krumbach
|
| Verfasst am: 23. Apr 2005 20:58 Titel: |
|
|
Naja ob rekursionen soooo schick sind?
Das Traversieren eines Baumes ist meiner Meinung nach der
einzige Grund etwas rekursiv zu implementieren.
Schon alleine aus performance Gründen.
wenn ich z.B. strcpy() rekursiv implementiere.
Na da zeig mir das doch mal effizient.
In der Praxis macht sowas niemand.
Ist mehr was für Theoretiker und eine Spielerei.
_________________
Zeit ist, was man auf einer Uhr abliest. A.E. |
|
| Nach oben |
|
|
Gast
|
| Verfasst am: 23. Apr 2005 21:09 Titel: |
|
|
| ich würde auch sagen, dass rekursionen vom quelltext her zwar leichter zu lesen sind als interative beschreibungen, nur machen sie auch in meinen augen nur zb bei binären bäumen oder linearen listen wirklich sinn |
|
| Nach oben |
|
|
flixgott
Gast
|
| Verfasst am: 27. Apr 2005 17:44 Titel: |
|
|
| dann ist die sicht deine augen leider ziemlich beschränkt |
|
| Nach oben |
|
|
kurellajunior
Administrator
Anmeldungsdatum: 14.02.2005
Beiträge: 214
Wohnort: Berlin-Pankow
|
| Verfasst am: 28. Apr 2005 12:49 Titel: |
|
|
Das war jetzt aber ausgesprochen unqualifiziert lieber Gast. Vielleicht nochmal etwas konstruktiver?
Jan
_________________
|
|
| Nach oben |
|
|
Tobias
Anmeldungsdatum: 15.02.2005
Beiträge: 149
|
| Verfasst am: 28. Apr 2005 16:33 Titel: |
|
|
| Ich assoziiere lineare Listen im Allgemeinen eigentlich nicht mit Rekursion (im Sinne der Implementierung in einer imperativen Programmiersprache). |
|
| Nach oben |
|
|
|
FAQ
Suchen
Mitgliederliste
Benutzergruppen
Registrieren
Profil
Einloggen, um private Nachrichten zu lesen
Login
