剑指offer算法python版

递归与循环 斐波那契数列 大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0)。n<=39 解题思路:找规律 设函数f(n) 当 n=0时 f(0) =0 当 n=1时 f(1) =1 当 n=2时 f(2) =1 当 n=3时 f(3) =2 当 n=4时 f(4) =3 当 n=5时 f(5) =5 当 n=6时 f(6) =8 可以推出当 n ≥\ge≥ 2 :f(n) = f(n-1) + f(n-2) 解法一:使用递归方法进行求解会发现,时间和空间复杂度大,大于10就容易内存溢出,时间复杂度为O(2n2^n2n)具体