Fibonacci-Zahlen

• Rekursive Funktion:
  • Funktion, die sich selbst aufruft
  • kann auch indirekt geschehen (a ruft b, b ruft a)
  • muss ein Abbruch-Kriterium haben, sonst unendliche Verschachtelung (führt zum Programm-Absturz)
  • Compiler muss viel Information verwalten: lokale Variablen aller aufgerufenen Funktionen (Stack Frames) gemäß Verschachtelungstiefe
  • Anwendungen z.B.
    • dynamische Datenstrukturen (Listen, Bäume)
    • Algorithmen mit Zerlegungsverfahren (Quicksort, Strassen)
  • manche einfachen Rekursionen lassen sich besser mit Schleifen programmieren
• Beispiel Fibonacci-Zahlen:
  • erfunden als Modell zur Kaninchenvermehrung
  • definiert durch
    • a₀ = 0
      a₁ = 1
      a_n+2 = a_n+1 + a_n
• Rekursive Implementierung:

  • int fiboRek(int n) {
      switch (n) {
       case 0:
         return 0;
       case 1:
         return 1;
       default:
         return fiboRek(n-1) + fiboRek(n-2);
      }
    }
    

  • Ausführung von fiboRek(4):

    • fiboRec(4) = fiboRek(3) + fiboRek(2)
                 = (fiboRek(2) + fiboRek(1)) + (fiboRek(1) + fiboRek(0))
                 = ((fiboRek(1) + fiboRek(0)) + 1) + (1 + 0)
                 = ((1 + 0) + 1) + 1
                 = (1 + 1) + 1
                 = 2 + 1
                 = 3
      

  • 9 Funktionsaufrufe, 4 Additionen
• Iterative Implementierung:

  • int fiboIt(int n) {
      switch (n) {
       case 0:
         return 0;
       case 1:
         return 1;
      }
    
      int letzter    = 1;
      int vorletzter = 0;
      int neuer      = 0;
      for (i=2; i<=n; i++) {
        neuer = letzter + vorletzter;
        vorletzter = letzter;
        letzter = neuer;
      }
      return neuer;
    }
    

  • Ausführung von fiboIt(4):

    vorletzter	letzter	neuer
    0	1	1
    1	1	2
    1	2	3
    2	3	5

  • 1 Funktionsaufruf, 3 Additionen