Fachkonzept
Als nächstes wollen wir uns ein weiteres mathematisches Problem mit interessanten eigenschaften anschauen: die Fibonacci-Reihe.
Aufgabe 3
- Erste Fibonacci-Zahl:
fib(0) = 0 - Zweite Fibonacci-Zahl:
fib(1) = 1 - n+1-te Fibonacci-Zahl:
fib(n) = fib(n-1) + fib(n-2)für n > 1
Das hießt die n+1-te Fibonacci-Zahl ist die Summe der beiden vorherigen Fibonacci-Zahlen. Schau dir die folgenden Beispiele an und vergleiche sie mit der Fakultät. Was ist diesmal anders in Bezug auf die beiden Bausteine der Rekursion.
Beispiele:
- fib(2) = fib(1) + fib(0) = 1 + 0 = 1
- fib(3) = fib(2) + fib(1) = fib(1) + fib(0) + 1 = 1 + 0 + 1 = 2
- fib(4) = fib(3) + fib(2) = fib(2) + fib(1) + fib(1) + fib(0) = fib(1) + fib(0) + 1 + 0 + 1 = 1 + 0 + 1 + 1 = 3
Erklärung
Wir sehen also: eine Funktion kann auch mehr als einen rekursiven Aufrufe haben. Rekursive Funktionen mit maximal einem rekursiven Aufruf nennen wir "linear rekursiv", solche mit zwei rekursiven Aufrufen, nennen wir "binär rekursiv". Außerdem fällt auf, dass die Fibonacci-Funktion zwei Basisfälle hat, also zwei Instanzen des Problems, die keinen rekursiven Aufruf erfordern. Das liegt daran, wie die Fibonacci-Zahlen definiert sind.
Aufgabe 4
Aufgabe 5
- Welche Unterschiede fallen dir zu den Diagrammen davor auf?
- Spielt es eine Rolle, in welcher Reihenfolge du die Knoten anklickst?
- Wo endet jeweils der rekursive Abstieg und wo beginnt der rekursive Aufstieg?
Erklärung
Die rekursiven Aufrufe bei der Fibonacci Funktion sind unabhängig voneinander und können deshalb in beliebiger Reihenfolge ausgeführt werden.
