13.2. Iteration oder Rekursion?

Letztmalig dran rumgefummelt: 29.01.08 22:41:38

	Rekursion: wiederholter Aufruf eines Unterprogrammes durch sich selbst, bis eine definierte Abbruchbedingung erreicht wurde - ist doch eigentlich ganz einfach - oder? Das es dies eben nicht ist, zeigen wir im Nachhinein. Eine Rekursion ist ein Programmteil der, um eine Aufgabe, die sich bis zur Abbruchbedingung, also einen return-Fall, der true oder false, je nach Implementation, sein kann, liefert, gliedert, zu erledigen, verschachtelt ist. - Oder anders: Um Rekursion zu verstehen, muss man erst Rekursion verstehen ;-)
	1. Iteration 2. Rekursion 3. Direkte und Indirekte Rekursion 4. Absteigender und aufsteigender Ast 5. Endständige Rekursion 6. Echte Rekursion 7. Web-Links 8. Verwandte Themen
	die Informatikseiten Logo für die Rekursion Informatik-Profi-Wissen
	Quellen: Lehr- und Übungsbuch Informatik Band 1 - 5 Seite ??? Technische und Theoretische Informatik  Seite ???

1. Iteration

	Wiederholung, bis eine definierte Abbruchbedingung erreicht wird. Für den Fall, dass die Anzahl der Durchläufe bekannt, reduziert sich der Aufwand schon mal auf eine Zählschleife, in jedem Falle aber muss die Parameterweitergabe innerhalb der Schleife vorgenommen werden und zum definierten Abbruch in endlicher Zeit mit verfügbarer Menge führen.
	das ist für einige Rekursionsarten ohne weiteres möglich und bis zu einer bestimmten Mächtigkeit auch von Vorteil. Kaskadenartige Rekursion lässt sich nicht mehr iterativ umsetzen, da hierbei zwei voneinander abhängige Wiederholungen gleichzeitig mit gegenseitig bekannten Parametern abgearbeitet werden müssen.
	Was spricht gegen Rekursion? teilweise extrem lange Rechenzeit, in der u. U. gar nicht passiert (z. B. beim rekursiven Abstieg oder Aufstieg, die mit keinerlei sichtbarer Funktion gefüllt sind) enormer Speicherbedarf schon für kleinere Algorithmen kompliziert in der Beschreibung, Vermittlung und wohl auch im Ablauf (versuch's, einem Laien die Fibonacci Zahlen rekursiv zu erklären)

2. Rekursion

	Das muss aber auch einfacher gehen ;-)
	Rekursive Objekte sind Objekte, die aus sich selbst aufgebaut sind ;-) die rekursive Fakultätsfunktion
	Definition einer Funktion oder eines Verfahrens durch sich selbst. Rekursive Darstellungen sind im allgemeinen kürzer und leichter verständlich als andere Darstellungen, da sie charakteristische Eigenschaften einer Funktion betonen. Es wird ein Unterprogramm solange durch sich selbst aufgerufen, bis eine definierte Abbruchbedingung erfüllt ist (die definierte Abbruchbedingung ist dann die maximale Vereinfachung). Prinzipiell können fast alle Rekursionen auch iterativ geschrieben werden, dies ist in der Regel jedoch mit der Anwendung von mehr Variablen und größeren Quelltexten verbunden (Ausnahme: Ackermann-Funktion). Rekursion muss als theoretisches Prinzip und als praktische Ausführungsvorschrift beschrieben werden. In der theoretischen Beschreibung wird Rekursion so verstanden, dass ein Verfahren vereinfacht auf sich selbst zurückgeführt wird, bis keine weitere Vereinfachung mehr möglich ist. Praktisch bedeutet sie einen Aufruf eines Unterprogramms durch sich selbst mit anderen Parametern. Dies wird solange wiederholt, bis die Lösung hinreichend genau ist (der Algorithmus muss ja terminieren), eine maximale Vereinfachung des Problems erreicht oder das Ergebnis feststeht. Die Lösung muss nach einer endlichen Zeitspanne vorliegen. Schauen wir uns dies praktisch an: Ein Mathematiker und ein Physiker bekommen je zwei Aufgaben gestellt: Aufgabe 1) Gegeben ist: ein leerer Topf, ein Wasserhahn eine Kochstelle Wasser ist zum Kochen zu bringen! Beide lösen die erste Aufgabe richtig - füllen die Töpfe mit Wasser und bringen das Wasser auf der Kochstelle zum Kochen. Doch danach folgt Aufgabe 2) Gegeben ist: ein voller Topf, ein Wasserhahn eine Kochstelle Der Physiker nimmt den Topf mit Wasser stellt ihn auf die Kochstelle und bringt das Wasser zum Kochen. Der Mathematiker schüttet das Wasser aus und führt damit die Aufgabe auf ein schon gelöstes Problem zurück!
	„In den alten Zeiten, wo das Wünschen noch geholfen hat, lebte im Halleschen eine Fee, die pflegte jedem Sonntagskind, das sich zu ihr zu finden wusste, an seinem Geburtstag einen Wunsch zu gewähren. Nun gedieh da auch ein Knabe, hieß Hannes, ein ehrlich Blut, dünkte sich nicht auf den Kopf gefallen, der war an einem Sonntag Punkt zwölf geboren. Als Hannes an seinem 18. Geburtstag von Muttern in das Geheimnis eingeweiht wurde, war er vor Freude fast außer sich wusste auch die Fee zu finden und bedachte nun, was er sich wünschen solle. Aber es wollte und wollte ihm nicht einfallen. Manchmal meinte er, jetzt hätte er’s, aber hernach schien's ihm doch zu wenig. Die Fee wird allmählich ungeduldig, sagt, er möge sich beeilen, da murmelt er in seiner Not so vor sich hin : „Ich wollte, ich hätte noch einen Wunsch frei.“ Wie aber das letzte Wort aus seinem Munde kommt, ist die Fee verschwunden. Hannes schaut verdutzt um sich, dann geht ihm auf, dass sein Wunsch in Erfüllung gegangen - aber erst übers Jahr kann er sein Glück neu versuchen. Als das Jahr herum, steht er wieder vor der Fee und bedenkt sich, was er wünschen soll „Wenn ich mir auch alle Reiche und Schätze der Welt wünsche“, spricht er zu sich selbst, „so fällt mir hernach noch allerlei ein. Ich will’s aber so einrichten, dass mir gar nichts mehr zu wünschen übrig bleibt.“ Die Fee wird allmählich ungeduldig, sagt, er möge sich beeilen, da murmelt er in seiner Not so vor sich hin: „Ich wollte, ich hätte noch einen Wunsch frei.“ Als aber das letzte Wort aus seinem Munde kommt, ist die Fee verschwunden. Hannes schaut verdutzt um sich, dann geht ihm auf, dass sein Wunsch in Erfüllung gegangen - aber erst übers Jahr kann er sein Glück neu versuchen. Als das Jahr herum, steht er wieder vor der Fee und bedenkt sich, was er wünschen soll ... (Aus Platzgründen kann die Geschichte leider nicht vollständig abgedruckt werden.)“ Diese Geschichte nennt man eine „rekursive“ Geschichte, womit man ausdrücken will, dass die Geschichte sich wiederholt, indem sie immer wieder auf sich selbst „zurückläuft“ (lat.: recurrere = zurücklaufen), bis sie bei einem imaginären Anfang (oder Ende) angekommen ist - was in diesem Leben allerdings nicht eintreten dürfte. Zusammenfassung: Manche Vorgänge des täglichen Lebens haben die Eigenart, dass sie sich auf sich selbst beziehen. Sie lassen sich durch rekursive Funktionen und rekursive Prozeduren nachbilden. Solche Funktionen und Prozeduren rufen sich in ihrem Anweisungsteil selbst auf!
	Sicherlich haben Sie während einer Fernsehsendung schon einmal beobachten können, wie im Fernsehstudio die Kamera auf einen Monitor geschwenkt wird, der das augenblicklich gesendete Bild zeigt Ein Monitor mit einem Monitor mit einem Monitor mit einem Monitor ... Sie können sich auch mit einem Spiegel in der Hand vor einen Spiegel stellen und dabei den Handspiegel so halten, dass sie im Spiegel auf dem Handspiegel Ihr Spiegelbild samt Handspiegel erkennen u. s. w.
	Das gefällt mir als Veranschaulichung besonders gut: „Der Lehrer, der den Unterstufenschüler, der eine Zigarette, die er am Kiosk, der sich neben der Schule befindet, kaufte, rauchte, sah, schimpfte.“
	Ein Mops kam in die Küche ...
	Was spricht für Rekursion? Entwicklung eines dynamischen Denkens neben Iteration und alternativen Strukturen ergibt in jedem Falle extrem kurze Algorithmen, da die Abbruchbedingung als Übergabeparameter versteckt wird einige, sehr wenige Probleme sind nur mit rekursiven Algorithmen lösbar (Ackermann-Funktion)
	Rekursive Prozeduren und Funktionen Für rekursive Aufrufe von Unterprogrammen im Allgemeinen müssen Parameter übergeben werden, damit immer eine Abbruchbedingung in den nächsten Aufruf „mitgenommen“ werden kann. Bei Prozeduren müssen dies Referenz- und bei Funktionen Werteparameter sein, da sonst die Rückkehrwerte überschrieben werden würden bzw. bei Prozeduren sonst nichts zurückgegeben wird.
	... ist die Anzahl der rekursiven Aufrufe eines Unterprogramms, bis die Abbruchbedingung erfüllt ist

3. Direkt und Indirekte Rekursion

	Bei direkter Rekursion ruft sich das Unterprogramm bis zur Erfüllung der Abbruchbedingung jeweils direkt selber auf - die Abbruchbedingung ist auch in diesem Unterprogramm eingebunden (McCarthy-Funktion, Hofstätter-Funktion), bei indirekter Rekursion wird das Unterprogramm wiederholt von einem anderen Unterprogramm aus aufgerufen - die Abbruchbedingung steht im übergeordneten Unterprogramm (Collatz-Funktion).
	beiden ist aber das Prinzip des rekursiven Abstiegs und nachfolgenden rekursiven Aufstiegs gemein rekursiver Abstieg rekursiver Aufstieg

4. Absteigender und aufsteigender Ast

	In einem Ast wird gerechnet, im anderen mit veränderten Argument nur die Funktion oder Prozedur bis zu Abbruchbedingung selbst aufgerufen. Ob im ausfsteigenden oder absteigenden Ast gerechnet wird, hängt von der physischen Stelle des Unterprogrammaufrufes auf sich selbst ab (Anfang oder Ende).
	Problem Wortumkehr: rekursiver Abstieg
	Umkehrwort Status Zielwort NEBEL NEBE L NEBE NEB LE NEB NE LEB NE N LEBE N   LEBEN
	Abbruchbedingung ist das Erreichen der Wortlänge rekursiver Aufstieg realisiert nur noch die Rückkehr!

5. Endständige Rekusion

	In einem Ast wird gerechnet, im anderen mit veränderten Argument nur die Funktion oder Prozedur bis zu Abbruchbedingung selbst aufgerufen. Ob im ausfsteigenden oder absteigenden Ast gerechnet wird, hängt von der physischen Stelle des Unterprogrammaufrufes auf sich selbst ab (Anfang oder Ende).
	rekursiver Aufruf erfolgt in der Mitte Beispiel: Türme von HANOI

6. Echte Rekusion

	In einem Ast wird gerechnet, im anderen mit veränderten Argument nur die Funktion oder Prozedur bis zu Abbruchbedingung selbst aufgerufen. Ob im ausfsteigenden oder absteigenden Ast gerechnet wird, hängt von der physischen Stelle des Unterprogrammaufrufes auf sich selbst ab (Anfang oder Ende).
	rekursiver Aufruf erfolgt in der letzten Zeile lassen sich auch iterativ (durch Schleifen) programmieren Beispiel: n!
	die Quadratfunktion mal rekursiv gelöst - das wird anspruchsvoll!!! die Fakultätsfunktion mal rekursiv gelöst - das ist weniger  anspruchsvoll als die Quadratfunktion!!!

7. Web-Links

	http://tu-ilmenau.de/fakia/fileadmin/template/startIA/swt/Lehre/AuP_Materialien/VL_8.pdf

8. Verwandte Themen

	Das Vorangestellte hilft wirtschaften, löst jedoch kein einziges Problem (allerdings ohne Beachtung der Worst-Case-Strategien wird man auch nicht erfolgreich Software entwickeln und/oder informatische Projekte realisieren können). Deshalb nunmehr das, was wirklich Arbeiten hilft.
	Worst-Case-Denken Algorithmentheorie Komplexität, Mächtigkeit und Aufwand Praktische Elementaralgorithmen Lösbarkeit und Problemlösungsstrategien Zufall und Computer Graphentheorie Petri-Netze
	Informationsbegriff Logo für die Signale Nachrichten Wissen Systembegriff Modellbegriff Simulation Denken und Sprache Zahlen, Daten und Datentypen Gegenläufigkeit und Verklemmung Pattern-Matching

zur Hauptseite

© Samuel-von-Pufendorf-Gymnasium Flöha

© Frank Rost im August 1995