练习
• 例：编写求组合数的函数。
Cmn

m! n!(m n)!
6.9.2 函数的递归调用
递归: 一个函数直接或间接地使用自身。 1. 直接递归调用：函数直接调用本身 2. 间接递归调用：函数间接调用本身
直接调用
int f(int x) { int y,z;
…… z=f(y); ……. return(2*z); }
A
B
C
n个盘子
必须用递归方式解决，将n阶问题转为n-1阶：
1) 先将A塔n –1个盘子借助于C移至B上： 2) 将A上剩下的一个移至C上.
3) 将B上n –1个盘子借助于A移至C上. 可以看到:
1)、3)为同一问题,都为n –1个盘子借助于 一个空塔移至另一塔上。 递归出口：n=1，此时A座上只有一个盘子，直 接将其移动到C座上即可。
age( int 1n ) {
int c; if (n==1) c=10;
return c; }
age( int n3 ) {
int c;
else c= age( n2 -1 ) +2
return c; }
age( int 2n ) {
int c;
else c=age( n1 -1 ) +2
return c; }
《C语言程序设计》
学习内容： 函数的嵌套调用和递归调用
6.9 函数的嵌套调用和递归调用
引例
编程函数求解：
y=(x+y)2 ! 然后调用函数求解(2+3)2！以及(3+4)2！ 要求：
1、首先编写求和函数，求解x+y的和。 2、编写函数求解(x+y) 的平方(x+y)2 3、编写函数求解(x+y)2！
}
§C语言允许在一个函数的定义中出现对另一个函数 的调用(使用)。这样就出现了函数的嵌套调用，即在 被使用函数中又调用其他函数。
main( )函 数
①
②
f1( )函 数
③
④
f2( )函 数
调 用 f1( )函 数 调 用 f2( )函 数
⑤
后续语句
后续语句
⑨
⑧
结束
⑦
⑥
返回
返回
#include <stdio.h> long sum(int a, int b);
总结：递归算法
递归函数名f(参数x) { if (x==初值) //递归结束的条件
结果=…； else
结果=含f(x-1)的表达式；
main() { f(n) …
}
返回结果（return）； }
f(1或者0) { f(0)== …)
}
f(n) { f(n-1) }
f(n-1) { f(n-2) }
r=x>y?x:y; return(r>z?r:z); }
int min(int x,int y,int z) { int r;
r=x<y?x:y; return(r<z?r:z); }
练习
g(x,y)=
f( x+y) 2
x+y
(x<=y)
f(x-y) 2
x+y
( x>y)
其中：f(t)=(1+e-t)/(1+et) 求result=g(2.5,3.4)。
#include "stdio.h" void move(int n,char x,char y,char z) { if(n==1)
printf("%c-->%c\n",x,z); else { move(n-1,x,z,y); //n-1盘子已经到y上
printf("%c-->%c\n",x,z); move(n-1,y,x,z); // y上n-1盘子想办法放到z } }
c=10
age(2)
c=age(4)+2; c=age(3)+2; c=age(2)+2; c=age(1)+2;
return c;
c=18
return c;
c=16
return c;
c=14
return c;
c=12
main() {
int x;
x=age(3);
printf("%d",x); }
main() {
long x; x=jc(6); printf("%ld",x); }
long jc(int n) { long k;
int i; for(i=1;i<=n;i++) k=k*i; return k; } main() { long x; x=jc(6); printf("%ld",x); }
A
B
C
A >C A >B C >B A >C B >A B >C A >C
练习
1、用递归方法求和：
1！+2！+3！+4！+5！…+n!
其中n的值由键盘输入。 2、有5个人，第5个人说他的钱是第4个人的2 倍还多100元，第4个人说他是第3个人的2倍还 多100，第3个人说他是第2个人的2倍还多100， 第2个人说他是第1个人的2倍还多100，第1个 人说他1000元。求第5个人有多少钱。
int sum(int x, int y) { return (x+y); }
int pf ( int h) { return (h*h); }
6.9.1 函数的嵌套调用
§C语言中不允许嵌套的函数定义，各函数之 间是平行的，不存在上一级函数和下一级函数 的问题。 void print( )
{ putchar('*'); void prnline( int n) { int i; for(i=0;i<=n;i++) putchar('\n'); }
间接调用
int f1(int x) int f2(int t)
{ int y,z; { int a,c;
……
……
z=f2(y);
c=f1(a);
…….
…….
return(2*z); return(3+c);
}
}
【例1】有5个人，第5个人说他比第4个人大2 岁，第4个人说他对第3个人大2岁，第3个人说 他对第2个人大2岁，第2个人说他比第1个人大 2岁，第1个人说他10岁。求第5个人多少岁。
main() {
int n; printf (" input the number of diskes " :); scanf("%d",&n); move(n,'a','b','c'); }
运行情况如下： input the number of diskes:3 A >C A >B C >B A >C B >A B >C A >C
f(n-2) { f(n-3) }
例2：用递归算法计算n！ n!=n*(n-1)! (n-1)!=(n-1) *(n-2)! ………………….. 5!=5*4! 4!=4*3! 3!=3*2! 2!=2*1! 1!=1
long jc(int n) { long k;
if(n==1) k=1; else k=n*jc(n-1); return k; }
函数定义
{ long factorial(int n); 形参
long factorial(int n) { long rtn=1;
int i; for(i=1;i<=n;i++) rtn*=i; return(rtn); }
long c1,c2;
c1=factorial(a); 函数调用
c2= factorial(b);
if ((n==1) || (n==2)) return 1; else return (fib(n-1)+fib(n-2)); }
main() {
int i; printf("\n"); printf(" %d",fib(20));
}
例4: 汉诺塔(Hanoi)问题
问题: 将A塔上n个盘子移至C(借助于B)。 移动时, 保证三个塔始终是大盘在下,小盘在上。
main() { int a,b,c;
scanf(“%d,%d”,&a,&b);
c= jc(a,b);
printf(“sum is %d",c); }
int jc(int k, int j) { int z,m,i,s=1;
z=sum(k, j); m= pf(z); for(i=1;i<=m;i++) s=s*i; return s; }
return(c1+c2ห้องสมุดไป่ตู้; 函数返回值
}
例 2求三个数中最大数和最小数的差值
#include <stdio.h> int dif(int x,int y,int z); int max(int x,int y,int z); int min(int x,int y,int z); void main() { int a,b,c,d;
例3、用递归法计算Fibonacci序列的第20项。
f= 1
n=1或者n=2
f(n-1)+f(n-2) n>2