软件设计师考试 | 第八章 算法设计与分析 | 分治法

（一）递归的概念

递归是指子程序直接调用自己或通过一系列调用语句间接调用自己，是一种描述问题和解决问题的常用方法。

递归的两个基本要素：

• 边界条件
  确定递归到何时终止，也称为递归出口。
• 递归模式
  大问题是如何分解为小问题的，也称为递归体。

（二）分治法的基本思想

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

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

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

1. 分解，将原问题分解成一系列子问题。
2. 求解，求解各子问题。
3. 合并，将子问题的解合并成原问题的解。

（三）分治法的典型实例

典型案例有：归并排序，最大子段和问题等。

其中，归并排序的思路是：

1. 分解，将n个元素分成各含有n/2个元素的子序列。
2. 求解，用归并排序对两个子序列递归地排序。
3. 合并两个已经排好序的子序列以得到排序结果。