计算机导论：递归结构及执行流程

2023-11-18 理论教育版权反馈

【摘要】：递归结构是算法中的另一种重复结构。下面仍然以查找问题和阶乘问题为例，给出递归结构算法的两个例子，然后以阶乘问题递归算法的执行过程为例，讨论递归结构算法的执行流程。的伪码形式的递归算法：PROCEDURE Factorial2{IFTHEN y＝1；ELSE y＝n*Factorial2（n－1）；}2.递归结构算法的执行流程用例6-4算法的执行过程讨论递归结构算法的执行流程。递归算法中的递归调用过程不能无休止的进行，任何递归算法都要考虑递归调用的结束条件，这称作递归出口。

递归结构是算法中的另一种重复结构。所谓递归算法，就是算法中存在调用自己本身的算法。下面仍然以查找问题和阶乘问题为例，给出递归结构算法的两个例子，然后以阶乘问题递归算法的执行过程为例，讨论递归结构算法的执行流程。

1.递归结构算法的设计

【例6-3】设计有序表的查找问题的文字形式的递归结构算法。

分析；所谓有序表，就是表中的数据元素已经排列有序。例如，假如一个表中有5个整数数据元素1，3，5，7，9，如果这5个整数的排列次序是{3，1，5，9，7}，则是一个无序表，如果这5个整数的排列次序是{1，3，5，7，9}，则是一个有序表。

对于有n个数据元素的有序表来说，查找表中是否存在一个数据元素为x的数据元素的查找过程可以如下：用数据元素x和有序表中的中间数据元素比较，如果数据元素x和该数据元素相同，则查找成功，查找过程结束；如果数据元素x大于该数据元素，则调用自身算法，此时只需考虑有序表中后半部分的数据元素；如果数据元素x小于该数据元素，则调用自身算法，此时只需考虑有序表中前半部分的数据元素。这样的查找过程一直进行到某次比较的表中的数据元素等于数据元素x（查找成功），或有序表为空，已无数据元素可供查找（查找失败）为止。这样的查找算法是一个不断调用自身算法的算法，所以这样的查找算法是一个递归结构的算法。由于该算法每次新的查找过程都只包含原有序表的一半，所以该算法也称作折半查找算法。

假设有序表为{1，3，5，17，18，31，33}，要查找的数据元素x等于18，则递归算法的查找过程如图6-5所示。第一次查找时，有序表为{1，3，5，17，18，31，33}，最中间的数据元素为17，比较结果是18大于17，所以算法调用自身继续进行。第二次查找时，有序表为{18，31，33}，最中间的数据元素为31，比较结果是18小于31，所以算法调用自身继续进行。第三次查找时，有序表为{18}，最中间的数据元素为18，比较结果是18等于18，所以查找成功，算法结束。

图6-5 递归算法查找成功过程示例

假设有序表为{1，3，5，17，18，31，33}，要查找的数据元素x等于30，则递归算法的查找过程如图6-6所示。第一次查找时，有序表为{1，3，5，17，18，31，33}，最中间的数据元素为17，比较结果是30大于17，所以算法调用自身继续进行。第二次查找时，有序表为{18，31，33}，最中间的数据元素为31，比较结果是30小于31，所以算法调用自身继续进行。第三次查找时，有序表为{18}，最中间的数据元素为18，比较结果是30不等于18，所以算法调用自身继续进行。第四次查找时，有序表为空，查找失败，算法结束。

图6-6 递归算法查找失败过程示例

下面给出使用了伪码IF-THEN-ELSE的文字形式的递归结构的查找算法：

（1）IF（有序表空）THEN查找失败，结束：

（2）ELSE取有序表最中间位置的数据元素；

（3）IF（x等于有序表最中间位置的数据元素）THEN查找成功，结束；

（4）ELSE

IF（x小于有序表最中间位置的数据元素）

THEN令新有序表为原有序表的前半部分，调用自身算法；

（5）ELSE令新有序表为原有序表的后半部分，调用自身算法。

【例6-4】设计计算阶乘n！问题的伪码形式的递归结构算法。

分析：n！可以表示为n×（n－1）！，即n！等于n乘以（n－1）！，其中，（n－1）！是和n！计算方法相同、仅具体数值（即参数）不同的计算方法。数值n不能无休止的递减，当n等于1时n！＝1，此时递归调用过程结束。计算阶乘问题的算法中存在调用自身算法的成分，因此，计算阶乘问题的算法是一个递归结构的算法。

下面给出计算阶乘n！的伪码形式的递归算法：(www.chuimin.cn)

PROCEDURE Factorial2（n）

{

IF（n＝＝1）THEN y＝1；

ELSE y＝n*Factorial2（n－1）；

}

2.递归结构算法的执行流程

用例6-4算法的执行过程讨论递归结构算法的执行流程。对于计算阶乘问题的递归算法，若要计算4！，则调用的参数n＝4，执行过程是：

（1）由于n＝4，条件n＝＝1不成立，所以执行y＝n*Factorial2（n－1），其中语句Factorial2（n－1）为递归调用。此时递归调用的参数为n－1，即新的调用参数为原调用参数减去1，所以新的调用参数为n＝3；

（2）由于n＝3，条件n＝1不成立，所以执行y＝n*Factorial2（n－1），其中语句Factorial2（n－1）为递归调用。此时递归调用的参数为n－1，即新的调用参数为原调用参数减去1，所以新的调用参数为n＝2；

（3）由于n＝2，条件n＝＝1不成立，所以执行y＝n*Factorial2（n－1），其中语句Factorial2（n－1）为递归调用。此时递归调用的参数为n－1，即新的调用参数为原调用参数减去1，所以新的调用参数为n＝1；

（4）由于n＝1，条件n＝1成立，所以执行y＝1，从而结束了递归调用过程。但是，前面每次的递归调用过程还没有执行完，需要继续执行：