1.3 递归算法思想

因为递归算法思想往往用函数的形式来体现，所以递归算法需要预先编写功能函数。这些函数是独立的功能，能够实现解决某个问题的具体功能，当需要时直接调用这个函数即可。在本节的内容中，将详细讲解递归算法思想的基本知识。

1.3.1 递归算法基础

在计算机编程应用中，递归算法对解决大多数问题是十分有效的，它能够使算法的描述变得简洁而且易于理解。递归算法有如下3个特点。

①递归过程一般通过函数或子过程来实现。

②递归算法在函数或子过程的内部，直接或者间接地调用自己的算法。

③递归算法实际上是把问题转化为规模缩小了的同类问题的子问题，然后再递归调用函数或过程来表示问题的解。

在使用递归算法时，读者应该注意如下4点。

①递归是在过程或函数中调用自身的过程。

②在使用递归策略时，必须有一个明确的递归结束条件，这称为递归出口。

③递归算法通常显得很简洁，但是运行效率较低，所以一般不提倡用递归算法设计程序。

④在递归调用过程中，系统用栈来存储每一层的返回点和局部量。如果递归次数过多，则容易造成栈溢出，所以一般不提倡用递归算法设计程序。

1.4 分治算法思想

在本节将要讲解的分治算法也采取了各个击破的方法，将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。只要求出子问题的解，就可得到原问题的解。

1.4.1分治算法基础

在编程过程中，经常遇到处理数据相当多、求解过程比较复杂、直接求解法会比较耗时的问题。在求解这类问题时，可以采用各个击破的方法。具体做法是：先把这个问题分解成几个较小的子问题，找到求出这几个子问题的解法后，再找到合适的方法，把它们组合成求整个大问题的解。如果这些子问题还是比较大，还可以继续再把它们分成几个更小的子问题，以此类推，直至可以直接求出解为止。这就是分治算法的基本思想。

使用分治算法解题的一般步骤如下。

①分解，将要解决的问题划分成若干个规模较小的同类问题。

②求解，当子问题划分得足够小时，用较简单的方法解决。

③合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。