2-递归-效率提升-空间换时间-计算斐波那契数列第n项

# 递归调用是函数调用自己，在计算机中，函数调用是通过栈（stack）这种数据结构实现的，每当进入一个函数调用，
# 栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以，递归调用的次数过多，会导
# 致栈溢出。大多数编程语言没有针对尾递归做优化，Python解释器也没有做优化
# 在导致栈溢出前，此种以空间换时间的方法基本都是秒算。
import time


def fibonacci_v2(n, record):
    if n == 1:
        # 每次运算结束都记录对应的结果
        record[0] = 0
        return 0
    elif n == 2:
        # 每次运算结束都记录对应的结果
        record[1] = 1
        return 1
    else:
        if record[n-1] > 0:
            # 如果已经有记录结果，不再计算，直接取记录值
            return record[n-1]
        else:
            temp = fibonacci_v2(n-1, record) + fibonacci_v2(n-2, record)
            # 每次运算结束都记录对应的结果
            record[n-1] = temp
            return temp


if __name__ == '__main__':
    start = time.time()
    # [0]*50记录每一次计算的值
    print(fibonacci_v2(500, [0]*500))
    end = time.time()
    print(f'用时{end-start}秒')