|
AW: Rekursion vs. Iteration
Ich verstehe die kleinliche Rechthaberdiskussion nicht, bei der man die Integrität von Diskussionsteilnehmern in Frage stellt.
Mein Bauch sagt mir zwar, das man so ziemlich jedes Verfahren sowohl rekursiv als auch iterativ formulieren kann. Aber wenn nicht: WTF. Ich bin und bleibe Anhänger der Rekursion und setze sie immer ein, wobei ich Tail-Recursion und hohe Verschachtelungstiefen vermeide. Natürlich schaue ich mir jede Lösung hinsichtlich ihres Big-Oh-Verhaltens kritisch an, und würde daher z.B. eine unsinnige Fibionacci-Implementierung, wie vom Gammatester süffisant vorgetragen, vermeiden. Wenn ich mir die rekursiven Lösungen zum Türme-Von-Hanoi-Problem anschaue, oder die Ermittlung von Permutationen, oder eine Lösung des N-Damen-Problems, dann verstehe ich nicht, wie man iterative Lösungen per se bevorzugen kann. Und wenn ich eine iterative Berechnung der Fakultät oder der Fibionacci-Folge sehe, verstehe ich auch nicht, wie man rekursive Lösungen per se bevorzugen kann. :-D |
AW: Rekursion vs. Iteration
Zitat:
Zitat:
Der - auch von mir nicht bezweifelte - tendenzielle Vorteil der Rekursion hinsichtlich Übersichtlichkeit und Wartbarkeit sehe ich bei solchen Quelltexten, die anscheinend die endrekursive Variante verkörpern, wie
Code:
oder
private uint fib(uint n)
{ if (n == 0) return 0; else return fib(n, 1, 0); } private uint fib(uint n, uint x, uint y) { if (n == 1) return x; else return fib(n - 1, x + y, x); }
Code:
leider nicht mehr gegeben: Da sich hier nicht an der rekursiven mathematischen Definition vollumfänglich orientiert wird, muß man sich in so etwas - egal, ob als ursprünglicher Programmierer oder später als Sichter des Quelltextes - auch erst einmal genau wie bei Iterationen hineindenken.
function Fibonacci_Rekursiv2(Index : Integer) : Int64;
function Fibonacci_Rekursiv_Help(f1,f2,n: Integer): Integer; begin if n = 0 then Result:=f1 else Result:=Fibonacci_Rekursiv_Help(f2,f1+f2,n-1); end; begin case Index of 1, 2 : Result := 1; else Result := Fibonacci_Rekursiv_Help(0,1,Index); end; end |
AW: Rekursion vs. Iteration
Zitat:
Die Tailrecursion ist Rekursion. Punkt. Sie sollte aber durch eine Schleife ersetzt werden, weil das einfach einfacher zu verstehen ist. Punkt. Das das nebenbei auch noch performanter ist, liegt an der Tatsache, das eine Schleife nun mal schneller ist. Hier ist naturgemäß eine Umformung in eine Iteration die richtige Wahl. Eine andere Technik der Umformung (rekursiv => iterativ), Bookkeeping eines Stacks vs. rekursivem Aufruf und Stack ist dagegen nicht notwendigerweise performanter. Ich habe vor einiger Zeit mal wieder ein iterstives mit einem rekursiven Quicksort verglichen: Da gibt es einfach keine relevanten Unterschiede mehr. Wer allerdings einen Floodfill rekursiv implementiert, muss sich nicht wundern, wenn die Performance in den Keller geht. Man muss einfach, wie bei allen Implementierungen, seinen gesunden Menschenverstand einsetzen, um die richtige Lösung zu finden. Dogmen á la "rekursiv ist eh zu langsam" sind hier nicht zielführend, übrigens genauso wenig wie "Eleganz ist alles". Vor lauter Performancegeilheit darf man auch nicht vergessen, das es fast immer völlig egal ist, ob eine Anwendung 5 oder 5.02 Minuten benötigt. Viel wichtiger ist es mittlerweile, das der Code klar und lesbar ist. Lesbarer Code ist wartbar. Wartbarer Code ist zukunftssicher. Und zukunftssicherer Code sichert das Geschäft. So einfach ist das. Jedenfalls für mich. Ich kann mit Aussagen, wie "Rekursion ist per se langsamer als Iteration" nichts anfangen. Denn es ist Quatsch. |
AW: Rekursion vs. Iteration
Zitat:
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 iterative einer (bestimmten) rekursiven Lösung überlegen ist, bedurfte es ja nur einer Folge, die schon seit dem späten Hochmittelalter (oder frühen Spätmittelalter) bekannt ist. |
AW: Rekursion vs. Iteration
Zitat:
Zitat:
Als Gegenbeispiel führe ich mal die Türme von Hanoi an:  http://de.wikipedia.org/wiki/Türme_v...er_AlgorithmusDie rekursive Implementierung ist deutlich besser verständlich als die iterative. Beide haben natürlich das gleiche exponentielle Laufzeitverhalten. Noch ein bereits genanntes Gegenbeispiel: Rekursiver Quicksort vs. iterativer Bubblesort. Sind ja beides Lösungen für das Sortierproblem - aber die rekursive Implementierung der Lösung ist deutlich schneller im Average Case ;) |
AW: Rekursion vs. Iteration
Zitat:
Zitat:
Zitat:
|
AW: Rekursion vs. Iteration
Moin,
Zitat:
Das
Delphi-Quellcode:
nicht das beste Laufzeitverhalten hat, das hast du ja demonstriert, aber es gibt rekursive Implementierungen die sind so gut wie die iterativen. Ob das nun die ursprüngliche mathematische Definition ist, ist doch irrelevant, ob die rekursive Implementierung gut ist.
fib(n) := fib(n - 1) + fib(n - 2)
Und warum muss der rekursive Algorithmus unbedingt schneller sein? Solange sie gleich schnell sind passt das doch? Weil dann ist eine rekursive Implementierung meistens besser lesbar. MfG Fabian |
AW: Rekursion vs. Iteration
Zitat:
Bei Fibonacci habe ich dir eine rekursive Implementierung mit gleicher Komplexität gezeigt, die du wegen der verringerten Verständlichkeit (zu recht) abgelehnt hast. (Fibonacci ist eben ein Problem, dass man am besten per iteration löst) Bei den Türmen von Hanoi habe ich dir gezeigt, dass rekursive Implementierungen bei gleicher Komplexität übersichtlicher sein können. Und du bestehst auf einer schnelleren Lösung ... schon die Entwicklung der iterativen Lösung die du jetzt nur auf Wikipedia angeguckt hast, hat wahrscheinlich Tage wenn nicht gar Wochen gebraucht, während die rekursive Variante schnell hingeschrieben ist. |
AW: Rekursion vs. Iteration
Zitat:
|
AW: Rekursion vs. Iteration
Zitat:
15 Beiträgen versucht klar zu machen... :wall: |
AW: Rekursion vs. Iteration
Zitat:
Zitat:
greetz Mike |
AW: Rekursion vs. Iteration
@Alzaimar
Zitat:
Das gilt zb. für die Hardware FPGA oder Papier eben nicht mehr. Dort existiert kein Overhead im Speicher und Performance beim Aufruf von Unterfunktionen weil sie durch die Synthese eliminiert werden oder einfach nicht vorhanden sind. Letzendlich sind es auch nicht "iterative" und/oder "rekursive" Verfahren. Sondern es ist ein und das selbe Verfahren das man schriftlich entweder iterativ oder rekursiv niederschreibt. Was am Ende in Hardware ankommt ist eine Frage der Compiler/Synthese und der Hardware selber. Betrachtet man also die Frage "rekursiv vs. iterativ" unabhängig von Hardware dann sind sie identisch in ihrer Komplexität, Big O. Bezieht man die Hardware und Compiler etc.pp. mit in die Fragestellung ein dann muß man auch diese als Faktor berücksichtigen. Und erst da wird man dann leichte Nachteile der Rekursion gegenüber der Iteration haben wenn es sich zb. um ASICs handelt aber eben nicht bei FPGAs/CPLDs oder Quantenrechnern. Dieser Overhead auf ASICs entsteht ausschließlich durch folgende Faktoren: - zusätzliche CPU Takte sind nötig bei Sprüngen - zusätzlicher Stack ist nötig zum Speichern der Rücksprungadresse und Einrichten des Stackframes der rekursiven Unterfunktion - zusätzliche CPU Takte sind nötig für diese Stackeinrichtung und Stackbereinigung - ein RET zum Aufrufer ist nötig Das sind alles nur Faktoren auf Grund der CPU Architektur die eben Sprünge benachteiligt zu Programmcode der ohne diese auskommt wie bei iterativen Umsetzungen. Als letztes kommt noch der Punkt hinzu das zb. der Delphi Compiler nicht über Funktionsrümpfe hinweg optimieren kann. Er wird also besser eine iterative Funktion optimieren können als deren rekursve Schreibweise. Das alles sind aber Punkte die man bei der generellen Bewertung "iterativ vs. rekursiv" aussen vor lassen muß. Und dann ergibt sich wieder das gewohnte mathematische Bild das beide äquvivalente Schreibweisen der selben Sache sind und nichts mehr. Wenn dem so ist wird nun auch logsich das man sich bei dieser Frage nur auf die Fragestellung: was ist verständlicher beziehen darf. Und das hängt letzendlich vom Algorithmus und der Zielsetzung ab. Bei bestimmten, wenigen Problemen ist die iterative Schreibweise einfacher zu verstehen, bei den meisten Problemen wird aber schon bei der Mathematik und deren Formel die rekusive Schreibweise bevorzugt da sie intuitiver und einfacher ist. Vernachlässigt man also mal den mariginalen Performance/Speicheroverhead der auf ASICs systembedingt einen Unterschied ausmacht dann ist in den meisten Fällen die rekursive Schreibweise die bessere Wahl. Nicht weil sie schneller sein könnte oder weniger Speicher verbraucht, das haben wir ja nun hinlänglich ausdiskutiert das dies nicht der Fall sein kann und darf, sondern weil sie angemessener ist und verständlicher. Gruß Hagen |
AW: Rekursion vs. Iteration
Zitat:
Gruß Hagen |
AW: Rekursion vs. Iteration
Zitat:
Ich dachte eigentlich, daß ich mich klar genug ausdrückte: Einer bestimmten rekursiven Lösung. Es gibt auch eine andere, für die das nicht gilt. Ich werde Dir mal ein Gleichnis, das mit Programmierung nun überhaupt nichts zu tun hat, offenbaren: In meiner Schulklasse stritt sich mal ein Schüler mit einer Lehrerin, ob man ein Pflänzlein nur in einen größeren Blumentopf umpflanzt oder ob es auch in einen der gleichen Größe möglich bzw. sinnvoll ist. Die Lehrerin meinte, ein größerer sei nicht zwangsläufig, der Schüler schon. Schon damals spürte ich und auch heute bin ich noch der Meinung, daß jeder auf seine Weise recht hatte. Und so etwa kommt mir das mit den iterativen Rekursionen wenigstens bei dem hier so strapazierten Beispiel der Fibonacci-Berechnung auch vor: Natürlich kann man auch eine Rekursion dort hineinwürgen, wenn man denn unbedingt eine haben möchte, weil man sie so sehr mag, aber die eingangs so hochgelobten Vorteile wie Übersichtlichkeit, Wartbarkeit, geringeres Fehlerrisiko usw. bleiben dabei nach meiner Einschätzung voll auf der Strecke, sie sind jedenfalls nicht offensichtlich besser als bei der Iteration. Dafür stimmt aber das Laufzeitverhalten. Beides ist anscheinend wenigstens an diesem Beispiel nicht unter einen Hut zu bringen (weshalb ich die Pauschalität weiterhin negiere). Welchen Vorteil nun eine solche Rekursion gegenüber der Iteration hat, weiß ich immer noch nicht, aber ich möchte es nunmehr auch nicht mehr wissen. |
AW: Rekursion vs. Iteration
Zitat:
Zitat:
Zitat:
Zitat:
Zitat:
|
AW: Rekursion vs. Iteration
Da bist du nunmal anderer Meinung wie wir. Wenn hier einer eine Behauptung aufstellt ohe diese wirklich zu belegen, andere Antworten ignoriert, andere diskussionsteilnehmer beleidigt, dann ist es durchaus unsere Aufgabe ihn darauf hinzuweisen!
|
AW: Rekursion vs. Iteration
Zitat:
Zitat:
Zitat:
Zitat:
greetz Mike |
AW: Rekursion vs. Iteration
Zitat:
Hier wurde wohl nicht als "Forenverantwortlicher" gesprochen. Auch ist eine Diskussion über die richtige Schreibweise absolut unnötig. Deine Versuche jemandem ein schlechtes Verhalten im Forum unterzuschieben wurden schon bemerkt. Glube mir; es funktioniert hier ganz sicher nicht! Wenn hier nur noch persönlich Anfeindungen vorgetragen werden werden wir im Team beraten und dann denn Thread schliessen. P.S.: aus der englischen Word readme auf das richtige deutsche Wort zu schliessen zeigt sehr schön wie in diesem Thread argumentiert wird :roll: |
AW: Rekursion vs. Iteration
Markus Kinzler....
Zitat:
Zurück zum Thema. Ich ließ mir absichtlich ein wenig Zeit für eine erneute Antwort. In dieser Diskussion wurde m.E. teilweise sogar erheblich aneinander vorbeigeredet. Richtig ist, rein formal und von der Definition her, daß Rekursion dadurch charakterisiert ist, daß sich Programmteile (immer Unterprogramme?) (ggf. wiederholt) selbst aufrufen. Rekursion und Iteration kann man in bestimmter Weise aufeinander abbilden (es gibt sozusagen eine Schnittmenge). Die folgliche Kongruenz, ja fast schon Äquivalenz von Rekursion und Iteration führe ich zu folgendem absurden Höhepunkt:
Delphi-Quellcode:
versus
procedure rekursion;
begin rekursion end
Delphi-Quellcode:
Gibt es einen substantiellen Unterschied zwischen beiden Programmteilen, insbesondere hinsichtlich ihres Laufverhaltens? Anscheinend nein, denn beides sind Endlosschleifen (abgesehen davon, daß erstere den Stack schnell überlaufen läßt). Zudem ruft süffisanterweise sich im 2. Codeschnipsel auch die Schleife selbst immer wieder auf, es ist also auch sich selbst (immer wieder) aufrufender Code!
repeat
until false Ist es also das, was der Originalposter wohl gemeint haben mag, als er Rekursion und Iteration gegeneinander antreten ließ? Ganz sicher und offensichtlich nicht, denn damit wäre eine solche Gegenüberstellung überflüssig. Was ich in dieser Diskussion bisher von keinem Diskussionteilnehmer las, werfe ich jetzt deshalb hier ein: Rekursion ist eine selbstähnliche Struktur, und weil wir im Bereich der Informatik sind, eine selbstähnliche Algorithmen-/Programmablaufstruktur (das ist nicht identisch)! Das Wesen der Selbstähnlichkeit besteht darin, daß sich etwas selbst in gleicher oder wenigstens ähnlicher Gestalt selbst enthält. Nicht notwendig ist, daß die Teile erster Subordnung mehrmals vorhanden sind. Doch die Selbstähnlichkeit entfaltet erst ihre volle Pracht, ihr volles Wesen, wenn das gegeben oder zumindest möglich ist. Deshalb folgende Unterscheidungen: 1. Jedes Element enthält sein eigenes Abbild in der jeweils 1. Subebene nur einmal. So etwas ist z.B. bei der rekursiven Fakultät oder - im materiellen Bereich - bei den russischen Puppen namens Matrjoschka der Fall. Ich bleibe dabei, daß eine solche Rekursion nur eine „Lightversion“ ist, da sie letztlich mit der Iteration konformläuft. 2. Die Anzahl der Elemente (=Subprozesse) kann größer als 1 sein, so z.B. in Bäumen (und so auch in hierarchischen Dateisystemen). 3. Die Anzahl der Elemente (=Subprozesse) ist sicher größer als 1, so z.B. bei der rekursiven Fibonacciglied(er)berechnung. Erst in den Fällen 2 und 3 entfaltet die Rekursion ihr wahres Wesen: Sie ist elegant zu beschreiben (bzw. ist eine elgante Methode, Probleme zu lösen bzw. Problemlösungen darzustellen) und zu implementieren und führt zu kurzen, sicher auch gut wartbaren Quelltexten. Das Laufzeitverhalten ist dagegen eher mau, denn diese Baumstruktur des Prorgrammablaufes beim Aufrufen der rekursiv aufgerufenen Unterprogramme x. Ordnung führen mit ziemlicher Sicherheit zu mindestens exponentiellem Laufzeitverhalten (bei der Fakultät z.B. sogar zu hyperexponentiellem Wachstum). Wollte man solche rekursiven Algorithem in adäquate iterative transformieren, so ist das entweder unmöglich (?), sehr aufwendig (wie es hier jemand bezüglich Fibonacci andeutete) oder nur unbefriedigend (s. Quicksort, falls R. Sedgewicks Aussage immer noch aktuell ist) möglich. Ich hoffe, daß ich das Eingangsthema nunmehr wieder so aufgriff, wie es vermutlich (?) gemeint war/ist, und auch, daß mein Standpunkt nunmehr nachvollziehbarer ist. |
AW: Rekursion vs. Iteration
Zitat:
Zitat:
|
AW: Rekursion vs. Iteration
Zitat:
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 Baumstruktur. Und die Anzahl der Elemente von Bäumen ist - soweit ich weiß - exponentiell. Edit: So allgemein gilt das doch nicht. Beim Quicksort ist das Laufzeitverhalten viel günstiger (logarithmisch), allerdings gibt es dort keine Mehrfachaufrufe: Was sortiert ist, wird nie wieder vom Algorithmus berührt (vielleicht ist das schon der Grund für die gute Komplexität?!), im Gegensatz zu den vielen Mehrfachberechnungen bei z.B. dem rekursiven Fibonacci. Das mehrmalige (konkret immer zweifache) Aufrufen von hierarchiegleichen Subprozessen (wie im Vorbeitrag ausgeführt) ist aber auch hier gegeben. |
AW: Rekursion vs. Iteration
Zitat:
Zitat:
Zitat:
Zitat:
Optimiert man die Algorithmen, so erhält man neue Berechnungsmethoden, und ein (hoffentlich) besseres Laufzeitverhalten. Aber es gelten immernoch die gleichen Bedingungen: Gibt es einen Algorithmus, der die n-te Fibonaccizahl in t(n) berechnet, so gibt es sowohl eine iterative, als auch eine rekursive Implementierung, die in Theta(t(n)) läuft. Zitat:
Zitat:
Zitat:
Was mir bisher eigentlich immer aufgefallen ist: Wenn ich mit Leuten über Rekursion ect. diskutiert habe, so waren das fast immer Leute, welche sich in erster Linie mit iterativen Programmiersprachen befasst haben. Vor 2 Jahren war ich rekursiven Implmentierungen zwar nicht abgeneigt, habe aber nur einen sehr scheuen und vorsichtigen Blick dahingewagt, immer im Hinterkopf, dass mir der dahinterliegende Code meinen Stack zumüllt. Beginnt man, sich (gezwungenermaßen *g*) damit ordentlich außeinanderzusetzen, so lernt man damit umzugehen, und die Vorzüge kennenzulernen. Menschen, die die Ideen bspw. hinter Haskell, OCaml oder Lisp verstanden haben, musste ich noch nie von den Vorteilen von Rekursionen überzeugen - nur jene, die sich bisher noch nicht wirklich damit außeinandergesetzt haben. greetz Mike |
AW: Rekursion vs. Iteration
Zitat:
Zitat:
Doch ist jede Rekursion auch als Iteration abbildbar? Dazu fehlen mir die Kenntnisse. Ist das schon bewiesen worden? In Robert Sedgewicks Standardwerk z.B. stand zur Quicksort, daß sich das nur unbefriedigend als Iteration darstellen/umsetzen läßt. Während der Implementation wurde mir rasch klar, daß mit der dort vorgestellten Quelltext letztlich nur die Stackhandhabung emuliert/simuliert wird, es also eine verkappte Rekursion ist. Sollte die letzte Frage tatsächlich bejaht werden können, bliebe auf jeden Fall der Vorteil der kurzen, übersichtlichen Problem(lösungs)beschreibung sowie der Quelltexte mit gleichen Eigenschaften, zudem gut wart- und portierbarer Quelltexte. Edit: Weiter oben schriebst Du, daß es laut „theoretischen Beweisen“ (Anmerkung: Derlei Beweise sind immer theoretisch) möglich sei. Das überlas ich zunächst. |
AW: Rekursion vs. Iteration
Ich habe auf die Schnelle keine Quelle gefunden, die es explizit auf Iteration zurückführt, aber es gibt Funktionen, die insbesondere im Compilerbau Kopfschmerzen machen, nämlich nicht-primitiv-rekursive Funktionen (Ackermannfunktion, Busy Beaver, Sudanfunktion, etc.).
Ich meine mich zu erinnern, dass man die nicht einfach auf eine iterative Variante zurückführen kann. |
AW: Rekursion vs. Iteration
Zitat:
Zitat:
Zitat:
Zitat:
Was den genannten Busy Beaver betrifft: Der ist gar nicht berechenbar, somit gibts weder eine iterative, noch ne rekursive Beschreibung dieser Funktion. greetz Mike |
AW: Rekursion vs. Iteration
Zitat:
Iterationen dienen der einfachen - hierarchiegleichen bzw. horizontalen - Wiederholung von Befehlen. Rekursionen dienen der etas komplexeren, weil auf verschiedenen Hierarchieebenen befindlichen bzw. ablaufenden Wiederholung von Befehlen, sie sind sozusagen eine vertikale Iteration. |
AW: Rekursion vs. Iteration
Wobei der Mechanismus der Rekursion fest in den Prozessor verankert ist ( Stack)
|
AW: Rekursion vs. Iteration
Zitat:
Ergo: aus Sicht "Rekurson vs. Iteration", als Schreibweise eines Algorithmus in einer Programmiersprache, kann eine CPU diesen sehr wohl sequentiell wie eben auch nicht-sequentiell abarbeiten. Beispiel: ein Algorithmus der auf der Boolschen Algebra basiert. Formal schreibt man diesen als Rekursive Formel und programmiert diesen auch exakt so in einem FPGA, in rekursiver Schreibweise. Die Synthese=Compiler, zerlegt diese Formel mit Hilfe der Boolschen Algebra über Matrizen in vollständig definiert Boolsche Ausdrücke. Daraus entsteht dann eine Verschaltung von elektronischen Gattern innerhalb des FPGAs. Man beschreibt also rekursiv das Verhalten einer Hardware. Obwohl also das Problem rekursiv formuliert wurde arbeitet die Elektronik im Zielsystem alles in parallel ab. Damit exitieren also keine Sprungbefehle, keine einzeln nacheinander abzuarbeitenden Befehlssequenzen und somit auch kein Stackframe und finally somit keine Benachteiligung in der Peformance und Resourcen der Schreibweisen "rekursiv vs. iterativ" eines Algos. Gruß Hagen |
AW: Rekursion vs. Iteration
Zitat:
Zitat:
|
AW: Rekursion vs. Iteration
Code:
Oben sieht man zwei Funktionen in VHDL, erstere ist rekusiv die zweite nutzt eine Schleife. Beide beschreiben ein Verhalten einer späteren Hardware.function XorVectorBits(Bits: std_logic_vector, Index: integer) return std_logic; variable Result: std_logic; begin Result := Bits(Index); if Index < Bits'High then Result := Result xor XorVetorBits(Bits, Index +1); end if; return Result; end function; function XorVextorBits(Bits: std_logic_vector) return std_logic; variable Result: std_logic; Index: Intger; begin Result := '0'; for Index in Bits'Range loop Result := Result xor Bits(Index); end loop; return Result; end function; Das Signal Bits stellt man sich zb. wie ein Datenbus vor der aus zb. 16 Datenleitungen besteht. Die Boolsche Funktion lautet in Worten: Verknüpfe alle Datenleitungen in Bits per XOR und gebe das Resultat, ein Bit, zurück. Beides wird bei der Synthese in Hardware exakt identische Resultate erzeugen. Nämlich ein XOR Gatter mit Bits'Range Inputs und einem Output. Ok, es dürfte klar sein das das ein sehr enfaches Beispiel ist und hier der Vorteil in der formalen Schreibweise einer Rekursion noch nicht zum tragen kommt. Gruß Hagen |
AW: Rekursion vs. Iteration
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.
|
AW: Rekursion vs. Iteration
Denke mal drüber nach warum ich in diesem Thread immer wieder betone das das nur eine Form einer Schreibweise ist und eben nicht direkt im Zusammenhang mit irgendwas Realem, wie eben Hardware, steht.
Rekursiv vs. Iterativ ist eine Frage der Schreibweise eines Algorithmus. Es ist nicht der Algorithmus selber noch dessen praktische Realisierung in Hardware. Man muß immer strikt abstrahieren und eine Frage, je nach gewünschter Sichtweise, beantworten. Bei "Rekursv vs. Iterativ" gilt erstmal das es da keinen Unterschied geben kann in der Performance und Speicherverbrauch. Erst wenn man die benutzte Hardware oder Softwaretools berücksichtig ändert sich die Antwort, bzw. erst dann macht es Sinn den Speicherverbrauch/Performance als Entscheidungskriterium heran zu ziehen. Aber..., dann bewertet man nicht mehr "Rekursiv vs. Iterartiv" sondern defakto die Fähigkeiten der btrachteten Softwaretools und Hardware, wie sie die unterschiedlichen Schreibweisen eines Algorithmus umzusetzen in der Lage sind. Wer also behauptet: Rekursiv sei oft langsammer als Iterativ in der Performance oder eben mehr Speicher verbraucht auf Grund eines notwendigen Stackframes, der bewertet einen ASIC als Hardware, und eben nicht mehr objektiv zwei Schreibweisen eines Algos. Gruß Hagen |
| Alle Zeitangaben in WEZ +1. Es ist jetzt 20:43 Uhr. |
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz