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<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 %2d 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

变量的浸染域

#p#分页标题#e#

在接头函数的形参变量时曾经提到， 形参变量只在被挪用期间才分派内存单位，挪用竣事当即释放。 这一点表白形参变量只有在函数内才是有效的， 分开该函数就不能再利用了。这种变量有效性的范畴称变量的浸染域。不只对付形参变量， C语言中所有的量都有本身的浸染域。变量说明的方法差异，其浸染域也差异。 C语言中的变量，按浸染域范畴可分为两种， 即局部变量和全局变量。