数据结构与算法（第二季）：递归、回溯
2022-01-14 本文已影响0人
萧1帅
递归（Recursion）
一、概念
- 函数（方法）直接或间接调用自身。
image
二、递归现象
image
三、函数的递归调用过程
- 如下一段函数调用：
image
- 实际在栈中的调用过程：
image
image
- 如果递归调用没有终止，将会一直消耗栈空间，最终导致栈内存溢出（Stack Overflow），所以要
明确一个结束的递归条件，也叫做边界条件。
四、实例分析
- 求
1+2+3+...+ (n-1)+n的和，(n>0)
image
- 如果将递归转化为
非递归函数，那么通常复杂度会得到优化。
image
- 使用递归不一定是为了获得最优解，而是为了简化解决问题的思路，代码会更简洁。
五、递归的基本思想
- 拆解问题
- 把规模大的问题变成规模较小的同类型问题。
- 规模较小的问题又不断变成规模更小的问题。
- 规模小到一定程度可以直接得出它的解。
image
- 求解
- 由最小规模问题的解得出较大规模问题的解。
- 由较大规模问题的解不断得出规模更大问题的解。
六、递归的使用套路
- 明确函数的功能，先不要思考代码怎么写，而是搞清楚这个函数的作用。
- 明确原问题与子问题的关系，即寻找f(n)与f(n-1)的关系。
n + sum(n-1) - 明确边界条件，相当于思考问题规模小到什么程度可以直接得出解。
（n<=1）
image
七、练习
image
image
- 此种方法会超时，所以需要优化。
image
