下载掌阅APP，畅读海量书库
立即打开
在学习C语言的过程中递归是C语言的重点和难点。在数据结构与算法实践过程中，经常会遇到利用递归实现算法的情况。递归是一种分而治之、将复杂问题转换为简单问题的求解方法。使用递归可以使编写的程序简洁、结构清晰，程序的正确性很容易证明，不需要了解递归调用的具体细节。
本节主要介绍函数的递归调用、如何使用递归巧妙解决看上去比较复杂的问题。
简单来说， 函数的递归调用就是自己调用自己 ，即一个函数在调用其他函数的过程中，又出现了对自身的调用，这种函数称为递归函数。函数的递归调用可分为直接递归调用和间接递归调用。其中，在函数中直接调用自己称为函数的 直接递归调用 ，如图2-18所示；如果函数f1调用了函数f2，函数f2又调用了f1，这种调用方式称为 间接递归调用 ，如图2-19所示。
函数的递归调用就是自己调用自己，可以直接调用自己也可以间接调用自己。
图2-18 直接递归调用过程
图2-19 间接递归调用过程
在用递归解决实际问题时，递归函数只知道最基本问题的解。在递归函数中，遇到基本问题时仅仅返回一个值，在解决较为复杂的问题时，通过将复杂的问题化解为比原有问题更简单、规模更小的问题，最后把复杂问题变成一个基本问题，而基本问题的答案是已知的，基本问题解决后，比基本问题大一点的问题也得到解决，直到原有问题得到解决。
例如，利用递归求n的阶乘n！。n的阶乘递归定义为n！=n*（n-1）！，当n=5时，则有
5 ！=5*4 ！ 4 ！=4*3 ！ 3 ！=3*2 ！ 2 ！=2*1 ！ 1 ！=1*0 ！ 0 ！=1
递归计算5！的过程如图2-20所示。因为5！＝5*（5-1）！，因此，如果能求出（5-1）！，也就能求出5！；又因为（5-1）！＝（5-1）*（5-2）！；因此，如果能求出（5-2）！，则也就能求出（5-1）！；……最后一直递归到1！＝1*0！，因此，如果能求出0！，也就能求出1！；0！值是1，按上述分析过程逆向推回去，最后便可求得5！。
这样就把求解问题5！分解为求5这个基本问题与求4！这个比较复杂的问题，接着继续把求解4！分解为求4这个基本问题与求3！比较复杂的问题，直到把原问题变成求解0！=1这个最基本的已知问题为止。
根据上述分析可知，求解可分成两个阶段，第一阶段是由未知逐步推得已知的过程，称为“回推”；第二阶段是与回推过程相反的过程，即由已知逐步推得最后结果的过程，称为“递推”。其中，左半部分是回推过程，回推过程在计算出0！=1时停止调用；右半部分是递推过程，直到计算出5！=120为止。
下面以具体的例子讲解递归的调用。
【例2-1】 利用递归求n！。
【分析】 前面已经分析了递归实现n！的整个过程（见图2-20），只需要做到以下两点就可完成求n！：
（1）当n=0（递归调用结束，即递归的出口）时，返回1。
（2）当n≠0时，需要把复杂问题分解成较为简单的问题，直到分解成最简单的问题0！=1为止。
递归求n！的算法实现如下。
#include<stdio.h>
long factorial(int n);
void main()
{
int num;
for(num=0;num<10;num++)
printf("%d!=%ld\n",num,factorial(num));
}
long factorial(int n)
/*
递归求n
！函数实现*/
{
if(n==0) /*
当n=0
时，递归调用出口*/
return 1; /*0
！=1
是最基本问题的解*/
else /*
否则 */
return n*factorial(n-1); /*
递归调用将问题分解成较为简单的问题*/
}
程序运行结果如图2-21所示。
图2-20 求5！的间接递归调用过程
图2-21 递归求n！的运行结果
【例2-2】 要求利用递归实现求n个数中的最大者。
【分析】 假设元素序列存放在数组a中，数组a中n个元素的最大者可以通过将a[n-1]与前n-1个元素最大者比较之后得到。当n=1时，有findmax（a，n）=a[0]；当n>1时，有findmax（a，n）=（a[n-1]>findmax（a，n-1）?a[n-1]:findmax（n-1）。
也就是说，数组a中只有一个元素时，最大者是a[0]；超过一个元素时，则要比较最后一个元素a[n-1]和前n-1个元素中的最大者，其中较大的一个即所求。而前n-1个元素的最大者需要继续调用findmax函数。
求n个数中的最大者的递归算法实现如下。
#include<stdio.h>
#define N 200
int findmax(int a[],int n);
void main()
{
int a[N],n,i;
printf("
请输入n
的值:");
scanf("%d",&n);
printf("
请依次输入%d
个数：\n",n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("
在这%d
个数中，最大的元素是:%d\n",n,findmax(a,n));
}
int findmax(int a[],int n)
{
int m;
if(n<=1)
return a[0];
else
{
m=findmax(a,n-1);
return a[n-1]>=m?a[n-1]:m;
}
}
程序的运行结果如图2-22所示。
【例2-3】 利用递归函数输出正整数和等于n的所有不增的正整数和式。例如，当n=5时，不增的和式如下。
5=5 5=4+1 5=3+2 5=3+1+1 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1
【分析】 引入数组a，用来存放分解出来的和数，其中，a[k]存放第k步分解出来的和数。递归函数应设置3个参数，第1个参数是数组名a，用来将数组中的元素传递给被调用函数；第2个参数i表示本次递归调用要分解的数；第3个参数k是本次递归调用将要分解出的第k个和数。递归函数的原型如下。
void rd(int a[],int i,int k)
对将要分解的数i，可分解出来的数j共有i种可能选择，它们是i、i-1、…、2、1。但为了保证分解出来的和数依次构成不增的正整数数列，要求从i分解出来的和数j不能超过a[k-1]，即上次分解出来的和数。
特别地，为保证对第一步（k=1）分解也成立，程序可在a[0]预置n，即第一个和数最大为n。在分解过程中，当分解出来的数j==i时，说明已完成一个和式分解，应将和式输出；当分解出来的数j<i时，说明还有i-j需要进行第k+1次分解。
和为n的所有不增正整数和式分解算法实现如下。
#include<stdio.h>
#define N 100
void rd(int a[],int i,int k);
void main()
{
int n,a[N];
printf("
请输入一个正整数n(1
≤n
≤20):");
scanf("%d",&n);
a[0]=n;
printf("
不增的和式分解结果:\n");
rd(a,n,1);
}
void rd(int a[],int i,int k)
{
int j,p;
for(j=i;j>=1;j--)
{
if(j<=a[k-1])
{
a[k]=j;
if(j==i)
{
printf("%d=%d",a[0],a[1]);
for(p=2;p<=k;p++)
printf("+%d",a[p]);
printf("\n");
}
else
rd(a,i-j,k+1);
}
}
}
程序运行结果如图2-23所示。
图2-22 递归实现求n个数的最大者程序运行结果
图2-23 和式分解
迭代与递归是程序设计中最常用的两种结构。任何能使用递归解决的问题都能使用迭代的方法解决。迭代和递归的区别是，迭代使用的是循环结构，递归使用的是选择结构。使用递归能够使程序的结构更清晰，设计出的程序更简洁、程序更容易让人理解。
但是，递归也有许多不利之处，大量的递归调用会耗费大量的时间和内存。每次递归调用都会建立函数的一个备份，会占用大量的内存空间。迭代则不需要反复调用函数和占用额外的内存。通过分析递归求n的阶乘n！的计算过程，我们可以把它转化为非递归实现，其非递归实现如下。
int NonRecFact(int n)
/*
非递归求前n
的阶乘*/
{
int i,s=1;
for(i=1;i<=n;i++) /*
利用迭代求n
的阶乘*/
s*=i;
return s;
}
对于大整数问题，考虑到n值非常大的情况，运算结果超出一般整数的位数，可以用一维数组存储长整数，数组中的每个元素只存储长整数的一位数字。如有m位长整数N用数组a[]存储，N=a[m]*10 m-1 +a[m-1]*10 m-2 +…+a[2]*10 1 +a[1]*10 0 ，并用a[0]存储长整数N的位数m，即a[0]=m。按上述约定，数组的每个元素存储k的阶乘k！的每一位数字，并从低位到高位依次存储于数组的第2个元素、第3个元素……例如，6！=720在数组中的存储形式如图2-24所示。
其中，第一个元素3表示长整数是一个3位数，接着是低位到高位的0、2、7，表示长整数720。
图2-24 k!在数组中的存储情况
在计算阶乘k！时，可以采用对已求得的阶乘（k-1）！连续累加k-1次（即得到k*（k-1）！）后得到。例如，已知5！=120，计算6！，可对原来的120再累加5次120（即得到6*5）得到720。具体程序实现如下。
#include<stdio.h>
#include<malloc.h>
#define N 100
void fact(int a[],int k)
{
int *b,m,i,j,r,carry;
m=a[0];
b=(int*)malloc(sizeof(int)*(m+1));
for(i=1;i<=m;i++)
b[i]=a[i];
for(j=1;j<k;j++)
{
for(carry=0,i=1;i<=m;i++)
{
r=(i<=a[0]?a[i]+b[i]:a[i])+carry;
a[i]=r%10;
carry=r/10;
}
if(carry)
a[++m]=carry;
}
free(b);
a[0]=m;
}
void write(int *a,int k)
{
int i;
printf("%4d!=",k);
for(i=a[0];i>0;i--)
printf("%d",a[i]);
printf("\n");
}
void main()
{
int a[N],n,k;
printf("
请输入正整数n
的值:");
scanf("%d",&n);
a[0]=1;a[1]=1;
write(a,1);
for(k=2;k<=n;k++)
{
fact(a,k);
write(a,k);
}
}
对于较为简单的递归问题，可以利用简单的迭代将其转化为非递归。而对于较为复杂的递归问题，需要通过利用数据结构中的栈来消除递归。