函数的递归调用
一个函数在它的函数体内调用它本身称为递归调用。 这种函数称为递归函数。Ｃ语言准许函数的递归调用。在递归调用中， 主调函数又是被调函数。实验递归函数把几次调用其本身。 每调用一次就进入新的一层。例如有函数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<0) printf("n<0,input error");
else if(n==0||n==1) f=1;
else f=ff(n-1)*n;
return(f);
}
main()
{
int n;
long y;
printf("\ninput a inteager number:\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);
……
}
顺序中给出的函数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)。 逐次递归睁开如图5.3所示。截止四次递归调用后，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。
例5. 9也可以不消递归的方法来完成。如可以用递推法，即从1入部下手乘以2，再乘以3…直到n。递推法比递归法更苟且明白明明和完成。但是有些结果则只能用递归算法本领完成。典范的结果是Hanoi塔结果。
[例5.10]Hanoi塔结果
一块板上有三根针，A，B，C。A针上套有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)把A上的n`-1(即是1)个圆盘移到C上，见图5.5(b)。
(2)把A上的一个圆盘移到B，见图5.5(c)
(3)把C上的n`-1(即是1)个圆盘移到B，见图5.5(d)
B. 把A上的一个圆盘移到C，见图5.5(e)
C. 把B上的n-1(即是2，令其为n`)个圆盘移到C(借助A)，
步调如下：
(1)把B上的n`-1(即是1)个圆盘移到A，见图5.5(f)
(2)把B上的一个盘子移到C，见图5.5(g)
(3)把A上的n`-1(即是1)个圆盘移到C，见图5.5(h)。
到此，完成了三个圆盘的挪动进程。
从下面分解可以看出，当n大于即是2时， 挪动的进程可分解为
三个步调：
第一步 把A上的n-1个圆盘移到B上；
第二步 把A上的一个圆盘移到C上；
第三步 把B上的n-1个圆盘移到C上；此中第一步和第三步是类同的。
当n=3时，第一步和第三步又分解为类同的三步，即把n`-1个圆盘从一个针移到另一个针上，这里的n`=n-1。 显然这是一个递归过
程，据此算法可编程如下：
move(int n,int x,int y,int z)
{
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()
{
int h;
printf("\ninput number:\n");
scanf("%d",&h);
printf("the step to moving - diskes:\n",h);
move(h,'a','b','c');
}
move(int n,int x,int y,int z)
{
if(n==1)
printf("%-->%c\n",x,z);
else
{
move(n-1,x,z,y);
printf("%c-->%c\n",x,z);
move(n-1,y,x,z);
}
}
main()
{ ……
move(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 时顺序运转的效果为
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
变量的感化域
在交涉函数的形参变量时已经提到， 形参变量只在被调用时期才分派内存单元，调用竣事当即释放。 这一点诠释形参变量只要在函数内才是有效的， 离开该函数就不能再运用了。这种变量有效性的范围称变量的感化域。不仅对于形参变量， Ｃ语言中通盘的量都有本身的感化域。变量阐发');的体式式子不合，其感化域也不合。 Ｃ语言中的变量，按感化域范围可分为两种， 即局部变量和全局变量。
版权声明：原创作品，准许转载，转载时请务必以超链接体式式子标明文章 原始来因 、作者信息和本声明。否则将清查司法责任。