Lineare Datenstrukturen

Anwendung beim Programmieren

Bei Programmen, die sich selbst rekursiv aufrufen, verwaltet der Rechner die jeweiligen Parameterwerte in einem Stack.

einfaches Beispiel

Die Zahl n! = n(n-1)(n-2)...1 ("n Fakultät") kann man für n > 0 berechnen als n! = n (n-1)! . (Dabei wird 0! = 1 gesetzt. )
In dem folgenden Experiment wird der Ablauf eines rekursiven Programms zur Berechnung von n! simuliert.

Dank

Beobachte den Stack.

raffinierteres Beispiel

Die Binomialkoeffizienten $\left( \begin{array}{c} n \\ k \end{array} \right)$ sind für $0 \leq k \leq n$ definiert als

$\left( \begin{array}{c} n \\ k \end{array} \right) = \frac{n!}{k!(n-k)!}.$

Durch Nachrechnen erkennt man, dass für $0 < k < n$ die Beziehung

$\left( \begin{array}{c} n \\ k \end{array} \right) = \left( \begin{array}{c} n-1 \\ k \end{array} \right) + \left( \begin{array}{c} n-1 \\ k-1 \end{array} \right)$

gilt.
Das folgende rekursive Programm nutzt diese Beziehung. Es enthält jetzt zwei rekursive Aufrufe.

Teste
n=3, k=2
n=5, k=3
...
Dank

Gib Werte für n und k ein.

Bewertung

Rekursive Programme bieten sich für viele Problemstellungen an. Häufig sind sie elegant und kurz. Aber Vorsicht: der Rechenaufwand kann unerwartet hoch sein.
Das rekursive Programm für die Binomialkoeffizienten ist elegant, weil es weder Multiplikationen noch Divisionen durchführt. Dafür machte es aber sehr viele Additionen.