计算机科学-第15周 递归函数 题目及参考解答

《计算机科学》课程主页在：http://blog.csdn.net/sxhelijian/article/details/13705597

1、阅读下面关于递归函数的程序，在草稿纸上画出函数调用“递推-回归”的过程，得出运行结果，并和实际运行结果进行对照
（1）

#include <stdio.h>
int fact(int n);
int main(){
    long x=0,y=0;
    x=5;
    y=fact(x);
    printf("%ld\n",y);
    return 0;
}
int fact(int n){
    long f=0;
    if(n==1)
        f=1;
    else
        f=n*fact(n-1);
    return f;
}

通过绘出“递推-回归”图，你认为运行结果为:____________________
实际运行的结果为：_________________

(2)

#include <stdio.h>
void f(int n)
{
    if(n>=10)
        f(n/10);
    printf("%d\n",n);
}
int main()
{
    f(12345);
    return 0;
}

通过绘出“递推-回归”图，你认为运行结果为:____________________
实际运行的结果为：_________________


2、阅读下面关于递归函数的程序，写下你认为的运行结果，并和实际运行结果进行对照，然后通过“单步执行”，观察这些递归函数的执行过程。
（1）

#include <stdio.h>
void recur(char c)
{
    printf("%c\n",c);
    if(c<'5') recur(c+1);
    printf("%c\n",c);
}
int main()
{
    recur('0');
    return 0;
}

你认为运行结果为:__________________
实际运行的结果为：_________________
请用“单步执行”跟踪。

（2）

#include <stdio.h>
void f(int n);
int main ()
{
    int  i=1234;
    f(i);
    return 0;
}


void f(int n)
{
    if(n==0)
        return;
    else
    {
        printf("%d\n",n%10);
        f(n/10);
        printf("%d\n",n%10);
        return;
    }
}

你认为运行结果为:__________________
实际运行的结果为：_________________
请用“单步执行”跟踪。


3、楼梯有n阶台阶，上楼可以一步上1阶，也可以一步上2阶，编一程序计算共有多少种不同的走法？通过自定义的递归函数求解这个问题。
　　提示：设n阶台阶的走法数为f(n)。

• n=1时，一步上去，有1种走法；
• n=2时，可以一步1阶，分两步上去，也可以一步2阶，用一步上去，共有2种走法；
• n个台阶时，看最后一步怎么走。最后一步走1阶，走法为f(n-1)种，而最后一步走2阶，趟法为f(n-2)种，所以，总的走法种数是f(n-1)+f(n-2)

　　所以，编程序解下面的方程，即是本题解法：

 　　
　　参考解答：

#include <stdio.h>
int f(int n);
int main(){
    int x,y;
    x=5;
    y=f(x);
    printf("%d\n",y);
    return 0;
}
int f(int n){
    int m;
    if(n==1)
        m=1;
    else if(n==2)
        m=2;
else
    m=f(n-1)+f(n-2);
    return m;
}

4、编写程序，计算ackerman函数值并运行程序求出A(3,2)的值。

　　

参考解答：

#include"stdio.h"
int Ackerman(int m,int n)
{
    //printf("n=%d, m=%d\n",n, m);
    if(m==0)
        return n+1;
    else if(n==0)
        return Ackerman(m-1,1);
    else
        return Ackerman(m-1,Ackerman(m,n-1));

}
int main()
{
    int n,m;
    scanf("%d%d",&m,&n);
    printf("%d\n",Ackerman(m,n));
    return 0;
}

　　提示：执行程序求A(4,3)，将类似陷入死循环。原因是递归的层次太多，计算机在急速运行中，直到内存耗尽。
　　实际上，当m≥4，Ackermann函数的增长快得惊人。Ackermann(4,2)=2^65536-3有19729位，而Ackermann(4,3)则即使是位数也不易估计。
　　计算机要求解这样的函数，也得另辟他径。