-
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by idefix2,
21. Jun 2010
Ich muss zugeben, dass mich das verblüfft. Ich hätte nicht geglaubt, dass es im wirklichen Leben tatsächlich Systeme gibt, die derartige rekurive Strukturen als Eingabe hernehmen und die Rekursion in parallel arbeitende Harware auflösen.
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by idefix2,
21. Jun 2010
Also darunter kann ich mir überhaupt nichts vorstellen. Könntest Du mit einem Beispiel illustrieren, was du meinst?
Der Hardwarestack wird von rekursiven Prozedure verwendet, ebenso wie von nicht rekursiven Prozeduren. Der Stack selbst hat mit Rekursion nichts zu tun, sondern nur mit Prozeduraufrufen. Deshalb brauchen natürlich auch rekursive Prozeduren einen Stack.
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by idefix2,
11. Jun 2010
Was soll das heissen? rekursiv bedeutet doch nicht, dass man bereits vorhandene Ergebnisse ignorieren und bereits erfolgte Rechenschritte jedesmal von neuem machen muss.
Die Berechnung erfolgt in der rekursiven Variante 100% rekursiv, aber selbstverständlich wird eine vernünftige Implementierung JEDES Algorithmus auf bereits vorhandene Ergebnisse zurückgreifen und die nicht neuerlich berechnen,...
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by idefix2,
11. Jun 2010
Wie ich in meinem Post 58 geschrieben habe - eine schlechte Implementierung kann für schlechte Performance sorgen, auch bei iterativen Verfahren. Einen untauglich implementierten rekursiven algorithmus mit einem brauchbar implementierten itetrativen Algorithmus zu vergleichen, beweist gar nichts.
Es kommt auch bei iterativen Verfahren vor, dass man rechenaufwändige Zwischenergebnisse später...
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by idefix2,
11. Jun 2010
@ jfheins:
Jetzt erinnere ich mich, über die Transformation bin ich in meinem Studium auch einmal gestolpert, habs in der Zwischenzeit wieder vergessen. Ist ein sehr eleganter rekursiver Ansatz.
Fairerweise muss man aber sagen, dass es doch ein ganz anderer Algorithmus ist, als der in der iterativen Variante verwendete. Vor allem aber erfordert er sehr langes Nachdenken, um...
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by idefix2,
11. Jun 2010
Widerlegt wurde nichts dergleichen, sondern es wurde nur bewiesen, dass eine schlechte Implementierung eines Algorithmus katastrophale Folgen auf die Performance haben kann - und das gilt für rekursive ebenso wie für iterative Verfahren.
Ich habe die Fibonacci-Folge rekursiv und iterativ für die Zahlen 10,20... bis 90 berechnet und ausgegeben (92 ist die grösste Zahl, für die die...
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by idefix2,
10. Jun 2010
Viel wird ja heute wirklich nicht mehr in Assembler programmiert - Sinnvoll ist das wirklich nur mehr bei sehr wenig oft durchlaufenem extrem zeitkritischem Code. Ungeschickte Umsetzung des Algorithmus ist meistens eine wesentlich schlimmere Tempobremse als die im Vergleich zu Assembler geringere Effizienz des Compiler-generierten Codes. Und auch der Overhead, der durch Rekursionen entsteht, ist...
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by idefix2,
10. Jun 2010
Macht das der Compiler wirklich? Ich habe eigentlich geschrieben, dass ich in so einem Fall die Iteration verwenden würde, das heisst, dass ich quasi die Rekursion selbst manuell wegoptimieren würde.
-
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by idefix2,
9. Jun 2010
Es kommt wohl auf die Problemstellung an. Oft ist der iterative Ansatz nicht mit nennenswertem Mehraufwand verbunden, dann zahlt sich eine rekursive Konstruktion nicht aus. Beispielsweise würde ich es als Unfug bezeichnen, in einem "echten" Programm n! rekursiv zu berechnen (das ist nicht als Kritik am obigen Beispiel zu verstehen, weil zur Illustration der Rekursion eignet sich das Beispiel...