748 字
4 分钟
学习笔记-1-递归&分治
递归
概念
递归，在数学和计算机科学中是指在函数的定义中使用函数自身的方法，在计算机科学中还额外指一种通过重复将问题分解为同类的子问题而解决问题的方法。
本质
递归的实质就是直接或间接调用自身函数，将原问题转化为性质相同规模不同的子问题。
递归代码最重要的两个特征：结束条件和自我调用。自我调用是在解决子问题，而结束条件定义了最简子问题的答案。
主要格式
int func(传入数值) { if (终止条件) return 最小子问题解; return func(缩小规模);}要点
什么情况应该使用递归？
当问题可以被分解为成相同结构的小问题时，我们就可以使用递归来求解。
缺点
1.容易栈溢出
2.可能会超时，耗时间，需要优化。
注意
写递归程序时，**明白一个函数的作用并相信它能完成这个任务，千万不要跳进这个函数里面企图探究更多细节。**否则可能陷入无限的细节中无法自拔（引用自Oi Wiki）
分治
概念
分治（英语：Divide and Conquer），字面上的解释是「分而治之」，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
过程
核心思想：「分而治之」 大致分为三步：分解 -> 解决 -> 合并。
- 分解原问题为结构相同的子问题。
- 分解原问题为结构相同的子问题。
- 将子问题的解合并成原问题的解。
特征
- 分解原问题为结构相同的子问题。
- 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质，利用该问题分解出的子问题的解可以合并为该问题的解。
- 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 注意 如果子问题不独立，分治法要重复多次来求解公共的子问题，做了许多不必要的工作，这种情况一般使用动态规划（这里应该有个链接）较好。
区别
递归和枚举的区别在于：枚举是横向地把问题划分，然后依次求解子问题；而递归是把问题逐级分解，是纵向的拆分。
递归与分治的区别
递归是一种编程技巧，一种解决问题的思维方式；分治算法很大程度上是基于递归的，解决更具体问题的算法思想。
习题
学习笔记-1-递归&分治
https://blog.introl.top/posts/学习笔记-1-递归及递推/