递归

直接或者间接不断反复调用自身来达到解决问题的方法。要求原始问题可以分解为相同问题的子问题。

先决条件

• 递归边界
• 自身调用

特点
思路简单清晰，如果分析出将很快得到结果;递归将多次调用，使用到堆栈，算法效率低，费时费内存。

常用场景

• 阶乘
• 斐波纳契数列
• 汉诺塔问题
• 整数划分
• 枚举排列及二叉树
• 图的搜索相关问题。

分治

把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

基本思想
将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

策略
对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。

使用场景

• 问题的规模缩小到一定的程度就可以容易地解决
• 问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质
• 问题分解出的子问题的解可以合并为该问题的解
• 问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。

基本操作步骤
分治法在每一层递归上都有三个步骤：

• 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题
• 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题
• 合并：将各个子问题的解合并为原问题的解

常用场景

• 二分搜索
• 大整数乘法
• Strassen矩阵乘法
• 棋盘覆盖
• 合并排序
• 快速排序
• 线性时间选择
• 最接近点对问题
• 循环赛日程表
• 汉诺塔