AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren

Rekursion vs. Iteration

Ein Thema von MaBuSE · begonnen am 8. Jun 2010 · letzter Beitrag vom 21. Jun 2010
Antwort Antwort
Seite 9 von 12   « Erste     789 1011     Letzte » 
alzaimar
(Moderator)

Registriert seit: 6. Mai 2005
Ort: Berlin
4.956 Beiträge
 
Delphi 2007 Enterprise
 
#81

AW: Rekursion vs. Iteration

  Alt 12. Jun 2010, 16:40
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.
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat
Delphi-Laie

Registriert seit: 25. Nov 2005
1.474 Beiträge
 
Delphi 10.1 Berlin Starter
 
#82

AW: Rekursion vs. Iteration

  Alt 12. Jun 2010, 17:17
eine unsinnige Fibionacci-Implementierung, wie vom Gammatester süffisant vorgetragen, vermeiden.
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.

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.
Interessant ist - obwohl ich sie nicht gern zitiere - daß in der Wikipedia für die Endrekursion auch das Synonym „iterativ rekursiv“ benutzt wird. Sie scheint ein merkwürdiges Hybrid-/Übergangswesen zwischen der „klassischen“ / „echten“ Rekursion und der Iteration zu sein. Wer das eine will, muß das andere mögen. Rekursion (teilweise) abzuspecken, führt letztlich (teilweise) wieder zu der hier anscheinend von vielen verpönten Iteration. Doch taugt eine „Rekursion light“ keinesfalls als Nachweis dafür, daß sie vom Laufzeitverhalten her generell mit der Iteration mithalten kann.

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:
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);
        }
oder

Code:
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
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.

Geändert von Delphi-Laie (12. Jun 2010 um 18:14 Uhr)
  Mit Zitat antworten Zitat
alzaimar
(Moderator)

Registriert seit: 6. Mai 2005
Ort: Berlin
4.956 Beiträge
 
Delphi 2007 Enterprise
 
#83

AW: Rekursion vs. Iteration

  Alt 12. Jun 2010, 17:58
Doch taugt eine „Rekursion light“ keinesfalls als Nachweis dafür, daß sie vom Laufzeitverhalten her generell mit der Iteration mithalten kann.
Deine Gedankengänge sind für mich nicht nachvollziehbar. Du stehst zudem in deinem Bestreben, Äpfel generell über Birnen zu stellen, ziemlich allein. Erstens gibt es Birnenliebhaber und zweites faule Äpfel. Das haut also nicht hin.

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.
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat
Delphi-Laie

Registriert seit: 25. Nov 2005
1.474 Beiträge
 
Delphi 10.1 Berlin Starter
 
#84

AW: Rekursion vs. Iteration

  Alt 12. Jun 2010, 18:13
Ich kann mit Aussagen, wie "Rekursion ist per se langsamer als Iteration" nichts anfangen. Denn es ist Quatsch.
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 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.

Geändert von Delphi-Laie (12. Jun 2010 um 18:15 Uhr)
  Mit Zitat antworten Zitat
Benutzerbild von jfheins
jfheins

Registriert seit: 10. Jun 2004
Ort: Garching (TUM)
4.579 Beiträge
 
#85

AW: Rekursion vs. Iteration

  Alt 12. Jun 2010, 18:32
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.
Ist unmöglich, da das Komplexitätsverhalten vom Algorithmus (also der Art der Problemlösung) und nicht von der Implementierung des Algorithmus (rekursiv/iterativ) abhängt. Du meinst schon das mit der Groß-O-Notation, oder? Denn ein rekursiver Quicksort und ein iterativer Quicksort haben beide eine Laufzeit von n*log(n) im Schnitt.

Zitat:
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.
Das "nachzuweisen" ist trivial.

Als Gegenbeispiel führe ich mal die Türme von Hanoi an: http://de.wikipedia.org/wiki/Türme_v...er_Algorithmus
Die 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

Geändert von jfheins (12. Jun 2010 um 18:35 Uhr)
  Mit Zitat antworten Zitat
Delphi-Laie

Registriert seit: 25. Nov 2005
1.474 Beiträge
 
Delphi 10.1 Berlin Starter
 
#86

AW: Rekursion vs. Iteration

  Alt 12. Jun 2010, 18:57
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.
Ist unmöglich, da das Komplexitätsverhalten vom Algorithmus (also der Art der Problemlösung) und nicht von der Implementierung des Algorithmus (rekursiv/iterativ) abhängt. Du meinst schon das mit der Groß-O-Notation, oder?
Ja.

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.
Das "nachzuweisen" ist trivial.

Als Gegenbeispiel führe ich mal die Türme von Hanoi an: http://de.wikipedia.org/wiki/Türme_v...er_Algorithmus
Die rekursive Implementierung ist deutlich besser verständlich als die iterative. Beide haben natürlich das gleiche exponentielle Laufzeitverhalten.
Ich meinte doch ausdrücklich, ob es eine schnellere rekursive Lösung gibt. Die Verständlichkeit ist unberührt.

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
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 Quicksort wahrscheinlich mindestens ebenbürtig sind.
  Mit Zitat antworten Zitat
Benutzerbild von xZise
xZise

Registriert seit: 3. Mär 2006
Ort: Waldbronn
4.303 Beiträge
 
Delphi 2009 Professional
 
#87

AW: Rekursion vs. Iteration

  Alt 12. Jun 2010, 19:05
Moin,
[...]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 Quicksort wahrscheinlich mindestens ebenbürtig sind.
Dann fass dich bitte selber an die Nase: Du kannst einen schlechten rekursiv implementierten Algorithmus für die Fibonacci-Folge nicht mit einen optimierten iterativen Algorithmus vergleichen.

Das fib(n) := fib(n - 1) + fib(n - 2) 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.

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
Fabian
Eigentlich hat MS Windows ab Vista den Hang zur Selbstzerstörung abgewöhnt – mkinzler
  Mit Zitat antworten Zitat
Benutzerbild von jfheins
jfheins

Registriert seit: 10. Jun 2004
Ort: Garching (TUM)
4.579 Beiträge
 
#88

AW: Rekursion vs. Iteration

  Alt 12. Jun 2010, 19:12
Ich meinte doch ausdrücklich, ob es eine schnellere rekursive Lösung gibt. Die Verständlichkeit ist unberührt.
Wir drehen uns im Kreis

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.
  Mit Zitat antworten Zitat
mkinzler
(Moderator)

Registriert seit: 9. Dez 2005
Ort: Heilbronn
39.851 Beiträge
 
Delphi 11 Alexandria
 
#89

AW: Rekursion vs. Iteration

  Alt 12. Jun 2010, 20:06
Zitat:
Wir drehen uns im Kreis
Wir sind sozusagen Derwische
Markus Kinzler
  Mit Zitat antworten Zitat
Benutzerbild von Mithrandir
Mithrandir
(CodeLib-Manager)

Registriert seit: 27. Nov 2008
Ort: Delmenhorst
2.379 Beiträge
 
#90

AW: Rekursion vs. Iteration

  Alt 12. Jun 2010, 21:01
Wir drehen uns im Kreis
Das hab ich euch schon vor 15 Beiträgen versucht klar zu machen...
米斯蘭迪爾
"In einer Zeit universellen Betruges wird das Aussprechen der Wahrheit zu einem revolutionären Akt." -- 1984, George Orwell
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 07:27 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