递归算法的设计模式与调试

2011-05-08陈宝平

电子科技 2011年9期

陈宝平

(内蒙古财经学院信息管理系，内蒙古呼和浩特 010070)

一个直接或间接调用自己的算法称为递归算法。递归是软件设计中的重要方法和技术，其省略了程序设计中的许多细节操作，简化了程序设计过程，递归函数结构清晰，程序易读[1]。因此，在许多实际问题求解时，采用递归方法要比非递归方法容易实现，特别是在解决树、图等问题过程中得到了广泛应用[2-4]。在计算机科学中，许多数据结构都是通过递归方式加以定义的，由于其本身固有的递归性质，因而关于它们许多问题的算法均可以采用递归技术加以实现;另外，还有一些问题虽然本身没有明显的递归特征，但可以利用递归技术设计出简单高效的算法程序。递归问题一般采用分治法解决，分治法的设计思想是:将一个难以解决的大问题，分割成一些规模较小的相同问题，以便逐个击破，分而治之。文中在分治的基础上，进一步细化，提出递归算法的模型，并通过一些比较经典的实例加以说明。另外，递归问题在求解的过程中，如果有错，程序会中断，并出现“栈溢出”或“执行了非法操作”等信息，这些信息一般是在递归算法的某一过程中出现，调试难度较大，文中提出使用设置断点单步跟踪及打印变量等方法调试。

1 递归算法的设计模式

“自重复”是递归算法所具有的重要特征，对任何递归问题，都有向前递推和向后回退两个过程，把握这两个过程中的关键思维及其终点和起点至关重要。一般用于递归解决的问题都是有规模，有边界条件的，当规模较大时，反复采用分治法手段，可以使子问题与原问题一致，而其规模却不断缩小，最终使得子问题达到边界的条件，从而很容易求出解。根据递归问题的特点，可设计递归算法的步骤如下:

(1)找递归出口也即边界条件。对于一个递归算法而言，递归出口非常重要，它是递归的终止条件。有的算法边界条件很明显，例如Hanoi塔问题，盘子数为1时，不需要递归。有的算法边界条件不明显，此时可以先进行步骤(2)和步骤(3)等，根据参数判断特殊情况，例如整数划分问题。

(2)把一个规模较大的问题分解为一个或若干规模较小的相似子问题。对于定义本身就是递归的问题，定义中就包含分治过程，如树结构、图结构、Fibonaci数列等，分解过程很容易。可是对于没有明显的递归特征，但需要用递归来解决的问题如Hanoi塔问题、迷宫问题等，需要编程者自己设计递归过程。例如Hanoi塔问题，原问题是将64个盘子从a柱借助b柱移到c柱，可将64个盘子问题分解为最大盘子和其余63个盘子的问题。

(3)定义递归过程。原问题与子问题一般功能相同，只是规模或作用的对象不同，将相似的部分定义为递归过程，例如Hanoi塔问题，原问题和子问题都为从3根柱子上移盘子，因此将移盘子定义为递归Hanoi函数。原问题与小问题中盘子的个数以及3根柱子所承担的作用不同，故将3根柱子和盘子数n作为Hanoi函数参数。最后在确定是否需要返回值，Hanoi塔问题只需知道移盘子的顺序，无需返回值。因此Hanoi塔问题的递归函数定义应该为:void Hanoi(int n，char x，char y，char z)，其中x，y，z表示3根柱子。

(4)合成解。可以进一步推导出递归算法的设计模式:

其中，“将问题规模N分解为n1，n2，…，nk”，有时可以通过算法实现，有时直接将N分解即可，不需要调用算法。经过大量实践证明，最好是每个子问题的规模大致相同，即将一个问题分成大小相等的k个子问题。同样“合并所有的子问题”，需根据具体的情况而定，有的算法只要将各个子问题分布处理后，原问题也随之解决，这种情况就不需要合并子问题。将以上三步合成到递归模式中，即可写出程序。

2 实例

递归问题一般有3种:问题定义本身是递归的、数据结构是递归的和用递归解决问题。用递归解决问题，选出3个经典的递归算法，说明以上理论。

2.1 Hanoi问题的解法

Hanoi塔问题的求解是讲解递归程序时的一个经典示例。根据递归的基本四步和递归的模式，可以得到其程序。

Hanoi塔问题中，不需要合并子问题的结果，即可求解。

2.2 快速排序问题的解法

快速排序的原问题是:对数组R[1]，R[2]，…，R[n]排序。

(1)若n为0或1，则无需排序。

(2)否则需要将原问题分解，先经过一趟分割使得数组中的R[pos]有序，随之大问题被分割出两个子问题，子问题一:R[1]，R[2]，…，R[pos-1]排序，子问题二:R[pos]，R[pos+1]，…，R[n]排序。

(3)原问题和子问题相似的是给R数组排序，不同的是范围，另外排序无需返回值，因而定义函数void QuickSort(ElemType R[]，int low，int high)。

(4)根据以上分析及递归模式可以写出快速排序的算法。

2.3 整数划分问题的解法

将整数n表示成一系列正整数之和，n=n1+n2+…+nk，其中n1≥n2≥…≥nk≥1，k≥1。正整数的这种表示法称为正整数n的划分。正整数n的不同划分个数称为正整数 n的划分数，记作p(n)，求p(n)。

(1)此问题的边界条件不明显，因此先分解。

(2)正整数n的分解式可能有很多，可以将其分成两类:分解式中包含m与分解式中不包含m的，其中最大加数n1≤m。

(3)原问题与子问题相同的是求正整数n的划分，不同的是n值与m值，另外还需返回分解式的个数，故函数可以定义:int divide_integer(int n，int m)。显然原问题可以设计为divide_integer(n，n)，两个子问题分别设计为divide_integer(n-m，m)和divide_integer(n，m-1)。此时再分析边界情况:若m=1，则 divide_integer(n，1)=1;若 m＞n，则divide_integer(n，m)=divide_integer(n，n)。

(4)合成程序如下所示:

3 递归算法的调试

递归算法的特点是，表面上程序代码简单，但在实际执行流程中，语句执行顺序频繁跳跃，难觅规则，尤其是结果不正确或代码在运行过程中断，这样的错误很难调试。此时需在代码中设计断点，使用单步执行，观察各个变量值、观察函数调用栈等。使用单步跟踪技术时，递归算法与非递归算法不同之处在于，递归算法用到了工作栈，因此需要使用模拟栈。模拟栈一般遵循的规则是:递归调用需要将参数、局部变量、执行语句的地址等压栈;递归结束相关数据出栈，并且程序跳回栈中所指的地址。也可在程序中增加若干输出语句，输出某些变量的值，以此验证程序的执行效果。

递归程序在执行过程中，有时会因“栈溢出”而中断，此类问题可从以下几个方面检查。一是看边界条件是否考虑齐全，如整数规划问题，边界有4种情况，缺一不可。二是检查数据量，如果数据量过大，也会造成栈溢出，例如快速排序当需排序的数据达到100万时，就会出现栈溢出的现象，此时可以适当调整数据的大小。总之递归算法的调试难度较大，需要积累经验。