『数学ガール』4-2-5の解答4-1（フィボナッチ数列の一般項）をPythonで

積読状態の『数学ガール』をいまさら読み始めたのでなんとなく。

解答4-1（フィボナッチ数列の一般項）

from math import sqrt
def fib(n):
    return int(1 / sqrt(5) * (((1 + sqrt(5)) / 2) ** n - ((1 - sqrt(5)) / 2) ** n))
print [fib(i) for i in range(10)] #-> [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

ちなみにsicpでやった時のもの

Structure and Interpretation of Computer Programs

#recursive
def fib(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fib(n - 1) + fib(n - 2)
print [fib(i) for i in range(10)] #-> [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

#iterative
def fib(n):
    return fib_iter(1,0,n)
def fib_iter(a,b,count):
    if count == 0:
        return b
    return fib_iter(a + b, a, count - 1)
print [fib(i) for i in range(10)] #-> [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]