递归 & 分治
递归¶
介绍分治之前，首先要弄清楚递归这个概念。
递归是什么呢？举个简单的例子：从前有座山，山上有座庙，庙里有个老和尚，老和尚给小和尚讲故事：“从前有座山，山上有座庙，庙里有个老和尚，老和尚给小和尚讲故事：‘从前有座山……’”这个故事与递归算法有着异曲同工之妙。
递归的基本思想是某个函数直接或者间接地调用自身，这样就把原问题的求解转换为许多性质相同但是规模更小的子问题。我们只需要关注如何把原问题划分成符合条件的子问题，而不需要去研究这个子问题是如何被解决的。
递归和枚举的区别在于：枚举是横向地把问题划分，然后依次求解子问题，而递归是把问题逐级分解，是纵向的拆分。
递归三要素¶
在用递归思想解题的时候，要考虑三个要素。
递归式¶
如何将原问题划分为子问题？如何科学地进行递归？
递归出口¶
终止的条件是什么？换言之，最小的子问题是怎么求解的。
出口可以不止一个。
界函数¶
我们用一个函数来表示问题规模变化，这个函数需要保证递归的条件是在向出口条件靠拢。
递归模板¶
1 2 3 4 | int f(传入数值) { if (终止条件) return 最小子问题解; return f(缩小规模); } |
递归优化¶
先来一道例题：三连击。
这道题朴素的递归写法只能得到 25 分，因为递归次数太多，所以超时。
分治¶
分治是一种极为重要的思想。顾名思义，分而治之，就是把大问题化小，再各个击破的过程。
英文名是 divide and conquer.
例题
求数列中有多少个逆序对，所谓逆序对，是满足 而且 的数对 的个数。
考虑把数列等分成两部分，那么原数列的逆序对有两种情况：一种是两个数完全包含在某一侧的子数列中，另一种是两个数一左一右被分开了。
不难发现前者只需要递归地求出，后者只需要对于左侧的每个数，统计右侧有多少个比它小的。
build本页面最近更新：，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用