根据数学推导容易得；
f
(
n
)
=
f
(
n
−
1
)
+
f
(
n
−
2
)
f(n) = f(n-1) + f(n - 2)
f(n)=f(n−1)+f(n−2)
如下直观写递归容易造成栈溢出。
#f(n) = f(n-2) + f(n-1)
n = int(input())
def helper(n):
if n == 0 : return 1
elif n == 1 : return 1
return helper(n - 1) + helper(n - 2)
print(helper(n))
原因分析：
每个helper函数调用运行则又有两个嵌套helper函数运行，如同细胞分裂，时间复杂度： O ( 2 n ) O(2^n) O(2n)
解决方案：
优化，尾递归思路，使时间复杂度降到 O ( n ) O(n) O(n)
n = int(input())
a, b = 0, 1
mod = 1e9+7
def helper(a, b, n):
if n == 0: return b
n -= 1
return helper(b, (a+b)%mod, n)
print(helper(a, b, n))
