从斐波那契的递归实现到通用递归函数的实现
def fibonacci(_target):
if _target == 0:
return 1
else
return fibonacci(_target - 1) + fibonacci(_target - 2)
pass
fibonacci(10)
从上述算法中我们知道，每进入一层递归，递归函数都会在调用自己两次。故此方法实现的 Fibonacci 函数对空间的使用是指数级增长的，并且由 Fibonacci 的公式:
f(n) = f(n - 1) + f(n - 2)
我们知道，在下一层计算中有
f(n - 1) = f(n - 2) + f(n - 3)
f(n - 2) = f(n - 3) + f(n - 4)