Wann wird Rekursion verwendet und warum?

Doc.Snuggles

Tach,

bin neu im Land des Programmierens und versuche die Verwendung der Rekursion
zu begreifen und gezielt einzusetzen. Das Problem ist nur ich habe keine Ahnung,
wann Rekursion zur Anwendung kommt. Vielleicht kann mir jemand anhand der 5
Beispiele erklären wann und wann nicht rekursiv programmiert wird und
kann es eventuell auch noch begründen??? Ich hab zwar schon einiges im
Internet recherchiert, finde aber keinen Hinweis, wann Rekursion wirklich angebracht ist:

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.

Doc.Snuggles

Aus dem bisher gefunden Wissen würde ich - mehr aus dem Bauchgefühl entschieden als wirklich begündet -

1) als nicht rekursiv -- einzelne Arbeitsschritte machen eher objektorientiert sinnvoll
2) als rekursiv -- bei Suchalgorithmen angebracht, ständige Wiederholungen
3) weiß ich nicht -- ...
4) nicht als rekursiv -- Rekursion wird zwar bei math. Funktionen verwendet, vermute aber die Funktion ist zu speziell
5) als rekursiv -- bei Sortieralgorithmen angebracht, ständige Wiederholungen

bezeichnen. Ich weiß nicht, ob meine Begründungen Sinn machen oder ob sie außeichend sind. Kann mir bitte jemand helfen?

Snugg

Blue-Tiger

Im Grunde gilt: alles, was man sehr leicht rekursiv formulieren laesst (z. B. Fibonacci-Zahlen, oder die Berechnung der Fakultaet) kann man auch rekursiv programmieren. Aber sehr oft wird anstatt einer rekursiven Loesung eine iterative ( d.h. eine Schleife) hergenommen, weil sie in der Regel schneller ist. Aber Rekursion ist in der Regel ein viel eleganterer Weg, ein Problem zu loesen.

Aber bei vielen Aufgaben ist es so, dass man das gleiche Problem immer wieder loest, nur mit anderen (in der Regel kleineren) Paramteren.
Um z. B. die Fakultaet der Zahl x zu berechnen, muss man vorher die Fakultaet der Zahl x-1 berechnen ( = gleiches Problem, nur mit anderen Zahlen).
Um z. B. n Zahlen zu sortieren, kann man die erst in 2 Haelften mit je n/2 Zahlen aufteilen, und dann diese Sortieren ( = gleiches Problem, nur mit weniger Zahlen).
Um z. B. die Zahl x innerhalb der Zahlen 1 bis 500 zu finden, kann man erst mal schauen, ob x groesser oder kleiner als 250 ist, und brauch dann die Zahl x nur noch innerhalb von 1 - 249 bzw. 251 - 500 suchen ( = gleiches Problem, nur mit einem kleineren Suchraum).

Bei deinen Beispielen:

da wird eine Aktion Schritt fuer Schritt abgearbeitet, dabei gibts keine Wiederholungen. Das ist rein prozedural.
Es gibt sehr effiziente rekursive Suchalgorithmen, aber in der Regel wuerde man das iterativ machen.
wuerd ich persoenlich rekursiv machen: Ich probiere das erst mit der Belegung x aus, wenn das nicht klappt, versuch ich das gleiche Problem zu loesen, aber mit Belegung y.... und das mach ich so lange, bis ich eine Belegung gefunden hab. Aber evtl. gibts da effizientere Algorithmen, die keine Rekursion brauchen.
Wenn du auf Teufel-komm-raus Rekursion verwenden willst, kannst du das beim Schreiben der Messdaten zwar machen (ich schreibe Datensatz x, dann schreib ich Datensatz x+1), aber ich seh da keine Notwendigkeit fuer Rekursion.
siehe 2 Die meisten guten Sortieralgorithmen lassen sich rekursiv formulieren, werden aber oft iterativ implementiert.

@DocSnuggels:
ad 1) Objektorientierung hat da nix mit zu tun
ad 2 und 5) wie gesagt: kann man, aber muss man nicht.
ad 4) nur weil etwas mathematisch ist, wird nicht automatisch Rekursion verwendet.

groovemaster

So problemspezifisch kann man die sinnvolle Verwendung von Rekursion eigentlich nicht erläutern. Rekursion ist vor allem bei der _Formulierung_ von Algorithmen oder Abläufen nützlich. Bei der BNF findet Rekursion zB Verwendung, um Wiederholungen auszudrücken. Wenn es um die Implementierung geht, wird dann aber doch eher auf iterative Lösungen gesetzt. 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. Ich würde daher Rekursion eher bei Algorithmen mit geringer Tiefe und komplexen Schritten in Betracht ziehen. Hinzu kommt, dass man Rekursion nicht als Gegenstück zur Iteration betrachten sollte. Auch wenn sich beides mit dem jeweils anderen ausdrücken lässt. Dein Beispiel 1) scheint mir für Rekursion zB grundsätzlich ungeeignet.
Es sei noch angemerkt, dass Rekursion nach wie vor die Notwendigkeit der richtigen Algorithmen nicht ersetzen kann. Die Summe von n aufeinanderfolgenden natürlichen Zahlen lässt sich zB immer noch einfacher mit der Gaussschen Summenformel berechnen als mit Rekursion.

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.