Python 3

1Ein erstes Beispiel

Die Reihe der Fibonacci-Zahlen beginnt bekanntlich so:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, . . .

Offensichtlich ist jede Zahl die Summe ihrer beiden Vorgänger, wenn wir 0, 1 als Anfang vorgeben. Die rekursive Definition der Folge (Fn)n∈ℕ sieht bekanntlich so aus:

$F_n:=\{\begin{array}{ll}0,\hfill & \text{falls }n=0,\hfill \\ 1,\hfill & \text{falls }n=1,\hfill \\ F_{n-2}+F_{n-1},\hfill & \text{falls }n\ge 2.\hfill \end{array}$

1.1Implementierungen

Ein Python-Skript, mit dem man die Zahlen rekursiv berechnet, lässt sich wie folgt formulieren:

Dann berechnet der Aufruf fib(0, 1, n) die Zahl F n. In der Tat gibt der Aufruf fib(0, 1, 0) den Wert 0 = F0, der Aufruf fib(0, 1, 1) = fib(1, 1, 0) = 1 gibt also 1 = F1 zurück. Wir behaupten, dass for ...