# coding:utf-8
def fib(n):
    """公式法"""
    from math import sqrt, pow
    return int(1/sqrt(5)*(pow((1+sqrt(5))/2,n) - pow((1-sqrt(5))/2,n)))
def fib2(n):
    """累加，使用之前计算的数"""
    if n == 0:
        return 0
    elif n == 1:
        return 1
    firstnum = 0
    secondnum = 1
    fibnum = 0
    cnt = 1
    while cnt < n:
        fibnum = firstnum + secondnum
        firstnum ,secondnum = secondnum, fibnum
        cnt += 1
    return fibnum
def fib3(n):
    """列表计算追加，简洁"""
    begin = [1, 1]
    for count in xrange(1, n-2):
        begin.append(begin[-1]+begin[-2])
    return begin
def fib4(n):
    """递归计算"""
    if n <= 1:
        return n
    else:
        return fib4(n - 1) + fib4(n - 2)
# fib1 fib2 fib4
for i in range(1, 10):
    print fib4(i)
# fib3
print fib3(10)