对科普不感冒的同学可以直接跳到后面进行阅读。

什么是递归与分治策略？

唠唠递归

直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。

讲讲分治

分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题（由于“平衡子问题”的思想，子问题规模应该都要大致相同），这些子问题相互独立且与原问题相同。递归地解这些子问题，然后将各个子问题的解合并得到原问题的解。

孪生兄弟？

分治和递归就像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。

为什么这么说呢？

因为由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。
在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而规模却不断缩小，最终使子问题缩小到很容易求出其解（往往称其为递归出口）。由此自然导致递归算法。

时间复杂度

将规模为n的问题分成k个规模为n/m的子问题去解所需的时间(n0是阈值)：

在讨论最坏情况下的计算时间复杂度时，用等号还是小于等于号没有本质区别。

为什么要用递归与分治策略？

因为任何可以用计算机求解的问题所需的计算时间都与其规模有关。问题规模越小，解题所需的计算时间往往也越少，从而也较容易处理。并且使用了递归技术往往使函数的定义定义和算法的描述简洁且易于理解。

怎么用递归与分治策略？

是不是有很多同学觉得：道理我都懂，可是我实在不会用啊。。。
干货来了——

前面讲到：分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题。

所以，最最最重要的就是找出递归关系，递归的定义问题的解。自顶向下的考虑问题。

下面，以Fibonacci数列为例：

科普：无穷数列1，1，2，3，5，8，······，被称为Fibonacci数列。即当前数为前两数之和。

于是，我们很简单就可以找出其递归关系式：

这个递归关系式，应该被分成两个部分来看：

1. 上两项为第一部分：这一部分被称为递归出口，因为递归算法就是要直接或间接的调用自身。算法要满足有穷性，不能无终止的运行下去。而且此时问题已经足够简单，我们不需要再对它进行分解了。
   
2. 最下面一项为一部分：这一部分就是递归的灵魂，我们将递归算法就是一直在直接或间接的调用自身，而这一部分就是在告诉我们如何调用，有什么要求。
   

所以根据这两部分，我们很容易就能写出程序：

• 所以，总结以上所讲述的内容，我可以知道：使用递归与分治策略时，我们首先要找出递归关系式，然后就可以根据递归关系式来编写程序了。

在哪用递归与分治策略？

要使用递归与分治策略，原问题就必须要能分解为相互独立且与原问题相同的子问题（如果不相互独立，即有重叠，则更适用动态规划算法。实则上述Fibonacci数列问题的子问题是有重叠的，但是仅为举例说明，所以读者无需过度纠结）。

举例说明：

1. Fibonacci数列：因为当前数为前两数之和，所以在求当前数的时候必须要求出前两数，因此此处可建立递归调用关系，并在递归出口结束调用。
2. 二分搜索技术：在有序数组中找一特定元素，使用二分搜索技术，判断中间位置是否为所寻数，如果所寻数比中间数小则在左边使用二分搜索算法，如果所寻数比中间数大则在右边使用二分搜索算法，此处则为递归调用。
3. ······

递归算法怎么运行？

递归调用的关键是为算法 建立递归调用工作栈。

• 在一个算法中调用另一个算法时，系统需要在运行被调用的算法之前先完成3件事：

1. 将所有实参指针、返回地址等信息传递 给被调用算法
2. 为被调用算法的局部变量分配存储区
3. 将控制转移到被调用算法入口

• 在从被调用算法返回调用算法时，系统相应地要完成3件事：

1. 保存被调用算法的计算结果
2. 释放分配给被调用算法的数据区
3. 依照被调用算法保存的返回地址将控制转移到调用算法

---

吃透！

OK，到这儿就结束了，你吃透了“递归与分治策略”吗？

关注博主，后续连载算法讲解······