-
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by JasonDX,
21. Jun 2010
So einfach ist es leider nicht - bspw. sind nicht Schleifen wirklich das Problem, sondern aufeinanderfolgende Befehle. Aber über die rein theoretische Definition von TMs lässt sich das ganze einfacher in rekursive Ausdrücke überführen.
In den 30ern von Alonzo Church, durch die Turingvollständigkeit von Lambdaausdrücken. Eine etwas einfachere und verständlichere Variante wäre die iterative...
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by JasonDX,
15. Jun 2010
Diese Schnittmenge ist die Menge der derzeit berechenbaren Sprachen.
Das Laufzeitverhalten eines Algorithmus ist nicht von der Art seiner Implementierung abhängig. Man kann relativ einfach aus einem iterativen Programm ein Rekursives erstellen, und umgekehrt. Mit selbem Laufzeitverhalten. Wenn du möchtest, kann ich dir zumindest die Idee dahinter erklären, auch wenns dann etwas theoretisch...
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by JasonDX,
13. Jun 2010
Es ist nunmal nicht jeder Deutscher in diesem Forum. Mir wärs eh lieber, wenn die ganze Diskussion auf englisch geführt werden würde. Aber danke für den Hinweis...
Du hast dich offensichtlich nicht klar genug ausgedrückt. Folgendes Zitat lässt auch relativ wenig Interpretationsmöglichkeiten offen:
Entweder du hast eine triviale Aussage getroffen (bspw. Quicksort rekursiv ist besser als...
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by JasonDX,
13. Jun 2010
Ich tendiere zu nein. Sollte ich die Zeit dafür finden, ließe sich evt. ein Beweis für die Äquivalenz beider Verfahren finden.
Ein klares Zeichen, dass du Beiträge entweder nicht liest oder nicht verstehst. Es ist bereits gezeigt worden, dass die iterative Lösung der rekursiven nicht überlegen ist. Tailrecursion is recursion! Bitte lese zukünftig Beiträge, bevor du ihnen widersprichst.
...
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by JasonDX,
11. Jun 2010
Es ist dir bisher nicht gelungen, dies zu begründen. Beide Algorithmen lassen sich sowohl iterativ als auch rekursiv implementieren. Die Schlussfolgerung deines Vergleichs unterliegt aber der Wahl des Algorithmus, nicht der Implementierungsvariante, du ziehst somit die falschen Rückschlüsse daraus.
Du vergleichst also Algorithmen. Wir vergleichen Implementierungen. Du willst uns davon...
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by JasonDX,
11. Jun 2010
Du hast es richtig erfasst: Du vergleichst Algorithmen, nicht Implementierungen. Vergleiche doch mal eine rekursive und eine iterative Implementierung des selben Algorithmus. Dann wirst du merken, dass dort kaum ein Unterschied vernehmbar ist.
Andernfalls... Ich friemle mal für dich (deine Worte) Klugheitsausscheider mal ein kleines Programm zusammen, das eine Liste von Zahlen sortiert. Ich...
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by JasonDX,
11. Jun 2010
Ja, deshalb habe ich auch den Apfel auf eine Birne abgebildet - nämlich aus der stupiden rekursiven Implementierung, bei der Werte mehrfach berechnet werden, eine Variante, bei der jeder Wert nur einmal berechnet wird. Dieser Algorithmus hat dann rekursiv implementiert die selbe Laufzeit wie DLs iterative Schleife. Ich wollte damit seiner Behauptung, die iterative Implementierung sei besser als...
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by JasonDX,
11. Jun 2010
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.
Es könnte schwierig...
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by JasonDX,
10. Jun 2010
Die rekursive Definition der Fibonacci-Folge ist trivial, und ihr Verlauf ist auf den ersten Blick halbwegs abschätzbar - im Gegensatz zur iterativen Implementierung; Dort ist eine Einschätzung der Funktion verhältnismäßig komplex.
Ja, sie ist leicht implementierbar und hat (rein theoretisch) konstante Laufzeit - aber ein grobes Genauigkeitsproblem.
Womit man dann zurück zum Punkt kommt,...
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by JasonDX,
10. Jun 2010
Seit meinem (unfreiwilligen) Zusammenstoß mit funktionalen Programmiersprachen im letzten Semester implementiere ich mehr und mehr rekursiv. Es ist einfach schöner und eleganter; Nur noch selten implementiere ich einen Algorithmus, den ich erst auf Papier erarbeitet habe, iterativ.
Tut es (fast) auch. Einzige Existenzberechtigung ist das minimum an dazwischenliegenden Schichten zwischen...
