-
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by Delphi-Laie,
21. Jun 2010
Letztlich arbeitet eine (jede?!) CPU sogar nur sequentiell. Iterationen sind ja letztlich auch nur ein „Trick“, dem Prozessor immer und immer wieder das (fast) gleiche unterzuschieben.
Iterationen dienen der einfachen - hierarchiegleichen bzw. horizontalen - Wiederholung von Befehlen.
Rekursionen dienen der etas komplexeren, weil auf verschiedenen Hierarchieebenen befindlichen bzw....
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by Delphi-Laie,
21. Jun 2010
Zumindest die, die in Internetamateurenzyklopädie sicher aus gutem Grundes als „iterative“ Rekursion bezeichnet wird.
Das ist die entscheidende Frage. Jede Iteration läßt sich als Rekursion darstellen, denn letztlich rufen - in gewisser Weise - sich Schleifen auch nur selbst immer wieder auf.
Doch ist jede Rekursion auch als Iteration abbildbar? Dazu fehlen mir die Kenntnisse. Ist das...
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by Delphi-Laie,
15. Jun 2010
Laufzeitverhalten schrieb ich.
Dann gehe mal einen rekursiven Algorithmus (im engeren Sinne, wie ich es ausführlich beschrieb), während er abläuft (also den Prozeß seines Ablaufes) durch: Die hierarchieniedrigsten Aufrufe sind die häufigsten! Konkret z.B. beim rekursiven Fibonacci: Fib(0) bzw. Fib(1) werden am häufigsten berechnet. Ziseliert man diesen Prozeß (graphisch), entsteht eine...
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by Delphi-Laie,
15. Jun 2010
Markus Kinzler....
So etwas weise ich zurück, und zwar deshalb, weil Du - obwohl Moderator - m.E. nicht neutral bist. Wo warst Du, als mich jemand absichtlich (?) und öffentlich in dieser Diskussion zu meinem Ungunsten fehlinterpretierte, was ich zudem leicht widerlegen konnte, und damit emotionale Spannung erzeugte?
Zurück zum Thema. Ich ließ mir absichtlich ein wenig Zeit für eine...
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by Delphi-Laie,
13. Jun 2010
Zunächst einmal heißt es „lies“ (oder heißt die inzwischen aus der Mode gekommen Dateibezeichnung „lesemich.txt“?). Auch sollte ein Forumsverantwortlicher sich mit solchen indiskutablen Aussagen besser zurückhalten. Für diesen Umgangston seitens des Forumsstabes gibt es nämlich schon ein anderes Delphi-Forum. Ich verstand zudem sehr wohl, daß man Iterationen auch über Rekursion (bzw. umgekehrt)...
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by Delphi-Laie,
12. Jun 2010
Ja.
Ich meinte doch ausdrücklich, ob es eine schnellere rekursive Lösung gibt. Die Verständlichkeit ist unberührt.
Der Vergleich hinkt m.E. etwas. Es lassen sich zum einen auch rekursive (und auch iterative) Algorithmen finden, die langsamer als Bubblesort sind (Trippelsort, Slowsort), zum anderen gibt es auch iterative Sortieralgorithmen, die von der Geschwindigkeit her dem...
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by Delphi-Laie,
12. Jun 2010
Natürlich. So pauschal eine solche Aussage ist, so falsch ist sie auch.
Mich würde in diesem Zusammenhang allerdings einmal interessieren, ob bei Problemlösungen, die sowohl iterativ als auch rekursiv möglich sind, es auch Fälle gibt, in denen die Rekursion hinsichtlich des Laufzeitverhaltens der Iteration substantiell (also vom Komplexitätsverhalten her) überlegen ist. Nachzuweisen, daß eine...
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by Delphi-Laie,
12. Jun 2010
Warum unsinnig? Sie orientiert sich lediglich an der rekursiven mathematischen Definition und dürfte wohl all' das, was zugunsten der Rekursion hier ins Felde geführt wurde, wie Übersichtlichkeit und Einfachheit und womöglich einen mathematischen Exaktheitsbeweis im Nacken, in vollem Umfange aufweisen.
Interessant ist - obwohl ich sie nicht gern zitiere - daß in der Wikipedia für die...
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by Delphi-Laie,
11. Jun 2010
Gern, und zwar ohne daß ich Sätze mehr verstümmele, als diese zu zitieren:
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by Delphi-Laie,
11. Jun 2010
In dieser Diskussion finden sich pauschale Äußerungen, daß rekursiv dem Iterativen ebenbürtig ist, und das ist so pauschal eben falsch. Nunmehr wird - von Dir - bei rekursiv zwischen „brauchbar“ und „untauglich implementiert“ unterschieden. Daß der Algorithmus als solcher selbst bzw. an sich ein schlechteres Laufzeitverhalten hat (haben kann), wird auch mit solchen Aussagen umschifft. Wie soll...
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by Delphi-Laie,
11. Jun 2010
Das ist durchaus möglich. Allerdings ist dieser Algorithmus - im Vergleich zur „vollrekursiven“ Variante - teilweise „entrekursiviert“ (Die, die Ihr Informatik studiert(et) - gibt es ein Verb dafür?) (worden). Die originale rekursive Definition der Fibonaccigliederberechnung findet sich dort jedenfalls nicht mehr. Wenn man einen vollrekursiven Algorithmus teilweise von der Rekursion befreit und...
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by Delphi-Laie,
11. Jun 2010
Nun mal halblang. Du kannst mich dafür verantwortlich machen, daß Du in meine Aussagen etwas hineindichtest und sie damit fehlinterpretierst. Erst recht steht es Dir nicht zu, für alle zu sprechen. Ich weiß genau, was ich schrieb und krame es extra noch mal für Dich hervor:
„Manchmal habe ich sogar den Verdacht, daß absichtlich Bremsschleifen dorthinein implementiert wurden.“
Dort steht...
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by Delphi-Laie,
11. Jun 2010
Mit Tatsachen läßt sich bekanntlich am schlechtesten diskutieren - nämlich gar nicht.
Deshalb friemelte ich für alle Klugheitsausscheider mal eben - so auf die Schnelle - ein kleines (natürlich Delphi-)Programm zusammen, das beide Algorithmen bei Fibonacci vergleicht. Ich hoffe, das das Hochladen desselben klappte.
Bei größeren Eingabewerten steigt die Berechnungszeit bei der Rekusrsion...
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by Delphi-Laie,
11. Jun 2010
Wenn einer 'was nicht sehen will.... Letzlich wiederholtest Du nur Deine Aussage und besitzt sogar noch die Stirn zu behaupten, ich hätte Deine Aussage untermauert, bleibst den Nachweis dieser abenteuerlichen Behauptung jedoch schuldig. Wenn iterativ und rekursiv wirklich nie einen Unterschied ausmachen, dann kann es an der Hardware ja erst recht kaum liegen.
Diese abgedroschene Floskel,...
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by Delphi-Laie,
11. Jun 2010
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...
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by Delphi-Laie,
11. Jun 2010
Ganz bestimmt nicht. Die Komplexität bzw. Effizienz von Algorithmen hat zunächst einmal überhaupt nichts mit ihrer Umsetzung zu tun.
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.
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by Delphi-Laie,
10. Jun 2010
Wo ist ein/der Widerspruch?
Ohne Rekursion - sogar ohne Iteration - kann man die Glieder der Fibonacci-Folge über Berechnungen mit der (Quadrat-)Wurzel aus 5 ermitteln. Diese Formel ist leicht zu implementieren bzw. aus dem Quellcode (nur wenige Anweisungen, deshalb leicht zu erfassen) leicht die Formel abzuleiten. Doch wie man aus dieser Gleichung die rekursive Berechnung der...
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by Delphi-Laie,
10. Jun 2010
Also, die Optimierung des Algorithmus' (möglich in mehrerlei Hinsicht) als eine Zielfunktion darf man hier demnach als unstrittig konstatieren.
Auch wenn die Rekursion vielleicht sogar in den meisten Fällen eine kurze und elegante Problem(lösungs)beschreibung liefert, so kann dennoch die Algorithmenoptimierung durchaus in einer Beseitigung der Rekursion zu suchen bzw. zu finden sein.
Es mag...
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by Delphi-Laie,
10. Jun 2010
Speicherverbrauch und Geschwindigkeit sind schwach?
Dann müßte die Assemblerprogrammierung erst recht ohne Existenzberechtigung dastehen!
Naja, auf Anhieb habe ich nur die Fakultät und die Fiboncci-Folge als Paradebeispiele. Sicher erklärt die (nichtiterative) Formel bei letzterem nicht das Wesen jener Folge, aber sie ist als solche deshalb nicht weniger verständlich.
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by Delphi-Laie,
8. Jun 2010
Über dieses Thema der - vermutlich - theoretischen Informatik gelangten bestimmt schon manche an ihren Doktorhut.
Tendenziell ist die Iteration schneller und von geringerem Speicherbedarf (s. Luckies Bemerkung), vor allem ohne Stackspeicherverbrauch. Mit Rekursion ist so manche Problemlösung dafür schneller und kürzer beschrieben - wenigstens auf dem Papier. Zudem kann ich mir vorstellen, daß...
