递归

斐波那契数列

1 1 2 3 5 8 13 21...

从第三个数开始 后面的数是前2个数之和

什么情况可以用递归: 

1.一个问题可以分解为几个子问题

2.这个问题和分解后的子问题,求解思路完全一样

3.最终肯定有一个确定的答案,即终止递归的条件

斐波那契数列递归实现

如何优化?

1.改为循环,理论上所有递归都可以改写为循环

2.将结果缓存,降低中间重复计算

3.尾递归 

尾递归就是调用函数一定出现在末尾 没有任何其他操作了,编译器在编译代码时，如果发现函数末尾已经没有其他操作了 这时就不会创建新的栈 而是覆盖到前面去