二级C语言考试辅导教程第五章:函数[6]

函数的递归调用
在函数体中调用自身的函数称为递归调用。这种函数称为递归函数。c语言允许递归调用函数。在递归调用中，调用函数也是被调用函数。执行递归函数会反复调用自身。每个调用都进入一个新的层。比如函数f如下:
int f(int x)
{
int y；
z = f(y)；
return z；
}
此函数是递归函数。但是运行这个函数会无休止地调用自己，这当然是不正确的。为了防止递归调用无限期地进行下去，函数中必须有终止递归调用的方法。常见的方法是加入条件判断，满足一定条件后，不再递归调用，然后逐层返回。下面是递归调用执行过程的一个例子。
[例5.9]用递归方法计算N！用递归计算n！可以用下面的公式表示:
n！=1 (n=0，1)
n×(n-1)！(n>1)
公式可以编程如下:
long ff(int n)
{
long f；
if(n else if(n = = 0 | | n = = 1)f = 1；
else f = ff(n-1)* n；
return(f)；
}
main()
{
int n；
long y；
printf(" \ n输入整数:\ n ")；
scanf("%d "，& n)；
y = ff(n)；
printf("%d！=%ld "，n，y)；
}
long ff(int n)
{……
else f = ff(n-1)* n；
……
}
main()
{……
y = ff(n)；
……
}来源:www.examda.com
程序中给出的函数ff是递归函数。主函数调用ff后，进入函数ff的执行。如果n的返回值是6*4=24，则最终返回值ff(5)是24*5=120。
例5。9也可以不用递归。比如可以用递归的方法，就是1乘以2，再乘以3…直到n，递归的方法比递归的方法更容易理解和实现。但有些问题只能用递归算法来解决。典型的问题是河内塔问题。

[例题5.10]汉诺塔问题
一块木板上有A、B、C三根针。一根针上套着64个大小不一的圆盘，大的在下面，小的在上面。如图5.4所示。要将这64个圆盘从A针移动到C针，一次只能移动一个圆盘，移动可以借助b针进行，但任何时候，任何针上的圆盘都必须保持下面的大板和上面的小板。找到移动的步骤。
这个问题的算法分析如下。假设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，那么:
A .将A上的n-1(等于2，使之为n `)个磁盘移到B上(借助C)。
步骤如下:
(1)移动n`-1(等于1)
(2)将一个磁盘从A移动到B，如图5.5所示(c)
(3)将n`-1(等于1)个磁盘从C移动到B，如图5.5所示(d)
B .将一个磁盘从A移动到C，如图5.5所示。
步骤如下:
(1)将B上的n`-1(等于1)个盘移动到A上，如图5.5(f)
(2)将B上的一个盘移动到C上，如图5.5(g)
(3)将
至此，三个盘的移动过程已经完成。