- 零基础学算法（第4版）
- 张昆 戴艳
- 2890字
- 2025-02-25 05:17:50
1.5 递归算法思想
递归算法也是一种很常用的算法思想，使用该算法有时可有效地解决一些问题，往往可以简化代码的编写，提高程序的可读性。但若有不合适的递归，反而会导致程序的执行效率变低。
1.5.1 算法思路
所谓递归算法，就是在程序中不断反复调用自身来求解问题的方法。这里强调的重点是调用自身，就得等待求解的问题能够分解为相同问题的一个子问题，这样通过多次递归调用，自己便可完成求解。
递归算法的具体实现过程一般通过函数（或子过程）来完成，在函数（或子过程）的内部，编写代码直接或者间接地调用函数（或子过程）自己，即可完成递归操作。这种函数也称为“递归函数”。在递归函数中，主调函数同时又是被调函数。执行递归函数将反复调用其自身，每调用一次就进入新的一层。
编程经验 把求解问题转化为规模缩小了的同类问题的子问题，然后递归调用函数（或子过程）来表示问题的解，通过多次递归调用，最终可求出最小问题的解，然后通过这个最小问题的解返回上层调用，再求出次小问题的解，再返回上层调用，不断重复，最终得到整个问题的解，完成递归操作。
从递归算法的实质可以看出，递归算法也是一种循环，只是这种循环不是使用程序设计语言的循环语句来实现，而是循环调用函数（或子过程）自身来实现的。要实现这种递归循环，一般有三个要求：
·每循环调用一次，求解问题的规模都要有所缩小，即将求解的问题化为一个缩小了的子问题；
·相邻两次循环之间有紧密的联系，前一次要为后一次做准备（通常前一次的输出就作为后一次的输入）；
·当子问题的规模极小时，应该能直接给出解答而不再进行递归调用（即必须有一个结束递归的条件），因而每次递归调用都是有条件的，无条件递归调用将会使程序进入死循环而不能正常结束（最终导致栈溢出）。
由以上递归算法的要求可以看出，在使用递归算法解决问题时，需要注意以下几点：
·在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。
·递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。
·在递归调用的过程中，系统将每一次递归调用的返回点、局部变量（临时变量）等保存在系统的栈中，当递归调用的次数太多时，就可能造成栈溢出错误。
1.5.2 实例：求阶乘
理解递归算法最简单的例子就是：编写程序求n的阶乘（n！）。所谓阶乘，就是从1到指定数之间的所有自然数相乘的结果，或者说阶乘就是从数n到1之间的所有自然数相乘的结果，可写为以下算式：
n!=n*(n-1)*(n-2)*…*2 * 1
例如，6的阶乘为：
6*5*4*3*2*1=720
由阶乘的算式可看出，阶乘运算可以直接使用循环来完成，也可以使用递归来进行计算。可以将n的阶乘分解为以下算式：
n!=n*(n-1)!
即n的阶乘等于n乘以n-1的阶乘。
同样，又可将n-1的阶乘分解为n-1乘以n-2的阶乘，算式如下：
(n-1)!=(n-1)*(n-2)!
则
n!=n*(n-1)*(n-2)!
这样，当将变量n逐步减小，到1时，就完成了递归操作，也就有了结束递归的条件。因此，可以使用递归算法来编写求阶乘的代码。
编程经验 像这种“将问题化为一个缩小了的子问题”的情况，就构成了递归调用，程序就可考虑使用递归算法来编写。
具体代码如下：
【程序1-6】使用递归算法计算阶乘
1 #include <stdio.h>
2 int fact(int n); //函数声明
3 int main()
4 {
5 int i; //声明变量
6 printf("请输入要求阶乘的一个整数:");
7 scanf("%d",&i); //输入数据
8 printf("%d的阶乘结果为:%d\n",i,fact(i)); //调用函数
9 getch();
10 return 0;
11 }
12 int fact(int n) //求阶乘函数
13 {
14 if(n<=1)
15 return 1;
16 else
17 return n*fact(n-1); //递归
18 }
【程序说明】
·第3~11行为主函数，要求用户输入需要求阶乘的一个整数，然后调用fact函数来计算结果。
·第12~18行为计算阶乘的函数fact，在该函数内部第17行调用函数fact自身，构成递归调用，而第14、15行判断递归的结束条件。
编译执行以上程序，输入整数6，可得到阶乘结果为720，如图1-9所示。
图1-9 【程序1-6】执行结果
分析函数fact的运行过程。当输入n=6时，其计算过程如下。
首先，在第8行使用printf函数调用fact（6），引起第1次函数调用。进入函数fact后，实参n=6，应执行计算6*fact（5）。
为了计算fact（5）的值，引起对fact函数的第2次调用（进入递归调用），重新进入函数fact。这时，实参n=5，应执行计算5*fact（4）。
就这样逐步重复上一步，一直计算到n=1，为了计算fact（1），引起对函数fact的第6次调用（递归调用），重新进入函数fact。这时，实参n＝1，根据第14行程序进行判断，n≤1时，函数fact（1）=1，这时，将返回第5次调用层。
在第5次调用层中计算执行2*fact（1），因为fact（1）在上一次中返回的结果为1，所以，这里的算式应该是2*1，即fact（2）=2，然后返回第4次调用层。
在第4次调用层中计算执行3*fact（2），因为fact（2）在上一次中返回的结果为2，所以，这里的算式应该是3*2，即fact（3）=6，然后返回第3次调用层。
就这样逐步向上层调用返回，最后返回到第1次调用层中，计算执行6*fact（5），因为fact（5）在上一次中返回的结果为120，所以，这里的算式应该是6*120，即fact（6）=720。到达第1层时，递归调用已全部完成，这时，函数将返回其主调用函数printf中，由printf函数输出其计算结果。
以上文字描述看起来很复杂，可参考图1-10，更详细地了解递归的过程。
图1-10 递归调用过程
编程陷阱 对于本例程序，算法是没有错的，但如果输入1000，即求1000的阶乘，将得到一个什么结果？这时，由于阶乘的结果已经超过int型变量的表示范围，因此将得到一个错误的结果。即使使用更大表示范围的变量类型，也会超过其表示范围。
1.5.3 实例：数制转换
在计算程序中，经常需要使用各种进制的数据，这就需要对数制进行转换。
将十进制整数转换为其他进制整数的计算过程是：将十进制数除以相应数制的基数，取其余数作为相应数制的最低位，再用商除以相应数制的基数，取余数作为相应数制的次低位……这样不断重复，即可完成转换。
这样描述可能概念上还有点模糊，下面以常用的二进制为例，看看相应的转换过程。
将十进制数转换为二进制数时，使用除以2取余法，即将十进制数除以2，取其余数为相应二进制数最低位，用商再除以2得到次低位……直到最后一次相除商为0时得到最高位。
例如，将十进制数121转换为二进制数的过程如下：
通过以上的算式计算，可得出：
（121）10=（1111001）2
即十进制数121转换为二进制数为1111001。
通过以上的竖式可以得出两点：
·数制转换的过程是数据逐步变小的过程，即构成了递归调用中的“将问题化为一个缩小了的子问题”的特点。
·在数制转换过程中有递归的结束条件，即当商为0时结束递归过程。
因此，可以将数制转换的过程用递归算法来实现，下面是实现这种算法的C程序。
【程序1-7】使用递归算法设计数制转换程序
1 #include <stdio.h>
2 #include <string.h>
3 void convto(char *s, int n, int b) //函数声明
4 {
5 char bit[]={"0123456789ABCDEF"};
6 int len; //声明变量
7 if(n==0)
8 {
9 strcpy(s,""); //字符串复制
10 return;
11 }
12 convto(s, n/b, b); //递归
13 len = strlen(s); //获取字符串长度
14 s[len] = bit[n%b];
15 s[len+1] = '\0';
16 }
17
18 void main(void) //主函数
19 {
20 char s[80];
21 int i, base,old;
22 printf("请输入十进制数:");
23 scanf("%d",&old);
24 printf("请输入转换的进制:");
25 scanf("%d", &base);
26 convto(s, old, base); //对数制转换
27 printf("%s\n", s);
28 getch();
29 return;
30 }
【程序说明】
·第3~16行为递归调用函数，在该函数中使用了3个参数，第1个参数为一个字符串s，用来保存转换后的结果；第2个参数n是需要转换的数；第3个参数b是需要转换的进制。
·第12行调用函数自身，构成递归调用。
·第18~30行为主函数，让用户输入需要转换的十进制数和需要转换的进制。第26行调用convto函数进行数制转换。
编译执行程序，可得到如图1-11所示的结果。
图1-11 【程序1-7】执行结果