Wissen: Rekursion

Autor: Dr. Volkmar Naumburger ❤️ Bedanken

Einführung Rekursion

Die Rekursionstheorie ist die Theorie des absolut Berechenbaren. Sie wurde durch GÖDEL, CHURCH, KLEENE, TURING und POST begründet und führt mit relativ kurzen Schlüssen zu weitreichenden Einsichten.

Ein rekursiver Algorithmus enthält zunächst noch ungelöste Probleme, zu deren Lösung man denselben Algorithmus nochmals anwenden muss.

Ein rekursiver Algorithmus liegt also dann vor, wenn in einer elementaren Anweisung ein Verweis auf den eigenen Algorithmus erfolgt. (Man sagt auch: "der Algorithmus ruft sich selbst auf")

GÖDEL definiert eine rekursive Funktion so:

Eine Funktion ist rekursiv, wenn sie eine Ausgangsfunktion ist oder sich aus solchen in endliche vielen Schritten durch Anwendung der angegebenen Operationen erzeugen lässt.

Anfangsfunktionen sind:

  • Argumentenauswahlfunktionen (Idenditäten)
  • Konstante Funktionen
  • Nachfolgerfunktionen \( (∀ n∈⊆ \; n^{\boxed{ }} = n + 1) \)

Operationen mit Funktionen sind:

  • Verkettung von Funktionen
  • Erzeugung von Funktionen durch primitive Rekursion
  • Erzeugung von Funktionen durch (beschränkte) Minimumbildung.

Rekursive Berechnung von Quadratwurzeln

Die Wurzel einer positiven reellen Zahl a, die > 1 ist, ist ebenfalls > 1. Ista < 1, ist die Wurzel auch < 1. Aus dieser Feststellung kann abgeleitet werden, dass

\(1 + r = \sqrt a \) Gl. 95

worin r ein noch nicht bekannter Rest ist. r ist positiv, wenn a > 1 sonst negativ.

Beidseitiges quadrieren von Gl. 95 führt auf

\( {\left( {1 + r} \right)^2} = a \) Gl. 96

Auflösen des Binoms

\( 1 + 2r + {r^2} = a \) Gl. 97

und Umstellen

\( r \cdot \left( {2 + r} \right) = a - 1 \) Gl. 98

Schließlich folgt die Rekursionsvorschrift für die Berechnung des Rests r:

\( r = \frac{ {a - 1} }{ {2 + r} } \) Gl. 99

Das r der linken Seite von Gl. 99 kann beliebig oft in das r der rechten Seite eingesetzt werden. Dies entspricht dem Selbstaufruf, der für Rekursionen typisch ist.

Für numerische Anwendungen wird Gl. 5-8 besser so geschrieben:

\( {r_{i + 1} } = \frac{ {a - 1} }{ {2 + {r_i} } } \) Gl. 100

Worin i den aktuellen Rekursionsschritt bezeichnet.

Beispiel

Gesucht ist die Quadratwurzel aus 2. Die Anwendung von Gl. 100 führt auf:

\( {r_{i + 1} } = \frac{ {2 - 1} }{ {2 + {r_i} } } = \frac{1}{ {2 + {r_i} } } \).

Mit der Startannahme, dass der Rest r0 gleich Null ist, führt der erste Schritt auf r1 = 0,5 und so weiter:

\( {r_{i + 1} } = \frac{1}{ {2 + \frac{1}{ {2 + \frac{1}{ {2 +..... + \frac{1}{ {2 + {r_0} } } } } } } } } \)

Dies ist ein Kettenbruch, der bereits nach vier Schritten eine Wert für den Rest von r4 = 0,41428... Der gesuchte Wurzelwert ergibt sich dann zu

1 + r = 1,41428...

Der korrekte Wert lautet 1,41421...

Numerische Bestimmung von Funktionen oder deren Elemente

Bei der computerisierten Lösung mathematischer Aufgabenstellungen steht die Effizienz, d.h. Rechengeschwindigkeit und Speicherplatzbedarf, im Vordergrund. Daher werden Algorithmen gesucht, die diesen Anforderungen gerecht werden.

Beispiel 1

Die Berechnung von n! ist auf die Multiplikation aller ganzen Zahlen (n Î N) in aufsteigender Folge bis zum Wert n mit sich selbst zurückzuführen.

\( n! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5...n \) Gl. 101

Als Sonderfall ist 0! = 1 definiert.

Als Rekursionsformel lautet Gl. 101:

\( n! = n \cdot (n - 1)! \) Gl. 102

(n-1)! wird nun wiederum durch (n-1)(n-2)! usw. berechnet. Wenn endlich 0! = 1 erreicht worden ist (Abbruchbedingung) ist die Rekursion beendet.

Als C-Programm würde die Berechnung der Fakultät wie folgt aussehen:

int fact(int n) { if(n==0) return 1; else return n*fact(n-1); };

Beispiel 2

Die Berechnung der Koeffizienten des PASCAL’schen Dreiecks beruht auf der wiederholten (also rekursiven) Anwendung der folgenden Beziehung:

\( {a_{i,k} } = {a_{i - 1,k} } + {a_{i - 1,k + 1} } \) Gl. 103

Wobei i der Zeilenindex und k der Spaltenindex innerhalb des Dreiecks ist.

Die Startbedingung für i = k = 0 lautet:

\( {a_{0,0} } = 1 \) Gl. 104

Wie aus den Beispielen zu erkennen ist, eignen sich Rekursionen besonders für die prinzipielle Lösung von komplexen mathematischen Problemen.

Inwieweit eine Rekursionsformel Anweisungen für die numerische Lösung solcher Probleme liefern kann, ist fallweise zu untersuchen, da hier u.a. Instabilitäten gegenüber Rundungsfehlern Grenzen setzen können.

  Schreib uns deine Hinweise