递归
2022-09-30 本文已影响0人
春去春又来花谢花会开
斐波那契数列
1 1 2 3 5 8 13 21...
从第三个数开始 后面的数是前2个数之和
什么情况可以用递归:
1.一个问题可以分解为几个子问题
2.这个问题和分解后的子问题,求解思路完全一样
3.最终肯定有一个确定的答案,即终止递归的条件
斐波那契数列递归实现
如何优化?
1.改为循环,理论上所有递归都可以改写为循环
2.将结果缓存,降低中间重复计算
3.尾递归
尾递归就是调用函数一定出现在末尾 没有任何其他操作了,编译器在编译代码时，如果发现函数末尾已经没有其他操作了 这时就不会创建新的栈 而是覆盖到前面去
