生活中的递归与分治
“你站在桥上看风景，看风景的人在楼上看你，明月装饰了你的窗子，你装饰了别人的梦。”——卞之琳《断章》
上面这首诗包含了一个递归的概念。生活中无处不是递归~
递归又常常与算法里面且难以避免的另一个重要概念“分治”（分而治之）紧密联系。事实上，递归在很多时候就是因为分治策略的使用才出现的，可以说没有递归，就没有分治。
分治法可能是最著名的通用算法设计技术了。虽然它的名气可能和它那好记的名字有关，但它的确是当之无愧：因为很多有效的算法实际上就是这个通用算法的特殊实现。
分而治之是一个非常重要的战略：
- 战国时期纵横之术就使得秦国通过合纵连横的分治策略而统一了当时的六国（具体措施：笼络燕齐，稳住魏楚，消灭韩赵；远交近攻，逐个击破。）秦国，就是在与六国连横的过程中，一方面击破了合纵，另一方面不断深挖本国的潜能，使国家不断的富强，最终取得了统一霸业的伟大胜利。
- 在 LPL 游戏比赛中，为了选出最强的的四支队伍去参加世界赛，所有的队伍都进行对抗会使得赛程太久，成本很高。所以通过分治的策略：首先将不同的战队分为上下半区，从每个半区通过 BO5 淘汰赛来选出最优秀的战队。又加入了胜者组合败者组的复活赛，最后通过决赛角逐出一只最顶尖的队伍成为世界赛 1 号种子。
说完上面这些之后，我们来看看正式一点的概念。
分治算法概念与步骤
定义：分治算法（Divide and Conquer）：字面上的解释是「分而治之」，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
算法步骤：
- 分解：将一个问题划分为同一类型的若干个子问题，子问题最好规模相同
- 求解：对这些子问题求解（一般使用递归方法，但在问题规模足够小时，也会使用其他算法）
- 合并：如果还需要，合并子问题的解，以得到原始问题的答案
用图来表示的话，如下
其中，第二步递归解决子问题就是按照同样的分治策略进行求解，通过将这些子问题分解为更小的孙子问题进行求解。直到分解出来的子问题简单到只用常数操作时间即可解决为止。
其对应的伪代码如下：
def divide_and_conquer(problem): # problem 为问题规模 if problem < d: # 当问题规模足够小时，直接解决该问题 return solove(); # 直接求解 k_problems = divide(problem) # 将问题分解为 k 个相同形式的子问题 res = [0 for _ in range(k)] # res 用来保存 k 个子问题的解 for k_problem in k_problems: res[i] = divide_and_conquer(k_problem) # 递归的求解 k 个子问题 ans = merge(res) # 合并 k 个子问题的解 return ans # 返回原问题的解
分治算法的适用条件
分治算法能够解决的问题，一般需要满足以下 4 个条件：
- 原问题可以分解为若干个规模较小的相同子问题。
- 分解出来的子问题可以独立求解，即子问题之间不包含公共的子子问题。
- 具有分解的终止条件，也就是说当问题的规模足够小时，能够用较简单的方法解决。
- 子问题的解可以合并为原问题的解，并且合并操作的复杂度不能太高，否则就无法起到减少算法总体复杂度的效果了。
