Mathesis Wiki

Diese Seite ist nicht editierbar. Sie können den Quelltext sehen, jedoch nicht verändern. Kontaktieren Sie den Administrator, wenn Sie glauben, dass hier ein Fehler vorliegt.

===== Fibonacci =====

Die rekursive Definition übersetzt sich in eine Funktion:

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

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':
<code python>
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]
       
</code>

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:

<code python>
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
   
</code>

Mathesis Wiki

Benutzer-Werkzeuge

Webseiten-Werkzeuge

Seiten-Werkzeuge