明递归调用的执行

    过程。

    【例 8.5】用递归法计算 n!

    用递归法计算 n!可用下述公式表示：

    n!=1         (n=0,1)

    n×(n-1)!    (n>1)

    按公式可编程如下：

    long ff(int n)

    {

    long f;

    谭浩强      C 语言程序设计               2001 年 5 月 1 日

    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);

    }

    程序中给出的函数 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)。

    进行四次递归调用后，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 上；