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.