06-函数嵌套调用与递归调用课件

int main() {
int x, y, z, max; scanf("%d%d%d",&x,&y,&z); max = Max3(x, y, z); printf("max=%d\n",max); return 0; }
int Max3(int a, int b, int c) {
int max; max = Max(a, b); max = Max(max, c); return max; }
else f = n*fact(n-1);
y = fact(n);
return f;
printf("%d!=%ld\n", n,y);
}
}
main函数
fact函数
fact函数
fact函数
y=fact (3)
f=3*fact (2)
f=2*fact (1)
f=1
return 6
return 2
return 1
8
例4 用递归方法计算 n!
n!

1 n(n -
1)!
递归的终止条件 n 0,1 n 1
#include <stdio.h>
void main()
递归方式
long fact(int n)
{ long y;
{ long f;
int n;
if(n==1||n==0) f = 1;
scanf("%d", &n);
int age(int n); int n; scanf(("%d", &n); printf("NO. 5, age: %d\n" ,age(n));
14
long sum( int n ) //素数求和 { int i;
long s = 0; for( i=2; i<=n; i++ )
if ( isprime(i)==1 ) s = s+i; return s; }
int isprime( int m ) //判断素数 { int i, k;
k=sqrt(m); for( i=2; i<=k; i++ )
age(n) 10
(n 1)
age(n) age(n 1) 2 (n 1)
12
#include <stdio.h> int age(int n) { int c;
age(n) 10 age(n) age(n 1) 2
if(n==1) c = 10;
else c = age(n-1) + 2;
– 存在递归的终止条件； – 存在导致问题求解的递归方式。 – 递归方法：递推、回归。
• 使用递归的优缺点
- 优点：程序简洁，代码紧凑。 - 缺点：每调用函数一次，在内存堆栈区分配空间，用于存放
函数变量、返回值等信息。所以递归次数过多，可能引起 堆栈溢出，且时间效率较差。
7
递归函数fact求解求9的阶乘过程
嵌套调用：在调用一个函数的过程中，又调用另一个函数。 C语言不能嵌套定义，但可以嵌套调用！
main( ) 调用函数a 结束
a函数


调用函数b


b函数


——函数嵌套调用的示意图
1
例3 函数嵌套调用实例—求三个变量中的最大值。
#include <stdio.h> int Max3(int a, int b, int c); int Max(int a, int b);
max = Max3(x, y, z);
int Max(int a, int b)
printf("max=%d\n",max);
return 0;
}
输出：max= 8
{ ⑤ if( a > b ) return a; ⑧ else return b; }
2x 5y 8z 8 max ……
2a 5b 8c 58 max …… 25 a 85 b
int Max(int a, int b) {
if( a > b ) return a; else return b; }
例3 求三个变量的最大值程序调用执行过程。
内存示意图
~
#include <stdio.h> int Max3(int a, int b, int c); int Max(int a, int b);
if( m%i == 0 ) return 0; return 1; }
什么是递归调用？
在调用一个函数的过程 中又出现直接或间接地调用 该函数本身，称为函数的递 归调用。
前者称为直接递归，后 者称为间接递归。
Ｃ语言的特点之一就在 于允许函数的递归调用。
直接递归 间接递归
6
递归函数的执行过程
• 用递归求解问题的特点
int Max3(int a, int b, int c) {
③ int max;
int main()
max = Max(a, b);
{
②
max = Max(max, c);
① int x, y, z, max;
}
scanf("%d%d%d",&x,&y,&z); ⑩
return max;
④⑦
⑥ ⑨
10
解题思路： • 要求第5个年龄，就必须先知道第4个年龄； • 要求第4个年龄必须先知道第3个年龄； • 第3个年龄又取决于第2个年龄； • 第2个年龄取决于第1个年龄； • 每个学生年龄都比其前1个学生的年龄大2岁。
11
解题思路：
age(5) = age(4) + 2 age(4) = age(3) + 2 age(3) = age(2) + 2 age(2) = age(1) + 2 age(1) = 10
fact(9)=9*fact( 8) fact(8)=8*fact( 7)
fact(9)=9*fact( 8) fact(8)=8*fact( 7)
·····
·····
递 fact(3)=3*fact( 2)
fact(3)=3*2*1
回
推
fact(2)=2*fact( 1)
fact(2)=2*1
归
fact(1)=1
9
练习：利用递归求解下列问题。 有 5 个学生坐在一起， • 问第 5 个学生多少岁？他说比第 4 个学生大 2 岁； • 问第 4 个学生岁数，他说比第 3 个学生大 2 岁； • 问第 3 个学生，又说比第 2 个学生大 2 岁； • 问第 2 个学生，说比第 1 个学生大 2 岁； • 最后问第 1 个学生，他说是 10 岁； • 请问第 5 个学生的年龄是多少？
例4 求 1～n 之间所有素数的和。 问题分析： • 该问题的主体结构是求和运算，而参与求和的数是 1～n
之间的素数。 • 程序编写main函数和判断素数以及求素数和的2个函数。 • 求素数:用2,3,4…… ������ 依次除n，如果n能被2～ ������中任
何一个数整除，则不是素数，否则即是素数。 • 程序分3步求解：
retur输出结果：
{
printf("NO. 5, age: %d\n ", age(5));
return 0;
}
(n 1) (n 1)
13
#include <stdio.h> int main() {
int age(int n); printf("NO. 5, age: %d\n ", age(5)); return 0; } int age(int n) { int c; if(n==1) c = 10; else c = age(n-1) + 2; return(c); }
① 输入n的值；
② 求和运算（在求和计算中调用判断素数函数）；
③ 输出结果。
例4 求 1～n 之间所有素数的和。
#include <stdio.h> #include <math.h> long sum( int n ); int isprime( int m ); int main() {
int n; long s; scanf("%d", &n); s = sum(n); printf("Sum = %ld\n", s); return 0; }