6 Rekursion, numerisch
Zum vorigen Kapitel Zum Inhaltsverzeichnis Zum nächsten Kapitel


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:
In Delphi : 
   function faku(n: Integer): Integer;
     begin
     If n = 0 then
       Result := 1
     else
       Result := n * faku(n-1);
     end;
In Java : 
   int faku(int n) {
     if (n == 0) {
       return 1
     } else {
       return n * faku(n-1);
     }
   }
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.



Aufgaben:


  1. Die Fibonacci-Zahlen


    2. Der Klassiker unter den rekursiven Funktionen ist die Folge der Fibonacci-Zahlen. Auf diese Zahlenfolge ist der italienische Mathematiker "Leonardo da Pisa, genannt Fibonacci" schon zu Beginn des 13. Jahrhundert gestoßen, als er Wachstumsvorgänge mathematisch modelliert hat. In einer modernen Sprache gilt für die Zahlenfolge (fibo(n)) die folgende Definition: 
                        / 1                     für n = 1 sowie n = 2
       fibo (n) =  {
                    \ fibo(n-1) + fibo(n-2) für n > 2
    Ab der dritten Zahl der Folge gilt also: Jede Fibonacci-Zahl ist die Summe der beiden vorhergehenden Fibonacci-Zahlen.

    1. Schreiben Sie ein Programm, das eine rekursive Funktion zur Berechnung der Fibonacci-Zahlen enthält und Ihnen damit eine Liste der ersten 50 Fibonacci-Zahlen erstellt und anzeigt. Falls Sie dabei über wesentliche Schwierigkeiten stolpern, versuchen Sie herauszubekommen, worin das Problem besteht. Und vielleicht bemerken Sie ja auch, dass es eigentlich 2(!) verschiedene Probleme gibt...
      Bis zu welchem Index liefert Ihr Programm verlässliche Werte für die Fibonacci-Folge?

    2. Die Folge der Quotienten (f(n+1)/f(n)) zweier aufeinanderfolgender Fibonacci-Zahlen strebt gegen eine bestimmte irrationale Zahl Φ. Bestimmen Sie die Dezimalbruchentwicklung dieser Zahl möglichst genau!

    3. Wenn Ihnen Mathe Spaß macht, können Sie noch ein wenig weiter forschen:
      Wenn man nicht nur die Quotienten f(n+1)/f(n), sondern auch deren Kehrwerte ausgibt, dann erhält man eine weitere Folge, deren Grenzwert offenbar 1/Φ ist. Die vom Programm produzierte Tabelle der Werte legt nahe, dass die Dezimalbruch-Entwicklungen von Φ und 1/Φ offenbar nach dem Komma übereinstimmen - zumindest im Rahmen der Rechengenauigkeit! Wir nehmen mal an, dass Φ und sein Kehrwert tatsächlich diese Eigenschaft haben. Welchen Wert erhält man dann bei der Berechnung der Differenz von Φ und 1/Φ? Schreiben Sie eine entsprechende Gleichung auf! Wenn Sie diese lösen, erhalten Sie eine exakte Darstellung von Φ!
      Aber wahrscheinlich ist das doch zu schwer für Sie...
    Lösungsvorschlag [Delphi] [Java]


  2. Pascal und die Rekursion


    3. 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

    Machen Sie sich klar, dass diese Definition nichts weiter ist als eine formale Beschreibung der umgangssprachlichen Regel, die Sie für die Bildung der Zahlen des Pascal'schen Dreiecks schon früher kennengelernt haben: "Jede Randzahl ist 1, jede innere Zahl ist die Summe der beiden darüberstehenden Zahlen."

    1. 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.....

    2. Wie oft muss die Funktion Bino() 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 diese dann ja ohne Computer beweisen.

    Lösungsvorschlag [Delphi] [Java]


Zum vorigen Kapitel Zum Inhaltsverzeichnis Zum nächsten Kapitel