6.6　递归函数

函数的递归调用是指调用一个函数的过程中直接或间接的调用该函数自身，如图6.6.1所示，这种函数称为递归函数。C语言允许函数的递归调用。在递归调用中，主调函数又是被调函数，执行递归函数将反复调用其自身，每调用一次就进入新的一层。

图6.6.1　函数递归示意图

采用递归算法解决问题的特点：原始的问题可转化为解决方法相同的新问题，而新问题的规模要比原始问题小，新问题又可以转化为规模更小的问题，直至最终归结到最基本的情况。

例如，有函数f如下：

这个函数是一个递归函数，但是运行该函数将无休止地调用其自身，这当然是不正确的。为了防止递归调用无终止地进行，必须在函数内有终止递归调用的手段。常用的办法是加条件判断，满足某种条件后就不再进行递归调用，然后逐层返回。下面举例说明递归调用的执行过程。

递归调用的过程分为：

① 递归过程：将原始问题不断转化为规模小了一级的新问题，从未知向已知推进，最终达到递归终结条件；

② 回溯过程：从已知条件出发，沿递归的逆过程，逐一求值返回，直至递归初始处，完成递归调用。

例6-20　用递归法计算n！，n！可用下述公式表示：

程序中给出的函数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）。逐次递归展开，如图6.6.2所示。进行四次递归调用后，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。

图6.6.2　递归调用示意图

大部分递归函数没有明显地减少代码规模和节省内存空间。另外，大部分函数的递归形式比非递归形式运行速度要慢一些。这是因为编译器使用堆栈来实现递归过程的，所以附加的函数调用增加了时间开销（在许多情况下，速度的差别不太明显）。对函数的多次递归调用可能造成堆栈的溢出。

递归函数的主要优点是可以把算法写得比使用非递归函数时更清晰更简洁，而且某些问题，特别是与人工智能有关的问题，更适宜用递归方法。递归的另一个优点是，递归函数不会受到怀疑，较非递归函数而言，某些人更相信递归函数。在递归函数中不使用if语句，是一个很常见的错误。在开发过程中广泛使用printf（）和getchar（）可以看到执行过程，并且可以在发现错误后停止运行。

例6-20也可以不用递归的方法来完成，如可以用递推法，即从1开始乘以2，再乘以3……直到n。递推法比递归法更容易理解和实现，但是有些问题则只能用递归算法才能实现。典型的问题是Hanoi塔问题。

如图6.6.3（a）所示（n=3），一块板上有三根针，A，B，C。A针上套有n（n=3）个大小不等的圆盘，大的在下，小的在上。要把这n个圆盘从A针移动C针上。

图6.6.3　Hanoi塔问题求解示意图（n＝3）

移动规则是：

（1） 一次只能移动一个；

（2） 大的不能放在小的上面；

（3） 只能在三个位置中移动。求移动的步骤。

本题算法分析如下，设A上有n个盘子。

如果n=1，则将圆盘从A直接移动到C。

如果n=2，则

　　1．将A上的n−1（等于1）个圆盘移到B上。

　　2．再将A上的一个圆盘移到C上。

　　3．最后将B上的n−1（等于1）个圆盘移到C上。

如果n=3，则：

　　1．将A上的n−1（等于2，令其为n'）个圆盘移到B（借助于C）。

　　步骤如下：

　　（1）将A上的n`−1（等于1）个圆盘移到C上，如图6.6.3（b）所示。

　　（2）将A上的一个圆盘移到B，如图6.6.3（c）所示。

　　（3）将C上的n`−1（等于1）个圆盘移到B，如图6.6.3（d）所示。

　　2．将A上的一个圆盘移到C，如图6.6.3（e）所示。

　　3．将B上的n−1（等于2，令其为n`）个圆盘移到C（借助A）。

　　步骤如下：

　　（1）将B上的n`−1（等于1）个圆盘移到A，如图6.6.3（f）所示。

　　（2）将B上的一个盘子移到C，如图6.6.3（g）所示。

　　（3）将A上的n`−1（等于1）个圆盘移到C，如图6.6.3（h）所示。

　　到此，完成了三个圆盘的移动过程。

从上面分析可以看出，当n大于等于2时，移动的过程可分解为三个步骤：

　　第一步 把A上的n−1个圆盘移到B上；

　　第二步 把A上的一个圆盘移到C上；

　　第三步 把B上的n−1个圆盘移到C上；其中第一步和第三步是类同的。

　　当n=3时，第一步和第三步又分解为类同的三步，即把n`−1个圆盘从一个针移到另一个针上，这里的n`=n−1。显然这是一个递归过程，据此算法如例6-21所示。

例6-21　Hanoi塔问题。

从程序中可以看出，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时程序运行的结果为：

input number：

4

the step to moving 4 diskes：

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

常见的编程错误6.4

省略基本情况，或者将递归步骤写得不正确，以致于不能归结到基本情况，引起无限“递归”，最终耗尽内存。

如果一个非递归函数不经意地直接或间接调用了自身，会产生逻辑错误。

良好的编程习惯6.3

避免导致指数级调用“爆炸”的递归程序。