Rekursion vs. Iteration

[MaBuSE]

Hallo,
mich würde mal interessieren, ob Ihr in Euren Programmen ehr zur Rekursion oder zur Iteration neigt.
Es können ja schließlich alle Rekursionen durch Interationen ersetzt werden.

• Rekursion
  • Vorteile:
    • meist kurz (wenig Quellcode)
    • oft verständlicher als Iteration
  • Nachteile:
    • meist langsamer als Iteration in der Ausführung
    • es wird von Anfängern gern mal die Abbruchbedingung vergessen
• Iteration
  • Vorteile:
    • meist schneller als Rekursion in der Ausführung
  • Nachteile:
    • meist längerer Quellcode
    • oft weniger verständlich als Resursion

Für alle die mit dem Begriff Rekursion und Iteration nciht vertraut sind:

• Iteration
  http://de.wikipedia.org/wiki/Iterative_Programmierung
  
• Rekursion
  http://de.wikipedia.org/wiki/Rekursive_Programmierung

Beispiel:
Neue Anwendung -> Form1, ein TButton -> Button1 und ein TMemo -> Memo1
Methode rec ist recursiv (ruf sich also selbst wieder auf)
methode iter ist iterativ (in diesem Fall eine einfache For Schleife)

Delphi-Quellcode:

...
procedure TForm1.Button1Click(Sender: TObject);
var
  i: Integer;
begin
  Memo1.Lines.Clear;
  Memo1.Lines.Add('i   rec(i)   iter(i) ');
  Memo1.Lines.Add('--- -------- --------');
  for i := 0 to 10 do
  begin
    Memo1.Lines.Add(Format('%2d: %8d %8d', [i, rec(i), iter(i)]));
  end;
end;

function TForm1.iter(i: Integer): integer;
var
  j: Integer;
begin
  Result := 1;
  for j := 1 to i do
  begin
    Result := Result * j;
  end;
end;

function TForm1.rec(i: Integer): integer;
begin
  if i = 0 then Result := 1
           else Result := i * rec(i-1);
end;
...

Das Ergebnis:

Code:

i   rec(i)   iter(i) 
--- -------- --------
 0:        1        1
 1:        1        1
 2:        2        2
 3:        6        6
 4:       24       24
 5:      120      120
 6:      720      720
 7:     5040     5040
 8:    40320    40320
 9:   362880   362880
10:  3628800  3628800

Viele Grüße
MaBuSE

ps:Ich wollte schon immer mal als Erster in einem Forum schreiben

[freak4fun]

Meistens Iteration, weil es leichter zu verstehen ist.

[nahpets]

Hallo,

Zitat von MaBuSE:

Es können ja schließlich alle Rekursionen durch Interationen ersetzt werden.

Stimmt das?

Wie kann ich die Suche z. B. im Verzeichnisbaum durch eine Iteration abbilden?

Zur eigentlichen Frage:

Kommt drauf an, was leichter und verständlicher zu implementieren ist, wobei ich nur selten auf Aufgabenstellungen stoße, die rekursive lösbar sind. Das Meiste ist das Sammeln von Datenbankdaten und deren Ausgabe.

[Khabarakh]

Zitat von nahpets:

Stimmt das?

Wie kann ich die Suche z. B. im Verzeichnisbaum durch eine Iteration abbilden?

Ja, Rekursion lässt sich immer als Iteration + Stack umsetzen. Nicht zufällig heißt das Ding, auf dem die Variablen landen, gleich .

In deinem Beispiel: Das Ursprungsverzeichnis auf einen Stack werfen, solange dieser nicht leer ist, das oberste Element behandeln und alle Unterverzeichnisse hinzufügen.

Rekursionen sind wirklich wunderhübsch, aber da die wenigsten imperativen Sprachen Tail Call Optimization kennen, gibt es nur wenige Probleme (z.B. Quicksort), bei denen man keinen Stacküberlauf riskiert.

[himitsu]

Die Interative Lösung hat noch andere Vorteile
(gut, der Nachteil, daß Interativ meißt schieriger/umständlicher/unverständlicher zu implementieren ist, sei mal dahingestellt)

Vorteil, da man den Stack selber verwaltet, kann man auch mal ganz leicht aus der Funktion rausspringen und diese später erneut an selber Stelle weiter abarbeiten.

Im Fall von FindAllFiles wäre z.B. sowas möglich:

Delphi-Quellcode:

Suche := TSucheAlleDateien.Create('c:\', '*.*');
while Suche.NochWasDaFragezeichen and not SollAbgebrochenWerdenFragezeichen do
  WriteLn(Find.WasDennFragezeichen);
Suche.Free;

Wobei man hier die nächste Datei erst in NochWasDaFragezeichen suchen könnte.

PS: http://www.delphipraxis.net/142669-f...iterative.html

[Luckie]

Der Speicherverbrauch.

[s.h.a.r.k]

Es kommt vor allem auf die Datenstruktur drauf an, und wenn sich anbietet eine Rekursion zu nehmen, dann nutze ich diese auch. Aber egal ob Rekursion oder Iteration, es muss schon auch dokumentiert werden, was gemacht wird

[himitsu]

Zitat von Luckie:

Der Speicherverbrauch.

Ohne unnütze Stackframes sollte man bei Beiden doch etwa auf's Selbe rauskommen?

[Delphi-Laie]

Ü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ß die Rekursion als etwas anspruchsvoller, also akademisch eleganter empfunden wird.

Ursache beider sind Ähnlichkeiten und Wiederholungen im Programmablauf, und deren Vorwegnahme im Programmcode (in gewisser Weise ist ein Programm ein Ablaufplan für ein später laufendes Programm, besser, für die Menge seiner potentiell ablaufenden Programme) kann eben auf unterschiedliche Weise beschrieben werden.

Zitat von Khabarakh:

Zitat von nahpets:

Stimmt das?

Wie kann ich die Suche z. B. im Verzeichnisbaum durch eine Iteration abbilden?

Ja, Rekursion lässt sich immer als Iteration + Stack umsetzen. Nicht zufällig heißt das Ding, auf dem die Variablen landen, gleich .

Ist damit so eine Art „Pseudo-Entrekursionierung/-rekursivierung“ gemeint? So etwas lernte ich in Robert Sedgewicks Standardwälzer beim Quicksort kennen und implementierte es auch in mein Sortierkino. Im Prinzip wird die Stackbehandlung „zu Fuß“ nachgebildet. Grund ist, daß Quicksort einer der Algorithmen ist, die sich nicht (wenistens nicht zufriedenstellend) derekursionieren/-rekursivieren lassen. Auch bei hierarchischen bzw. Baumstrukturen mit beliebiger bzw. unbekannter Tiefe ist mir ein nichtrekursives, also iteratives Vorgehen nicht simpel einleuchtend (mag sein, daß es möglich ist). Allerdings gehöre ich zu dem - wohl übergroßen - Anteil der Forumsmitglieder, die nicht Informatik studierten.

Edit: Das neue Timeout ist eine Zumutung, Daniel, bitte tue etwas dagegen!

[angos]

Zitat von MaBuSE:

Hallo,
mich würde mal interessieren, ob Ihr in Euren Programmen ehr zur Rekursion oder zur Iteration neigt.

Hi,

da ich die Iteration meist als den lesbareren Quellcode ansehe nutze ich nur in Ausnahmefällen eine Rekursion.

Gruß
Ansgar