Fibonacci-Folge

Eine kleine Aufgabe für zwischendurch ist die Programmierung einer Funktion, die die Fibonacci-Folge bzw. das Element n dieser Folge ausgibt.

Rekursive Umsetzung

Hier eine rekursive Umsetzung, die auf meinem System für den Zahlenraum bis etwa 30 einigermaßen flott unterwegs ist, sich anschließend aber festfährt:

def fib(n):
    ''' Rekursive Funktion, die fuer eine Ganzzahl n
    die Fibonacci-Zahl zurueckgibt

    '''
    if n < 2:
        return n
    else:
        return fib(n-2) + fib(n-1)



for i in range(0,100):
    print(i,fib(i))

Eine zweite Umsetzung

Bei diesem Skript, befüllt die Funktion eine Liste und nutzt sie für die Berechnung. Nachteil ist, dass die Liste bei jedem Funktionsaufruf neu erzeugt werden muss, was nicht sehr sinnvoll ist. Das Skript wirkt zunächst recht performant:

def fib(n):
    ''' Rekursive Funktion, die fuer eine Ganzzahl n
    die Fibonacci-Zahl zurueckgibt

    '''
    fibfolge = [0,1,1]
    if n < 2:
        return n
    else:
        for i in range(2,n+1):
            result = fibfolge[i-1] + fibfolge[i]
            fibfolge.append(result)
        return result

Man beachte den Artikel „Fibonacci numbers (Python)“ im LiteratePrograms-Wiki.