本次课内容：递归调用
教学目的：掌握递归概念，利用函数嵌套进行的递归处理算法，
能建立递归结构。
重点：递归的概念和函数的自身调用过程（递归）。
难点：函数的自身调用过程。
预习：函数的定义、调用、传值和嵌套。
main()
{
int a=3,b=5;
void swap(int x,int y);
swap(a,b);
printf(“a=%d,b=%d\n’,a,b);
}
void swap(int x,int y)
{
int t;
t=x;x=y;y=t;
printf(“x=%d,y=%d\n”,x,y);
}
一、概念
函数不允许定义在另一个函数内，但可以在一个函数中调
用另一个函数，这种调用称函数的嵌套。
递归：某一事物直接地或间接地由自己组成。
递归调用：一个函数直接或间接地调用自身，便构成了函数
的递归调用。前者称直接递归调用，后者称间接递归调用。
二、递归函数与数学模型
1、计算 n!
数学模型,
函数,
long fact(int n)
{
if (n<=1)
return(1);
else
return(n*fact(n-1));
}
?
?
?
? )1(*
1
nf a c tn
(n<=1)
(n>1 ) fact(n)=
main()
{
int x;
long fact(int n);
printf(“input a integer”);
scanf(“%d\n”,&x);
printf(“x!=%ld\n”,fact(x));
}
递归调用过程,
main()
调 fact(5)
Fact(5)=120
5*fact(4)
120
4*fact(3)
24
3*fact(2)
6
2*fact(1)
2
返回
1
fact(5)
fact(4)
fact(3)
fact(2)
fact(1)
?
?
?
? )1(*
1
nf a c tn
(n<=1)
(n>1 ) fact(n)=
2、求两个数的最大公约数的数学模型
int gcd(int a,int b)
{
if (a%b==0)
return(b);
else
return(gcd(b,a%b);
}
?
?
?
)%,g c d ( bab
b
(a%b==0)
(a%b!=0 ) gcd(a,b)=
main()
{
int x,y;
int gcd(int a,int b);
printf(“input two integers”);
scanf(“%d%d\n”,&x,&y);
printf(“%d\n”,gcd(x,y));
}
(a=b;b=a%b)
小结,
1、递归
2、递归调用
3、递归模型
4、递归调用过程