フィボナッチ数列

ブクマコメントでフィボナッチという声があったので書いた。

def fib1(n):
    if n < 2:
        return 1
    return fib1(n - 1) + fib1(n - 2)

print [fib1(n) for n in range(10)]
# => [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

def fib2(n):
    x, y = 1, 1
    for i in range(n):
        x, y = y, x + y
    return x

print [fib2(n) for n in range(10)]
# => [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]     

最初に貼ったときに x + y が x + 1 になっていたのにテストコードもfib2にすべきところがfib1になっていてミスに気づかなかったのは秘密だ。