13.6. Repetive Rekursion

Letztmalig dran rumgefummelt: 20.12.07 07:39:26

	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. Verwandte Themen
	die Informatikseiten Logo für die repetive 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 ;-)
	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!

7. 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.
	Rekursive Datenstrukturen Funktionen & Prozeduren mit Parameterübergabe Rekursion primitive Rekursion µ-Rekursion lineare Rekursion kaskadenartige Rekursion Wechselseitige Rekursion
	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 Oktober 2007