Rekursion, numerisch

6 Rekursion, numerisch

Häufig wird Rekursion bei Funktionen angewendet, deren Berechnungsalgorithmus sich dadurch besonders einfach formulieren läßt. Das wohl bekannteste Beispiel ist die Fakultäts-Funktion: unter der Fakultät einer natürlichen Zahl n versteht man das Produkt aller natürlichen Zahlen von 1 bis n. Um also aus der Fakultät von (n-1) die Fakultät von n zu berechnen, muss man das Ergebnis der Fakultät von (n-1) mit n multiplizieren. Zusätzlich zur obigen Definition setzt man fest, dass die Fakultät von 0 als 1 definiert ist. Insgesamt erhält man damit die folgende rekursive Definition:

                    /  1             für n = 0
       faku (n) =  {
                    \ n * faku (n-1) für n > 0

Diese Definition läßt sich direkt in der folgenden Funktion implementieren:

       function faku(n: Integer): Integer;
         begin
         If n = 0 then
           Result := 1
         else
           Result := n * faku(n-1);
         end;

Obwohl diese Formulierung des Algorithmus in der Tat recht elegant ist, würde man in der Praxis für die Fakultätsberechnung eher keine Rekursion einsetzen: das Produkt der ersten n natürlichen Zahlen kann viel einfacher mit einer FOR-Schleife berechnet werden, was im übrigen auch deutlich schneller läuft als die rekursive Version mit ihren vielen ineinandergeschachtelten Funktionsaufrufen.

Das eigentliche Einsatzgebiet rekursiver Funktionen sind denn auch solche Situationen, in denen erst zur Programmlaufzeit festgelegt werden kann, welche Struktur der Berechnungsalgorithmus der implementierten Funktion genau hat. Solche Funktionen tauchen z.B. beim Compilerbau oder in der KI-Forschung häufig auf.

Und nun sind Sie dran:

Erstellen Sie ein Programm, das mit Hilfe einer rekursiven Funktion die Binomialkoeffizienten berechnet. Die Binomialkoeffizienten sind die Zahlen aus dem Pascal'schen Dreieck: Bino(n,k) ist der Koeffizient des k-ten Summanden der Summe, die man erhält, wenn man (a+b)^n ausmultipliziert. Dabei sind n und k zwei ganze Zahlen mit 0 <= k <= n.

Vielleicht wissen Sie noch, wie man die Zahlen "graphisch" im Pascal'schen Dreieck konstruiert:
jede Zahl ist die Summe der beiden darüberstehenden Zahlen, und an den Rändern stehen lauter Einsen. Dies führt auf folgende Definition:
                     /  1               falls (k=0) oder (k=n)
     Bino (n, k) =  {
                     \ Bino(n-1, k-1) + Bino(n-1, k)     sonst
Mit dieser Definition sollte es Ihnen gelingen, die Binomialkoeffizienten für nicht gar zu große n und k zu berechnen. Vergrößern Sie die Parameter vorsichtig, da Ihr Rechner sonst möglicherweise für den Rest des heutigen Tages keine anderen Aufgaben mehr annehmen kann.....

Für Fortgeschrittene:

Wie oft muss diese Funktion aufgerufen werden, um Bino(n, k) zu berechnen?
Ergänzen Sie Ihr Programm durch eine entsprechende Statistik, und probieren Sie erst einmal mit kleinen Werten für n und k. Wenn Sie schließlich eine Vermutung haben, können Sie die ja dann ohne Computer beweisen.