#递归方法

def fibona(n):

    if n == 0:

        return 0

    elif n==1:

        return 1

    else:

        return fibona(n - 1) + fibona(n - 2)

#结果验证

print(fibona(18))  #2584

#用字典（diction)对象，保存计算过的值

def fib(n):

    diction = {0:0,1:1}

    if n in diction:

        return diction[n]

    else:

        for i in range(2,n+1):   #左闭右开

            diction[i] = diction[i-2] + diction[i-1]

    return diction[n]     #输出第n个数，return diction 就是整个字典

print(fib(30))     #832040