Wann wird Rekursion verwendet und warum?

Doc.Snuggles

Vielen Dank für die Hilfe. Genau so etwas hab ich mir gewünscht.
Empfehlungen von erfahrenen Programmierern und eigene Meinungen,
wann ihr rekursiv programmieren würdet.

@Blue-Tiger
Danke, dann würde das bedeuten, dass du nur bei Nummer 3) rekursiv programmieren würdest.
Bei 1) und 4) auf jeden Fall nicht. Und bei Beispiel 2) und 5),
würdest du hier eher rekursiv oder eher iterativ empfehlen, und warum???

@groovemaster
Danke, und du würdest bei keinem der 5 Beispiele rekursiv programmieren?

1) Die schrittweise Steuerung eines fest vorgegebenen Produktionsablaufs

2) Suchprobleme, beispielsweise die Suche nach einem Begriff im Glossar
eines elektronischen Dokuments oder nach einem Namen in einem elektronisch
aufbereiteten Telefonbuch

3) Die Ermittlung einer zulässigen Belegung der Variablen eines
Gleichungssystems mit mehr unbekannten Variablen als Gleichungen

4) Ansteuerung einer Messsonde sowie Klassifikation und Abspeicherung
der Messdaten auf Datei

5) Sortierung von Messdaten.

Am besten sollte man immer versuchen auf Rekursion zu verzichten. Dann hat man auch nicht das Problem von Stackoverflows, wenn die Rekursion zu tief wird.

Blue-Tiger

Doc.Snuggles schrieb:

@Blue-Tiger
Danke, dann würde das bedeuten, dass du nur bei Nummer 3) rekursiv programmieren würdest.
Bei 1) und 4) auf jeden Fall nicht. Und bei Beispiel 2) und 5),
würdest du hier eher rekursiv oder eher iterativ empfehlen, und warum???

Deine Probleme sind etwas allgemein gestellt. Fuer Nummer 3 wuerd ich mich wahrscheinlich nach einem guten Algorithmus umsehen, und das dann so machen wie vorgegeben

1 und 4 benoetigen keine Rekursion. Bei 2 wuerd ich nicht rekursiv programmieren. Wenn ich eine geordnete Liste durchsuchen muss, wuerd ich eine iterative binaere Suche verwenden, wenn sie ungeordnet ist einfach durch die einzelnen Elemente durchiterieren.
Fuer Beispiel 5 wuerd ich vermutlich Quicksort verwenden, und der verwendet Rekursion. Ich wuerd den aber nicht selbst ausprogrammieren, dafuer gibts die Standardbibliothek

Mit der Zeit wirst du lernen, wann du lieber Rekursion verwendest und wann nicht. Das kommt mit der Erfahrung, das kann dir auch niemand in einem Thread-Post abnehmen

ferschieben in RudP

Foren-Administrator schrieb:

ferschieben in RudP

Die Frage ob ich das Thema nach RudP verschieben soll habe ich mir auch schon gestellt. Bisher habe ich mich (offensichtlich) für einen Verbleib hier entschieden, da dort der Fokus auf C verloren gehen würde, und der (sinnvolle) Einsatz von Rekursion ja durchaus von der verwendeten Sprache abhängt. Denken wir z.B. an die ganzen Funktionalen.

BorisDieKlinge

zudem ist rekursion auch schwerer zu debuggen:)

BorisDieKlinge schrieb:

zudem ist rekursion auch schwerer zu debuggen:)

wie kommste denn darauf? oder verwechselst du rekursion mit inline-funktionen?

Bashar

Rekursion muss man dafür nicht so oft debuggen, weil es öfter beim ersten Versuch schon hinhaut

groovemaster

Doc.Snuggles schrieb:

@groovemaster
Danke, und du würdest bei keinem der 5 Beispiele rekursiv programmieren?

Grundsätzlich würde ich immer auf Rekursion bei der Implementierung verzichten, sofern sich dadurch keine gewichtigen Vorteile ergeben. Vorteile können zB Simplizität oder Eleganz sein.

Um mal konkret zu werden:

Wie Blue-Tiger schon sagt, das hört sich nach einer Ablaufkette an. Also keine Notwendigkeit, hier irgendwas zu iterieren.
Schwer zu sagen. Da müsste man erstmal die konkreten Vorgehensweise kennen.
Hier sehe ich auch noch nicht, an welcher Stelle iteriert werden soll.
- 1. Auch hier hängt es wiederum davon ab, auf welchen Such- oder Sortieralgorithmus zurückgegriffen wird.

DEvent

groovemaster schrieb:

[...]Das hat vor allem zwei Gründe, Stackspeicher und Geschwindigkeit. Jeder Rekursionsschritt benötigt einen Funktionsaufruf. D.h. es wird nicht nur Stackspeicher "verbraucht", jedes call/ret und Initialisieren des Stackframes benötigt Zeit. In sehr simplen Szenarien kann das uU zwar optimiert werden, auch dahingehend, dass kein Overhead entsteht. Das bleibt aber die Ausnahme. Für simple und rechenaufwändige Algorithmen ist die Realisierung mittels Rekursion also eher ungeeignet, da sich die Nachteile hier besonders stark auswirken.[...]

Das ist aber auch nur auf C/C++ und aehnliche Sprachen bezogen. Ich denke in funktionalen Sprachen ist Rekursion effektiver als iteration. Nicht das der Threadstarter denkt das Rekursion ueberall schlecht ist.

Die schrittweise Steuerung eines fest vorgegebenen Produktionsablaufs

Wieso denn das, was eine Dödel- SPS so machen kann, soll sie so tun. Nicht rekursiv.

Suchprobleme, beispielsweise die Suche nach einem Begriff im Glossar
eines elektronischen Dokuments oder nach einem Namen in einem elektronisch
aufbereiteten Telefonbuch

Unsinns- Frage, hängt vom Aufbau der Daten ab. Wenn jemand auf Suchbäume abzielt: Rekusiv, sonst eher nicht.

Die Ermittlung einer zulässigen Belegung der Variablen eines
Gleichungssystems mit mehr unbekannten Variablen als Gleichungen

Beides möglich. Rekursiv gefährlicher.

Ansteuerung einer Messsonde sowie Klassifikation und Abspeicherung
der Messdaten auf Datei

Da bringt Rekursion gar nix.

Sortierung von Messdaten.

S.h. 4) ^^^^^

Bei 3) gilt das von groovemaster Erwähnte, daß erstmal Returnstack und Frameverwaltung Performance und Speicher abknapsen. Ist beides knapp, muß man den Kopf schiefhalten und ermitteln, ob in der möglichen Aufruftiefe das gewünschte Ergebnis überhaupt gesichert erhältlich ist. Solange man nicht den mathematischen Beweis führen kann, daß die Rekursion zu einem gesicherten Ende führt, sollte man die Finger davon lassen.
Klassiker ist da z.B. der Newtonsche Nullstellenalgorithmus, der rekursiv ohne Konvergenzbetrachtung programmiert zu überaus lustigen Pleiten führen kann.

Doc.Snuggles

Vielen Dank für die hilfreichen Tipps. Ist mir klar, dass das Anwenden nur durch ausrechend viel Erfahrung klappt,
aber ich wollte vorab einfach mal nen kleinen roten Faden, an dem ich mich orientiern kann.

Danke und bis denn
Snugg

DEvent schrieb:

Das ist aber auch nur auf C/C++ und aehnliche Sprachen bezogen. Ich denke in funktionalen Sprachen ist Rekursion effektiver als iteration. Nicht das der Threadstarter denkt das Rekursion ueberall schlecht ist.

ich denke rekursion ist immer dann angebracht, wenn die aufgabe schon von ihrer natur her nach einer rekursiven lösung schreit. sonst ist rekursion nicht angebracht, eigentlich egal in welcher sprache.

rüdiger

Rekursion sollte man in C (und in C++) am besten ganz vermeiden: http://damienkatz.net/2008/02/recursion_unsaf.html

rüdiger schrieb:

Rekursion sollte man in C (und in C++) am besten ganz vermeiden: http://damienkatz.net/2008/02/recursion_unsaf.html

jaja, die guten stack overflows? dann machste es eben so: http://www.olympus.net/personal/7seas/recurse.html

DEvent schrieb:

Das ist aber auch nur auf C/C++ und aehnliche Sprachen bezogen. Ich denke in funktionalen Sprachen ist Rekursion effektiver als iteration. Nicht das der Threadstarter denkt das Rekursion ueberall schlecht ist.

Nicht, dass ich wüste. Bei OCaML wird die Rekursion genauso mit einem Stack gemacht, wie überall sonst. Wie soll es auch anders gehen. Wird bei der Rekursion der Rückgabe wert nicht benötigt, so optimiert OCaML dahingehend, dass aus der Rekursion automatisch eine Schleife gebaut wird, also Alles vom Computer iterativ gelöst wird, ohne Stack.

groovemaster

stackless-freak schrieb:

jaja, die guten stack overflows? dann machste es eben so: http://www.olympus.net/personal/7seas/recurse.html

Das ändert an der Problematik aber nichts. Und bei dem Aufwand wäre eine nicht-rekursive Lösung wohl auch einfacher und eleganter.