C语言设计

该语句对 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 个大小不等的圆盘，大的在下，小的在上。
如图 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，则：
谭浩强      C 语言程序设计               2001 年 5 月 1 日
A. 将 A 上的 n-1(等于 2，令其为 n`)个圆盘移到 B(借助于 C)，步骤如下：
(1)将 A 上的 n`-1(等于 1)个圆盘移到 C 上。
(2)将 A 上的一个圆盘移到 B。
(3)将 C 上的 n`-1(等于 1)个圆盘移到 B。
B. 将 A 上的一个圆盘移到 C。
C. 将 B 上的 n-1(等于 2，令其为 n`)个圆盘移到 C(借助 A)，步骤如下：
(1)将 B 上的 n`-1(等于 1)个圆盘移到 A。
(2)将 B 上的一个盘子移到 C。
(3)将 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(int n,int x,int y,int z)
{
    if(n==1)
      printf("%c-->%c ",x,z);
    else
    {
      move(n-1,x,z,y);
      printf("%c-->%c ",x,z);
      move(n-1,y,x,z);
    }
}
main()
{
    int h;
    printf(" input number: ");
    scanf("%d",&h);
    printf("the step to moving %2d diskes: ",h);
    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
8.7 数组作为函数参数
谭浩强      C 语言程序设计               2001 年 5 月 1 日
数组可以作为函数的参数使用，进行数据传送。数组用作函数参数有两种形式，一种是
把数组元素(下标变量)作为实参使用；另一种是把数组名作为函数的形参和实参使用。
1. 数组元素作函数实参
数组元素就是下标变量，它与普通变量并无区别。 因此它作为函数实参使用与普通变
量是完全相同的，在发生函数调用时，把作为实参的数组元素的值传送给形参，实现单向的
值传送。例 5.4 说明了这种情况。
【例 8.7】判别一个整数数组中各元素的值，若大于 0 则输出该值，若小于等于 0 则输出 0
值。编程如下：
void nzp(int v)
{
    if(v>0)
      printf("%d ",v);
    else
      printf("%d ",0);
}
main()
{
    int a[5],i;
    printf("input 5 numbers ");
    for(i=0;i<5;i++)
      {scanf("%d",&a[i]);
   nzp(a[i]);}
}
谭浩强      C 语言程序设计               2001 年 5 月 1 日
    本程序中首先定义一个无返回值函数 nzp，并说明其形参 v 为整型变量。在函数体中根
据 v 值输出相应的结果。在 main 函数中用一个 for 语句输入数组各元素，每输入一个就以
该元素作实参调用一次 nzp 函数，即把 a[i]的值传送给形参 v，供 nzp 函数使用。
2. 数组名作为函数参数
用数组名作函数参数与用数组元素作实参有几点不同：
1) 用数组元素作实参时，只要数组类型和函数的形参变量的类型一致，那么作为下标
变量的数组元素的类型也和函数形参变量的类型是一致的。因此，并不要求函数的
形参也是下标变量。换句话说，对数组元素的处理是按普通变量对待的。用数组名
作函数参数时，则要求形参和相对应的实参都必须是类型相同的数组，都必须有明
确的数组说明。当形参和实参二者不一致时，即会发生错误。
2) 在普通变量或下标变量作函数参数时，形参变量和实参变量是由编译系统分配的两
个不同的内存单元。在函数调用时发生的值传送是把实参变量的值赋予形参变量。
在用数组名作函数参数时，不是进行值的传送，即不是把实参数组的每一个元素的
值都赋予形参数组的各个元素。因为实际上形参数组并不存在，编译系统不为形参
数组分配内存。那么，数据的传送是如何实现的呢?在我们曾介绍过，数组名就是
数组的首地址。因此在数组名作函数参数时所进行的传送只是地址的传送，也就是
说把实参数组的首地址赋予形参数组名。形参数组名取得该首地址之后，也就等于
有了实在的数组。实际上是形参数组和实参数组为同一数组，共同拥有一段内存空
间。
上图说明了这种情形。图中设 a 为实参数组，类型为整型。a 占有以 2000 为首地
址的一块内存区。b 为形参数组名。当发生函数调用时，进行地址传送，把实参数
组 a 的首地址传送给形参数组名 b，于是 b 也取得该地址 2000。于是 a，b 两数组
共同占有以 2000 为首地址的一段连续内存单元。从图中还可以看出 a 和 b 下标相
同的元素实际上也占相同的两个内存单元(整型数组每个元素占二字节)。例如 a[0]
和 b[0]都占用 2000 和 2001 单元，当然 a[0]等于 b[0]。