1、概念
分治：分而治之
递归：自己调用自己
2、递归函数和函数调用栈
函数调用栈（栈帧）包含啥
参数
局部变量
返回地址
3、堆栈溢出和重复计算
堆栈溢出如何解决？
- 限制递归深度（主要是代码bug）
- 改用非递归实现
重复计算如何解决？
例如上图的 f(3) 被重复计算
- 备忘录（采用集合）
4、编写递归代码的技巧
怎么发现这个问题可以用递归来做？
- 规模更小的问题，跟规模大点的问题，解决思路相同、仅规模不同。
- 利用子问题的解可以组合得到原问题的解。
-
递归的正确编写姿势是什么样的？
我们可以假设子问题B、C已经解决在此基础上思考如何解决原问题A。
- 基于此，找递推公式+终止条件，然后翻译成代码。
注意：千万不要试图想清楚整个递和归执行过程，实际上是进入了一种思维误区。
5、递归时间和空间复杂度分析
时间复杂度
递归树-比较普适
递推公示-某些情况
空间复杂度
画出递归树，找高度
若有收获，就点个赞吧
0 人点赞
