Rekursion vs. Iteration

[gammatester]

Zitat von jfheins:

Wenn man den richtigen Algorithmus wählt, ist die Frage rekursiv/iterativ untergeordnet, solange man es vernüftig macht.

Das ist mM eine leere Ausssage, denn der Algorithmus enthält eine Beschreibung der Lösungsschritte und da steht natürlich drin, ob das ganze rekursiv oder iterativ ist. Wenn dem nicht so wäre, hättest Du eine unvollständige Beschreibung mithin gar keinen keinen Algorithmus.

[Delphi-Laie]

Zitat von jfheins:

=> Wenn man den richtigen Algorithmus wählt, ist die Frage rekursiv/iterativ untergeordnet, solange man es vernüftig macht.

Die Wahl des „richtigen“ (was ist damit konkret gemeint?) Algorithmus besteht doch oft genug in der Entscheidung, ob rekursiv oder iterativ.

Ich schlage mal folgendes vor: Vergleiche mal die Berechnung der Koeffizienten eines charakteristischen Polynoms einer quadratischen Matrix mit Rekursion (nach der Determinantenberechnung nach dem Laplaceschen Entwicklungssatz) mit ihren iterativen Pendants (der schnellste mir bekannte ist der von Le Verrier). Die Komplexität unterscheidet sich zwischen beiden um astronomischen Größenordnungen!

All' die, dier hier der Rekursion das Wort reden, konnte ich, sofern beide Alternativen (als Rekursion und Iteration oder sogar simpleres) zur Lösung eines Problemes verfügbar sind, noch keine einzigen Fall nennen hören, bei dem die Rekursion hinsichtlich Komplexität die überlegene Lösung darstellt. Ich bin gespannt darauf.

[negaH]

Zitat von Delphi-Laie:

Zitat von negaH:

Der einzige Grund warum eine rekursive Lösung unter Umständen einen leichten Performance-/Speicheroverhead hat liegt
in der Rechnerarchitektur begründet, ansonsten wird es zwischen beiden keinen Unterschied geben.

Ganz bestimmt nicht. Die Komplexität bzw. Effizienz von Algorithmen hat zunächst einmal überhaupt nichts mit ihrer Umsetzung zu tun.

Korrekt, du verstehst langsam. Aus dieser Sichweise heraus kann man also den Algo. iterativ wie auch rekursiv aufbauen (wenn es eine rekursive Version dafür gibt) ohne das es einen Untrschied in desen Komplexität gibt.

Erst wenn man anfängt diesen Algo. zu implementieren auf einer jeweiligen Hardware wird es nur und ausschließlich nur auf Grund dieser Hardware leichte Unterschiede zu Gunsten der iterativen Lösung geben.

Damit untermauert deine Aussage ja meine

Zitat von Delphi-Laie:

Außerdem wurde mit der rekursiven Berechnung irgendeines Gliedes der Fibonacci-Folge diese pauschale Lobhudelei der Rekursion bereits widerlegt, denn dort wird jeder Zwischenwert doppelt, dreimal oder noch (viel) häufiger berechnet.

Eben nicht. Wo ist da ein Beweis ? wenn man Äpfel mit Birnen vergleicht. Ich warte schon auf dein Argument das ja Windows auf Grund dessen das man dort alles rekursiv gelöst hat immer schlechter wird und jedes denkbare HW-System massiv ausbremst. Kannst du mir sagen woher du eigentlich weißt das die Entwickler bei MS rekursive statt iterative Implementierungen bevorzugen ?

Ich setze dagegen und behaupte das ich Fibonacci zb. auf einem FPGA sowohl iterativ wie rekursiv implementieren könnte und am Ende beides absolut identisch sein muß ! Und dabei bin ich sogar noch so fair und benutze in beiden Fällen als algortihmische Basis auch den gleichen Algorithmus und nicht Äpfel und Birnen, nicht ASIC vs. FPGA usw.

Gruß Hagen

[negaH]

Zitat:

bei dem die Rekursion hinsichtlich Komplexität die überlegene Lösung darstellt. Ich bin gespannt darauf.

Na endlich kommen wir weiter. Es gibt keinen Überlegenen, iterativ vs. rekursiv sind identisch und erst die Fähigkeiten der Hardware macht einen Unterschied. Aber dieser ist eben oft nur marginal im Speicher wie Performancebereich, ansonsten bleibt die Komplexität des Algos. erhalten, egal ob rekursiv/iterativ. Alle weiteren Tricks lassen sich dann rekursiv wie auch iterativ anwenden da es Tricks zur Verbesserung der Komplexität des Algos. sind.

Aber in der Verständlichkeit, Wartbarkeit, Definierbarkeit eines Bweweise für dessen Korrektheit gibt es gewaltige Unterschiede.

Gruß Hagen

[negaH]

Es gäbe da ein "Argument" pro Iterativ:

Nämlich das es bestimmte Problemstellung gibt die man nicht rekusiv formulieren kann. Aber das ist am Thema vorbei, da wir davon ausgehen können das ein Vergleich rekursiv vs. iterativ nur dann Sinn macht wenn auch auch vom Problem her beide Möglichkeiten gibt.

Gruß Hagen

[JasonDX]

Zitat von Delphi-Laie:

Außerdem wurde mit der rekursiven Berechnung irgendeines Gliedes der Fibonacci-Folge diese pauschale Lobhudelei der Rekursion bereits widerlegt, denn dort wird jeder Zwischenwert doppelt, dreimal oder noch (viel) häufiger berechnet.

Um Hagens Worte konkreter zu formulieren: Meine rekursive Implementierung der Fibonacci-Folge berechnet auch jeden Wert nur einmal. Ich gehe mal davon aus, dass du dich mit Rekursion und funktionaler Programmierung kaum außeinandergesetzt hast, da man schon in den Anfängen über die Konzepte des Tuplings stößt - was zur rekursiven Implementierung von Fibonacci in O(n) führt.

Zitat von negaH:

Es gäbe da ein "Argument" pro Iterativ:
Nämlich das es bestimmte Problemstellung gibt die man nicht rekusiv formulieren kann.

Es könnte schwierig werden, solche Problemstellungen zu finden. Lambda-Ausdrücke sind gleichmächtig wie TMs, somit kann alles, was iterativ berechenbar ist, auch rekursiv beschrieben werden.

greetz
Mike

[negaH]

Zitat:

Es könnte schwierig werden, solche Problemstellungen zu finden. Lambda-Ausdrücke sind gleichmächtig wie TMs, somit kann alles, was iterativ berechenbar ist, auch rekursiv beschrieben werden.

vorsicht, jetzt begibts du dich auf Glatteis. Es gibt einen mathematischen Beweis das es solche Probleme geben muß. Leider finde ich jetzt nicht auf die Schnelle bei Wikipedia die richtige Seite.

Solche Probleme gibt es also wirklich. War irgenwas mit einer Ameisensimulation oä.

Gruß Hagen

[jfheins]

Zitat von gammatester:

Zitat von jfheins:

Wenn man den richtigen Algorithmus wählt, ist die Frage rekursiv/iterativ untergeordnet, solange man es vernüftig macht.

Das ist mM eine leere Ausssage, denn der Algorithmus enthält eine Beschreibung der Lösungsschritte und da steht natürlich drin, ob das ganze rekursiv oder iterativ ist. Wenn dem nicht so wäre, hättest Du eine unvollständige Beschreibung mithin gar keinen keinen Algorithmus.

Zitat von Delphi-Laie:

Die Wahl des „richtigen“ (was ist damit konkret gemeint?) Algorithmus besteht doch oft genug in der Entscheidung, ob rekursiv oder iterativ.

Ihr habt mich missverstanden.

Bubblesort kann man Rekursiv oder Iterativ implementieren. (Standardvorgehensweise ist zwar iterativ, aber die äußere Schleife kann man ja auch als rekursion implementieren)
Wenn einem jetzt das Sortieren zu langsam geht, kann man natürlich die Implementierung anpassen, rekursion gegen Iteration testen und gucken was schneller läuft.
Viel mehr Gewinn macht man allerdings, wenn man stattdessen Quicksort, Mergesort, oder sowas hernimmt - ein anderer Algorithmus, der die gleiche Aufgabe in der Regel schneller erledigt.
Die Entscheidung rekursiv vs. iterativ ist für mich noch nicht beim Algorithmus festgelegt. Der sagt vielmehr aus, was wann wie mit welchen daten gemacht wird. Bei Quicksort z.B. "Wähle ein Pivotelement, erstelle zwei Listen mit Einträgen die größer/kleiner sind, sortiere diese Listen ebenfalls und füge am Schluss alles zusammen"

Zitat:

Ich schlage mal folgendes vor: Vergleiche mal die Determinantenberechnung mit Rekursion (nach dem Laplaceschen Entwicklungssatz) mit ihren iterativen Pendants (der schnellste mir bekannte ist der von Le Verrier). Die Komplexität unterscheidet sich zwischen beiden um astronomischen Größenordnungen!

Anderer Algorithmus, anderes Laufzeitverhalten. Das ist so wie wenn ich sage
"Vergleiche mal sie Sortierung einer diskreten Menge per iterativem Bucketsort mit rekursiven Slowsort - Die Komplexität unterscheidet sich zwischen beiden um astronomischen Größenordnungen!"

Zitat:

All' die, dier hier der Rekursion das Wort reden, konnte ich, sofern beide Alternativen (als Rekursion und Iteration oder sogar simpleres) zur Lösung eines Problemes verfügbar sind, noch keine einzigen Fall nennen hören, bei dem die Rekursion hinsichtlich Komplexität die überlegene Lösung darstellt. Ich bin gespannt darauf.

Rekursiver Quicksort ist wesentlich einfacher zu implementieren als die iterative Variante. Damit meine ich nicht das letzte Quäntchen Performance sondern Lesbarkeit und Wartbarkeit.
Oder wenn du einen binären Baum in den verschiedenen Modi (pre-order, in-order, post-order) ausgeben lassen willst.

[negaH]

Zitat:

Meine rekursive Implementierung der Fibonacci-Folge berechnet auch jeden Wert nur einmal. Ich gehe mal davon aus, dass du dich mit Rekursion und funktionaler Programmierung kaum außeinandergesetzt hast, da man schon in den Anfängen über die Konzepte des Tuplings stößt - was zur rekursiven Implementierung von Fibonacci in O(n) führt.

Wenn eine rekursive Variante eine Algos. Werte mehrfach berechnet im Vergleich zur iterative Variante dann existiert ein Unterschied in der Komplexität beider Implementierungen. Ein Unterschied in der Komplexität bedeutet das es unterscheidliche nicht mehr vergleichbare Algorithmen sind. Ergo: Äpfel und Birnen und damit nichts aussagend für den Vergleich "rekursiv vs. iteratv".

Also ganz unabhängig von "funktionaler Programmierung" und "Tupeling".

Gruß Hagen

[mkinzler]

@Hagen, er scheint nicht zu wissen, wer du bist und auch für deine Argumente wenig zugänglich