递归与循环
斐波那契数列
大家都知道斐波那契数列,现在要求输入一个整数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)具体解释如
1