01-递归算法

第12章　递归算法

递归就是自己调用自己，它是设计和描述算法的一种有力的工具，常常用来解决比较复杂的问题。递归是一种分而治之、将复杂问题转换为简单问题的求解方法。一般情况下，能采用递归描述的算法通常有以下特征：为求解规模为N的问题，设法将它分解成规模较小的问题，从小问题的解更容易构造出大问题的解，并且这些规模较小的问题也能采用同样的分解方法，分解成规模更小的问题，并能从这些更小问题的解构造出规模较大问题的解。一般情况下，规模N=1时，问题的解是已知的。

以上求解过程也利用了分治算法的思想。分治算法将一个大规模问题分解为若干子问题，子问题相互独立，然后将子问题的解合并就可得到原问题的解。分治算法具体可以使用递归实现。

递归算法具有以下优缺点。

• 优点：使用递归编写的程序简洁、结构清晰，程序的正确性很容易证明，不需要了解递归调用的具体细节。
• 缺点：递归函数在调用过程中，每一层调用都需要保存临时变量、返回地址、传递参数，因此递归函数的执行效率低。