Mathesis Wiki

Die rekursive Definition übersetzt sich in eine Funktion:

def fib(n):
   '''verlangt eine natuerliche Zahl n'''
   if n==0 or n==1:
       return 1
   else:
       return fib(n-1)+fib(n-2)

Leider ruft diese Funktion für die meisten Argumente anschließend zweimal sich selbst auf, so dass es zu einem exponentiellen Wachstum von Speicherplatz und Laufzeit kommt. Nicht wirklich praktikabel.

Deutlich besser ist diese Funktion mit 'memoizing':

memo = {0:1, 1:1}
def fib(n):
   '''verlangt eine natuerliche Zahl n'''
   if n in memo:
      return memo[n]
   else:
      memo[n] = fib(n-1)+fib(n-2)
      return memo[n]
 

Aber auch diese scheitert irgendwann an der beschränkten Rekursionstiefe, d.h. (vereinfacht) der maximalen Zahl von Selbstaufrufen einer Funktion.

Am Ende ist eine unelegante Lösung, die eine Schleife verwendet, also eine iterative Lösung in diesem Fall besser:

def fib(n):
   if n==0 or n==1: 
      return 1
   else:
      a,b = 1,1 
      for i in range(n-1):
      a,b = a+b, a
   return a