Rekursion vs. Iteration

[Corpsman]

Guten Morgen,

Ich nutze Rekursion wie Iteration. die Wahl der Technik legt das zu lösende Problem fest. Wenn ich die Wahl habe nehme ich in der Regel die Iteration, oder Baue die Rekursion mittels einer "FILO" nach, zwecks sparen der rekursiven Aufrufe.

Bei sehr einfachen Rekursionen ist es wie idefix2 ja schon schrieb, eh so, dass der Compiler die Rekursion weg optimiert.

Ich Denke im Zweifel sollte man sich immer für die Lesbarkeit entscheiden. Und erst nach gründlicher Prüfung auf einen "optimierteren" Code umsteigen, die Frage die sich hier immer stellt : Rechtfertigt der Nutzen den Mehraufwand. In einem einfachen Programm wie n! sicher nicht. Bei den Fibonacci Zahlen hingegen ist die Iterative Lösung auf jeden Fall vor zu ziehen.

[idefix2]

Zitat:

Bei sehr einfachen Rekursionen ist es wie idefix2 ja schon schrieb, eh so, dass der Compiler die Rekursion weg optimiert.

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.

[Corpsman]

Zitat von idefix2:

Zitat:

Bei sehr einfachen Rekursionen ist es wie idefix2 ja schon schrieb, eh so, dass der Compiler die Rekursion weg optimiert.

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.

In meiner Compilerbau Vorlesung haben wir das zumindest durch genommen,d.h. theoretisch geht es. Ob es der Delphi Compiler allerdings macht, dass ist natürlich ungewiss. In den entsprechenden Manuals müsste dass aber stehen.

Zitat von QuickAndDirty:

Es gab mal irgend eine Formel wie man ein Rekursives Problem umstellen kann so das es Iterativ abgebildet wird...habe das irgendwann man an der uni gelernt...aber wieder vergessen

Das war das Umformen mittels FILO . Ich kanns zwar implementieren, wie es genau heist weis ich auch nicht *g*

[p80286]

Iteration / Rekursion ist wie
Wanderschuhe / Pumps.
Das eine praktisch (auch für geistige Dünnbrettbohrer wie mich zuverstehen), das andere knackig, elegant und nicht zu gebrauchen (auf das "einfache" Debugging wurde ja schon mehrfach hingewiesen).

Das mit dem Stacküberlauf ist mir allerdings seit seligen TP-Zeiten nicht mehr passiert.


Gruß
K-H

[MrSpock]

Natürlich kommt es auf das Problem an, aber ich liebe Rekursionen.

Sie sind elegant, kurz und m.E. leicht zu verstehen. Zugegeben: das sage ich jetzt. Ich kann mich noch gut an meine erste "Programmieren" Klausur an der Uni erinnern. Dort ging es darum ein Problem mittels Rekursion zu lösen. Das Programm war auf Papier niederzuschreiben (also nix mit mal schnell am PC testen). Es waren 12 Zeilen Code, die mich 45 Minuten Zeit gekostet haben. Heute schreibe ich Rekursionen in der Regel gleich hin (meistens sogar richtig ).

[negaH]

Ich meine das sollte vom verwendeten Algorithmus und damit Zielsetzung abhängig gemacht werden. Es gibt nur sehr wenige und schwache Begründungen warum man zB. einen mathematischen Algorithmus, der per Formel rekursiv formuliert wurde, in Software später iterativ zu implementieren. Erstens dient ja die Formel als Basis und wenn man 1 zu 1 diese als Implementierung in SW wieder findet so erhöht das enorm die Verständlichkeit. Zweitens sind rekursive Formeln/Algos meistens einfacher verständlich. Die Hauptvorteile einer iterativen Variante, wie Geschwindigkeit, Speicherverbrauch sind in meinen Augen heutzutage absolut vernachlässigenbar. In meiner langjährigen Praxis haben sich bei vielen Implementierungen diese "Vorteile" als wirklich nur mariginal herausgestellt. Wichtiger war es dann immer den benutzen Algorithmus zu optimieren oder einen besseren zu benutzen.

Meiner Meinung nach ist es also wenig sinnvoll die Kriterien Performance und Speicherverbrauch in den Vordergrund zu stellen. Wichtiger ist Verständlichkeit, Wartbarkeit und Flexibilität.

Gruß Hagen

PS: Gegenteilig betrachtet gibt es rekursiv formulierte Probleme die als iterative Variante wirklich sehr sehr schwer zu verstehen sind (und ich habe solche iterativen Monster schon öfters analysiert

[Delphi-Laie]

Zitat von negaH:

Ich meine das sollte vom verwendeten Algorithmus und damit Zielsetzung abhängig gemacht werden. Es gibt nur sehr wenige und schwache Begründungen warum man zB. einen mathematischen Algorithmus, der per Formel rekursiv formuliert wurde, in Software später iterativ zu implementieren.

Speicherverbrauch und Geschwindigkeit sind schwach?

Dann müßte die Assemblerprogrammierung erst recht ohne Existenzberechtigung dastehen!

Zitat von negaH:

Erstens dient ja die Formel als Basis und wenn man 1 zu 1 diese als Implementierung in SW wieder findet so erhöht das enorm die Verständlichkeit. Zweitens sind rekursive Formeln/Algos meistens einfacher verständlich.

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.

Zitat von negaH:

Die Hauptvorteile einer iterativen Variante, wie Geschwindigkeit, Speicherverbrauch sind in meinen Augen heutzutage absolut vernachlässigenbar.

Jedes (!) Windows beweist den Gegensatz: Windows macht nämlich praktisch jeden Computer sofort, früher oder später zur Schnecke. Manchmal habe ich sogar den Verdacht, daß absichtlich Bremsschleifen dorthinein implementiert wurden.

Zitat von negaH:

In meiner langjährigen Praxis haben sich bei vielen Implementierungen diese "Vorteile" als wirklich nur mariginal herausgestellt. Wichtiger war es dann immer den benutzen Algorithmus zu optimieren oder einen besseren zu benutzen.

Zu optimieren in welcher Hinsicht? Geschwindigkeit? Speicherverbrauch? Die wurden doch weiter oben schon als relativ unwichtig gebrandmarkt.

Zitat von negaH:

PS: Gegenteilig betrachtet gibt es rekursiv formulierte Probleme die als iterative Variante wirklich sehr sehr schwer zu verstehen sind (und ich habe solche iterativen Monster schon öfters analysiert

Könntest Du bitte Beispiele nennen?

[gammatester]

Zitat von negaH:

In meiner langjährigen Praxis haben sich bei vielen Implementierungen diese "Vorteile" als wirklich nur mariginal herausgestellt. Wichtiger war es dann immer den benutzen Algorithmus zu optimieren oder einen besseren zu benutzen.

Meiner Meinung nach ist es also wenig sinnvoll die Kriterien Performance und Speicherverbrauch in den Vordergrund zu stellen. Wichtiger ist Verständlichkeit, Wartbarkeit und Flexibilität.

Naja, ganz so einfach ist es ja auch nicht. Wenn man als (zweites Standardbeispiel neben Fakultät) die Fibonacci-Zahlen gemäß der rekursiven Definition fib(n) = fib(n-1)+fib(n-2) umsetzt:

Delphi-Quellcode:

function fib(n: int64): int64;
begin
  if n=0 then fib := 0
  else if n=1 then fib := 1
  else fib := fib(n-1)+fib(n-2);
end;

wird man für fib(90) viel Geduld brauchen. Die iterative Lösung ist für int64 praktisch instantan. Das es für sehr große Zahlen einen noch viel besseren Algo gibt, wissen einige. Die rekursive Variante ist jedoch bezüglich "Einfachheit, Verständlichkeit, Wartbarkeit und Flexibilität" nicht zu toppen, ist aber praktisch unbrauchbar.

[mkinzler]

Es ist aber auch eine Geschmacksache.

[QuickAndDirty]

Und ich hasse Rekursion...vor allem beim debuggen...es ist die Hölle
besonders scheiße finde ich unabsichtliche Rekursion...wo man eine Methode aufruft die über zig andere Methoden wieder sich selbst aufruft...

Lustig zu debuggen.


Es gab mal irgend eine Formel wie man ein Rekursives Problem umstellen kann so das es Iterativ abgebildet wird...habe das irgendwann man an der uni gelernt...aber wieder vergessen