# -*- coding: UTF-8 -*-
# 作者：幻灰龙
# 标题：Python 函数+缓存
# 描述：递归计算斐波那契函数, 带缓存

def fibonacci_inner1(n, cache):
    if n == 1 or n == 2:
        cache[0] = 1
        cache[1] = 1
        return 1

    if cache.get(n) is None:
        fibonacci_inner1(n-2, cache)
        fibonacci_inner1(n-1, cache)
        cache[n-1] = cache[n-2]+cache[n-3]

    return cache[n-1]


def fibonacci1(n):
    return fibonacci_inner1(n, {})


if __name__ == '__main__':
    print(fibonacci1(10))