《计算机科学》课程主页在：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)则即使是位数也不易估计。
计算机要求解这样的函数，也得另辟他径。
