一个函数在它的函数体内调用它自身，称为递归调用。这种函数称为递归函数。C语言允许函数的递归调用。在递归调用中，主调函数又是被调函数。执行递归函数将反复调用其自身，每调用一次，就进入新的一层。
例如，有函数f如下：
intf（intx）
｛ inty；
z＝f（y）；
returnz；
｝
这个函数是一个递归函数。但是运行该函数将无休止地调用其自身，这当然是不正确的。为了防止递归调用无休止地进行，必须在函数内有终止递归调用的手段。常用的办法是加条件判断，满足某种条件后就不再做递归调用，然后逐层返回。下面举例说明递归调用的执行过程。
【例8.5】用递归法计算n！。
用递归法计算n！可用下述公式表示：
n！＝1 （n＝0，1）
n×（n－1）！ （n＞1）
按公式可编程如下：
longff（intn）
｛ longf；
if（n＜0）printf（＂n＜0，inputerror＂）；
elseif（n＝＝0‖n＝＝1）f＝1；
elsef＝ff（n－1）*n；
return（f）；
｝
main（）
｛ intn；
longy；
printf（＂＼ninputainteagernumber：＼n＂）；
scanf（＂％d＂，＆n）；
y＝ff（n）；
printf（＂％d！＝％ld＂，n，y）；
｝
程序中给出的函数ff是一个递归函数。主函数调用ff后即进入函数ff执行，如果n＜0， n＝＝0或n＝1时都将结束函数的执行，否则就递归调用ff函数自身。由于每次递归调用的实参为n－1，即把n－1的值赋予形参n，最后当n－1的值为1时再做递归调用，形参n的值也为1，将使递归终止。然后可逐层退回。
下面再举例说明该过程。设执行本程序时输入为5，即求5！。主函数中的调用语句即为y＝ff（5），进入ff函数后，由于n＝5，不等于0或1，故应执行f＝ff（n－1）*n，即f＝ff（5－1）*5。该语句对ff做递归调用，即ff（4）。
进行四次递归调用后，ff函数形参取得的值变为1，故不再继续递归调用而开始逐层返回主调函数。ff（1）的函数返回值为1，ff（2）的返回值为1*2＝2，ff（3）的返回值为2*3＝6， ff（4）的返回值为6*4＝24，最后返回值ff（5）为24*5＝120。
例8.5也可以不用递归的方法来完成。如可以用递推法，即从1开始乘以2，再乘以3，…，直到n。递推法比递归法更容易理解和实现，但是有些问题则只能用递归算法才能实现。典型的问题是Hanoi塔问题。
【例8.6】Hanoi塔问题。
一块板上有三根针，A，B，C。A针上套有64个大小不等的圆盘，大的在下，小的在上，如图8－2所示。要把这64个圆盘从A针移动C针上，每次只能移动一个圆盘，移动可以借助B针进行。但在任何时候，任何针上的圆盘都必须保持大盘在下，小盘在上。求移动的步骤。
本题算法分析如下，设A上有n个盘子。
如果n＝1，则将圆盘从A直接移动到C。
如果n＝2，则：
（1）将A上的n－1（等于1）个圆盘移到B上；
（2）再将A上的一个圆盘移到C上；
图8－2
（3）最后将B上的n－1（等于1）个圆盘移到C上。
如果n＝3，则：
①将A上的n－1（等于2，令其为n＇）个圆盘移到B（借助于C），步骤如下：
a.将A上的n＇－1（等于1）个圆盘移到C上。
b.将A上的一个圆盘移到B。
c.将C上的n＇－1（等于1）个圆盘移到B。
②将A上的一个圆盘移到C。
③将B上的n－1（等于2，令其为n＇）个圆盘移到C（借助A），步骤如下：
a.将B上的n＇－1（等于1）个圆盘移到A。
b.将B上的一个盘子移到C。
c.将A上的n＇－1（等于1）个圆盘移到C。
到此，完成了三个圆盘的移动过程。
从上面的分析可以看出，当n大于等于2时，移动的过程可分解为三个步骤：
第一步：把A上的n－1个圆盘移到B上；
第二步：把A上的一个圆盘移到C上；
第三步：把B上的n－1个圆盘移到C上。
其中第一步和第三步是类同的。
当n＝3时，第一步和第三步又分解为类同的三步，即把n＇－1个圆盘从一个针移到另一个针上，这里的n＇＝n－1。显然这是一个递归过程，据此算法可编程如下：
move（intn，intx，inty，intz）
｛ if（n＝＝1）
printf（＂％c－－＞％c＼n＂，x，z）；
else
｛ move（n－1，x，z，y）；
printf（＂％c－－＞％c＼n＂，x，z）；
move（n－1，y，x，z）；
｝
｝
main（）
｛ inth；printf（＂＼ninputnumber：＼n＂）；
scanf（＂％d＂，＆h）；
printf（＂thesteptomoving％2ddiskes：＼n＂，h）；
m ove（h，＇a＇，＇b＇，＇c＇）；
｝
从程序中可以看出，move函数是一个递归函数，它有四个形参：n，x，y，z。n表示圆盘数，x，y，z分别表示三根针。move函数的功能是把x上的n个圆盘移动到z上。当n＝＝1时，直接把x上的圆盘移至z上，输出x→z。如n！＝1，则分为三步：递归调用move函数，把n－1个圆盘从x移到y；输出x→z；递归调用move函数，把n－1个圆盘从y移到z。在递归调用过程中，n＝n－1，故n的值逐次递减，最后n＝1时，终止递归，逐层返回。当n＝4时，程序运行的结果为：
inputnumber：
4
thesteptomoving4diskes：
a→b
a→c
b→c
a→b
c→a
c→b
a→b
a→c
b→c
b→a
c→a
b→c
a→b
a→c
b→c
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
