Mathesis Wiki

Überträgt man die rekursive Definition der Fibonacci-Folge auf direkte Weise in eine Python-Funktion, erhält man so etwas:

def fibonacci(n):
    if (n == 1) or (n == 2):
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

Diese elegante Art, die Funktion zu definieren, hat jedoch einen entscheidenden Nachteil. Wenn wir mit $a_n$ die Folge bezeichnen, die angibt, wieviel Funktionsaufrufe nötig sind um fibonacci(n) zu berechenen, so sehen wir: $a_1=1$, $a_2=1$ und $a_n=1+a_{n-1}+a_{n-2}$ für $n>2$. Diese Folge wächst also schneller als die Fibonacci-Folge. Diese wächst für $n\to \infty$ so schnell wie $\left(\frac{1+\sqrt{5}}{2}\right)^n$. Die Rechenzeit wächst also ebenfalls mindestens mit dieser exponentiellen Rate. Benötigt der Rechner für fibonacci(40) Sekunden, so sind es für fibonacci (80) bereits Jahre. Im Laufe der Berechnung von fibonacci(n) werden die Werte der Folge für kleinere n immer wieder berechnet, eine große Verschwendung. Eine Art, dem beizukommen, ist, sich die bereits berechneten Werte zu 'merken' und nicht erneut zu berechnen.

merktabelle={}
 
def fibonacci(n):
    global merktabelle
    if not(n in merktabelle):
       if (n == 1) or (n==2):
           merktabelle[n]=1
       else:
           merktabelle[n]=fibonacci(n-1) + fibonacci(n-2)
    return merktabelle[n] 

Diese Lösung hat einen Vorteil und einige Nachteile: Benötigt man die Werte der Folge immer wieder, so wird die Funktion, nachdem sie die Werte einmal berechnet hat, sehr schnell. Andererseits ist ihr Speicherverbrauch linear in n, auch wird der Python-Interpreter für große n die Funktion sich sehr oft selbst aufrufen lassen müssen, bevor sie auf bereits tabellierte Werte stößt. Trotz der Nachteile dieses Verfahrens ist es nützlich, ein automatisierters Verfahren zu haben, dass aus einer beliebigen Funktion eine macht, die sich ihre Werte merkt. Dazu findet ihr Material in diesem Artikel über Memoizing und Decorators (hier besteht kein Unterschied zwischen Python 2.7 und Python 3).

Will man einfach nur eine Funktion, die für möglichst große Werte von n noch in der Lage ist, das n. Glied der Fibonacci-Folge zu berechnen, so kann man das in einer Schleife, die aus den ersten beiden Werten den dritten, aus dem zweiten und dritten, den vierten usw. bis zum n. berechnet:

def fibonacci(n):
   if (n==1) or (n==2):
       return 1
   else:
       a=1
       b=1
       k=2
       while (k<n):
           # Es gilt an dieser Stelle stets: a=fibonacci(k-1), b=fibonacci(k)
           a,b=b,a+b
           k=k+1
       return b

Dieses Programm liefert nun auch für sehr große Werte von $n$ den Wert der Fibonacci-Folge. Die Schleife muss zur Berechnung von fibonacci(n) n-2 mal aufgerufen werden. Da Python mit fast beliebig großen ganzen Zahlen rechnen kann, lässt sich so etwa fibonacci(100000) im Bruchteil einer Sekunde berechnen. Es kann aber auch in dieser Variante praktisch sein, eine Merktabelle anzulegen, wenn dieselben Werte immer wieder benötigt werden.