Hallo, ich habe vor eine Facharbeit über Rekursive Algorithmik zu schreiben.
Habt ihr Ideen was man da so einbauen könnte, eventuell Problemstellungen etc ?
Klar ist Einleitung, dann Arten (Backtracing etc), Beispiele, Beispielprogramme (Hanoi oder so), aber was noch ?

Vielen Dank schonmal

Na wirst sicherlich auf die Abbruchbedingung zu sprechen kommen müssen. Ohne AbbB keine Terminiertheit der Rekursion -> Stackoverflow, wirste ja wissen.

jo das ist klar, aber dann bräuchte ich nochmehr vorteile nachteile etc, vereinfachung usw ist klar, aber ich muss immerhin 12 seiten text vollkriegen

Du kannst ja mal ganz anders rangehen. Ist das menschliche Gehirn überhaupt geeignet rekursive Programmierung nachzuvollziehen?
Ich erinnere mich an eine Anwendung mit einem 4-fachen Gruppenwechsel, den ich rekursiv programmiert habe. Trotz Kommentierung war das später ungeheuer schwierig nachzuvollziehen. War aber auch nicht erforderlich, da es einwandfrei lief.

@jasocul: Das kenn ich. Ich geh an Rekursionen immer so heran:
Schreiben, freuen dass es läuft und bloß nicht versuchen zu überlegen, was der Computer da alles tut.

Beste Grüße
Tastaro

Hallo,

ich hatte mal vor langer Zeit dieses Tutorial geschrieben, da findest du bestimmt ein paar Anreize.

Cu,
Udontknow

Na der Vorteil von Rekursion ist: sie sind ja obligatorisch, wenn die Anzahl der Durchläufe von vornherein nicht bekannt ist. Beispiel: Scannen einer Ordnerstruktur (unter FAT).
Ich weiß, dass man alle iterativen Algorithmen auch rekursiv lösen kann, aber nicht jeder rekursive Algo ist iterativ lösbar.

Nachteil: Speicherverbrauch (Stack + u.U. globale Variablen); Möglichkeit, dass Algo nicht terminiert (AbbB). Gibt sicher noch mehr - soll ja auch nur als Denkanstoß gelten.

Guck erstma, wieviel Seiten Du mit eigenem Wissen vollkriegst und dann schick mal PDF.
Facharbeit muss doch mit Deckblatt und Inhaltsverzeichnis sein, oder!? Haste schonmal 2 Blätter weg (4 Seiten!?).

Zitat:

Ich weiß, dass man alle iterativen Algorithmen auch rekursiv lösen kann, aber nicht jeder rekursive Algo ist iterativ lösbar.

Öhm, eine Rekursion wird ja vom Prozessor im Endeffekt immer unter Zuhilfenahme von Speicher (Aufruf-Stack) iterativ umgesetzt. Wird da nicht eher umgekehrt ein Schuh draus?

Zitat:

Nachteil: Speicherverbrauch (Stack + u.U. globale Variablen); Möglichkeit, dass Algo nicht terminiert (AbbB). Gibt sicher noch mehr - soll ja auch nur als Denkanstoß gelten.

Eine Rekursion ohne Abbruch-Bedingung terminiert eher als eine Endlos-Schleife...

Cu,
Udontknow

DaRkFiRe hat folgendes geschrieben:

Ich weiß, dass man alle iterativen Algorithmen auch rekursiv lösen kann, aber nicht jeder rekursive Algo ist iterativ lösbar.

Falsch! ALLE rekursiven Algorithmen sind iterativ lösbar! Ich frage mich, wieso dieser Schmarrn immer wieder verbreitet wird .

Ich würde (wegen der Würze) die Türme von Hanoi und/oder das 8-Dame Problem als exemplarisches Beispiel für rekursive Lösungswege bzw. Backtracking verwenden. Eine Andere Möglichkeit ist 'FloodFill': Ausfüllen eines geschlossenen Bereiches einer Bitmap mit einer bestimmten Farbe, wobei der Rand durch eine andere Farbe definiert ist:

Und eigentlich ist Rekursivität ganz einfach und entspricht auch unserer Denkstruktur: Ein Problem wird auf einen einzigen Schritt reduziert, nämlich den, der die Lösung ein bisschen näher bringt. Eigentlich ganz einfach. Das ist zwar eine Kunst (weil es so simpel ist), und verlangt ein wenig Übung, aber widernatürlich ist das nicht (finde ich, aber vielleicht bin ich ja auch pervers )



Oder, noch blöder:


Wir haben immer ein Abbruchkriterium, einen kleinen Teilschritt und den rekursiven Aufruf.

Beim *Backtracking* (Try and Error, Versuch und Irrtum) verhält sich das ähnlich, nur das ich den Schritt wieder rückgängig machen muss. Damit eignet sich das Backtracking nicht für 'Trapdoors', also für Operationen, die nur in eine Richtung funktionieren.

Rekursivität ist natürlich insbesondere bei rekursiven Datenstrukturen (Bäumen, Graphen allgemein etc.) sinnvoll.

Udontknow hat folgendes geschrieben:

Öhm, eine Rekursion wird ja vom Prozessor im Endeffekt immer unter Zuhilfenahme von Speicher (Aufruf-Stack) iterativ umgesetzt.

Na logisch. Das reicht, um den zu beweisen, das jeder rekursive algo in einen iterativen (eventuell 1000x komplizierteren) Algo zu transformieren.

Es ist aber viel interessanter, einen rekursiv formulierten Algorithmus in einen (auch von der Komplexität=Zeilenanzahl) äquivalenten iterativen Algorithmus zu verwandeln. DAS ist kniffelig und nicht immer ohne weiteres lösbar. Paradebeispiel: Ackermann. Da ist die rekursive Definition irgendwie 3 Zeilen lang, die iterative aber so um die 50...

wow vielen dank schonmal, da sind einige gute sachen dabei, die mich gleich inspiriert haben.

vor allem das mit der gehirnleistung, ich weiß es selbst, ich wollte die türme von hanoi coden, iterativ, das waren ne menge zeilen code, dann finde ich den rekursiven algo und das war ein zwei zeiler, es hat mich schon einige zeit gekostet den zu verstehen, weil er simpel ist, aber alles regeln der türme befolgt, schlichtweg genialste algorithmik.

gibts auch typische beispiele für indirekte rekursion ?

F34r0fTh3D4rk hat folgendes geschrieben:

gibts auch typische beispiele für indirekte rekursion ?

Wasndat?

Wusste gar nicht, dass eine Endlosschleife terminiert. Begründe das bitte.

Dass man eine Rekursion auch iterativ lösen kann, sind selbst lt. wikipedia (okay, muss ja nicht stimmen) nur Spezialfälle.
Natürlich geht das mit dem Stack, indem man den PC "nachempfindet". Rekursion sind ja im PC wie schon gesagt: Iterationen mit einem Stack.

Zitat:

Wusste gar nicht, dass eine Endlosschleife terminiert. Begründe das bitte.

Tut sie eben nicht!

Da eine Rekursion irgendwann mit einer EStackoverflow-Meldung abgebrochen wird, beendet diese sich "eher"... Ja, ich weiss, die Pointe ist mau.

Was die Wikipedia angeht:

Zitat:

Manche Programmiersprachen (insbesondere in der Funktionalen Programmierung) erlauben keine Iteration, sodass immer die rekursive Umsetzung gewählt werden muss.

Das ändert nichts daran, daß dem PC als Rechenmaschine gar nichts anderes übrig bleibt, als iterativ vorzugehen.

Cu,
Udontknow

DaRkFiRe, jede rekursion kann man auch iterativ auflösen, aber nicht jede iteration auch rekursiv.... das sind grundverschiedene ansätze....


PS: F34r0fTh3D4rk: wenn du was über rekursion lesen willst, so empfehle ich dir die klassiker der algo. theorie... da findest du spielend ein paar 1000 seiten... die du lesen kannst.. und für deine facharbeit werden dann auch noch 10 bis 20 seiten übrig bleiben.. also ruhig mal zur biblio gehen,...

Jau, dann hab ich das vertauscht - und das mit der Endlosschleife hab ich dann wohl nur überflogen. Ich schieb das jetzt mal auf meinen nicht durchgängigen 4-stündigen Schlaf letzte Nacht.

Grenzgaenger hat folgendes geschrieben:

DaRkFiRe, jede rekursion kann man auch iterativ auflösen, aber nicht jede iteration auch rekursiv.... das sind grundverschiedene ansätze....

Wieso könnte es einen iterativen Algorithmus geben, die man nicht rekursiv lösen kann? Das kann nicht sein, weil die 'Tail recursion' eine äquivalente Umsetzung einer Aufzählung ('Iteration') ist.

Vielleicht magst du darauf eingehen, wie man mit rekursiven Funktionen sehr schön komplexe Grafiken machen kann.
Sowas wird z.B. bei Demos genutzt um die Programme klein zu halten.
www.educeth.ch/infor.../leitprog/rekursion/

ich brauche noch einen guten syntax highlighter für word 2000, gibts irgendwo sowas ?

Bei den Gexperts ist einer mit drin, der unterstützt HTML,RTF,Zwischenablage