当前位置：文档之家 › c语言--函数的递归调用 ppt课件

c语言--函数的递归调用 ppt课件

  • 格式：ppt
  • 大小：778.00 KB
  • 文档页数：16

下载文档原格式

  / 16

合集下载

C++函数、递推、递归ppt课件

C++函数、递推、递归ppt课件

i = 7 s1 = 2 * (s2 + 1) ; s2 = s1 ;
// S(7) = 2 * (S(8) + 1) // s2 = s1 = S(7)
i = 6 s1 = 2 * (s2 + 1) ; s2 = s1 ;
// S(6) = 2 * (S(7) + 1) // s2 = s1 = S(6)
看一个简单的例子：
1 4
第九讲——函数、递推、递归
递归
有 5 个人坐在一起，问第 5 个人多少岁？ 他说比第 4 个人 大两岁。问第 4 个人岁数，他说比第 3 个人大两岁。问第 3 个人，又说比第 2 个人大两岁。问第 2 个人，说比第 1 个人 大两岁。最后问第 1 个人，他说是 10 岁。请问第 5 个人多 大？
3
第九讲——函数、递推、递归
解题思路：
假设用 S(i) 表示第 i 天没吃之前的桃子数目；
则
S(1) 即为第 1 天所摘的桃子数； S(2) = S(1) * 1/2 – 1 第 2 天没吃之前的桃子数
S(3) = S(2) * 1/2 - 1 第 3 天没吃之前的桃子数
…
…
S(9) = S(8) * 1/2 - 1 第 9 天没吃之前的桃子数
= age(2) + 2 + 2 + 2 // c = age(2) + 2
= age(1) + 2 + 2 + 2 + 2；// c = 10;
2 2
计算年龄程序
第九讲——函数、递推、递归
2 3
第九讲——函数、递推、递归
递归算例（2）
用递归方法计算 n! 算法思路：

函数的递归调用III

函数的递归调用III

求3！即 1×2×3 int fac(int n)
3！=2！ ×3
{ 2！=1！ ×2 i1n！t i=,1t=1;
fo0！r(i==11;i<=n;i++)
ｎ!=１t=t*i;
（ｎ＝０，１）
ｎ!=r(eｎtu－rn １t; )! ×ｎ （ｎ＞１）
}
基本知识 过程演示 练习巩固 应用提高
Recursive Function—
Exercise:
main()
int fac(int n)
{
{
int s;
if(n==0||n==1)
s=fac(3);
return 1;
printf(“\n%d”,s); else
}
return fac(n-1)*n;
}
ห้องสมุดไป่ตู้
基本知识 过程演示 练习巩固 应用提高
Recursive Function— Procedure:
基本知识 过程演示 练习巩固 应用提高
有3个人站在一起，问第3个人多少岁？ 他说比第2个人大２岁;问第2个人岁数-他说比第１个人大２岁; 问第１个人-他说是１０岁。
第3个人的岁数是多少？
大2岁
大2岁
10岁
基本知识 过程演示 练习巩固 应用提高
用age()函数表示一个人的年龄 , 即：age(n)代表第n个人的年龄 则：
基本知识 过程演示 练习巩固 应用提高
int fac(int n) {
if(n==0||n==1) return 1;
else return fac(n-1)*n;
}
s=fac(3); =6 fac(2)*3; =2*3=6 fac(1)*2; =1*2=2 1

PPT-06函数递推和递归

PPT-06函数递推和递归
例：
bool checkprime( int );
15
函数的定义
函数返回值的类型 函数名(类型名 形式参数1，
类型名 形式参数2，. . . )
{
// 函数体
说明部分
语句部分
} 例: bool checkprime( int af )
checkprime 为函数名，要以英文字母开头
bool 是函数值的数据类型，这里是布尔型
18
被调用函数嵌套在 if 语句中，a 是实在参数
if ( checkprime( a ) )主函数 调用
checkprime( af ) 子函数 形式参数
19
实在参数是一个具有确定值的表达式
一个函数在调用子函数时，要将实在参数 赋给形式参数
调用时
17 实在参数 a
17 形式参数 af
实在参数的个数及类型应与形式参数一致。 赋值时前后对应关系不会改变。
两者配合得天衣无缝。
13
在checkprime( int af ) 函数 中，有return 0 和 return 1 两处 不同。
如果先有return 0了，后面 一条return 1 就不起作用了。
不会既执行return 0又执行 return 1。
14
函数的说明
要放在主函数之前，告诉系统 有自定义的子函数可以被调用。
for(i=1; i<=m; i=i+1 )
// 计数循环 i
sum=sum+power( i, l ); // 累加
return sum;
// 返回值sum给函数SOP(n, k)
}
// 自定义函数体结束
31
// 以下函数是被函数SOP(n, k)调用的函数 // 功能：计算p的q次幂

c语言--函数的递归调用PPT参考幻灯片

c语言--函数的递归调用PPT参考幻灯片

第机作业：num(n)= 2* (num(n+1)+1) (n<10)
❖ 说有一只调皮的小猴子,摘了一堆水果,第一天 吃了水果的一半,又多吃了一个;第二天吃了剩 下水果的一半,又多吃了一个;依次类推….到第 十天,发现只剩下了10个水果,请问这只猴子到 底摘了多少个水果?
16
可以看到: 1)、3)为同一问题,都为n –1个盘子借助于一个 空塔移至另一塔上。
10
计
例11 Hanoi问题
第五章 函数
A
B
C
11
计
12
程序如下：
A
B
C
A
B
C
A
B
C
A
B
C
第五章 函数
void move(char getone, char putone) {printf("%c--->%c\n",getone,putone); }
1
第五章 函数
张福祥 主编
辽宁大学出版社
1
计
2
第五章 函数
我们先看这样一个例子:
❖ 说有一只调皮的小猴子,摘了一堆水果,第一天 吃了水果的一半,又多吃了一个;第二天吃了剩 下水果的一半,又多吃了一个;依次类推….到第 十天,发现只剩下了1个水果,请问这只猴子到 底摘了多少个水果?
2
计
3
第五章 函数
第五章 函数
age(int n) { int c;
if(n==1) c=10; else c = age(n-1)+2; return(c) ; }
age(5)
n=5
n=4
n=3
n=2
n=1

函数的递归调用1(精选)28页PPT

函数的递归调用1(精选)28页PPT

21、要知道对好事的称颂过于夸大，也会招来人们的反感轻蔑和嫉妒。——培根 22、业精于勤，荒于嬉；行成于思，毁于随。——韩愈
23、一切节省，归根到底都归结为时间的节省。——马克思 24、意志命运往往背道而驰，决心到最后会全部推倒。——莎士比亚
25、学习是劳动，是充满思想的劳动。——乌申斯基
函数的递归调用1（精选）
26、机遇对于有准备的头脑有特别的 亲和力 。 27、自信是人格的核心。
28、目标的坚定是性格中最必要的力 量泉源 之一， 也是成 功的利 器之一 。没有 它，天 才也会 在矛盾 无定的 迷径中 ，徒劳 无功。- -查士 德斐尔 爵士。 29、困难就是机遇。--温斯顿．丘吉 尔。 30、我奋斗，所以我快乐。--格林斯 潘。
谢谢！
பைடு நூலகம்

C语言与程序设计ppt-第12章递归

C语言与程序设计ppt-第12章递归

第12章 递 归
华中科技大学计算机学院 卢萍
华中科技大学计算机学院C语言课
2021/4/25
程组
1
本章讲授内容
递归（recursion）是一项非常重要的编 程技巧，可以使程序变得简洁和清晰，是 许多复杂算法的基础。本章介绍 递归、递归函数的概念； 递归的执行过程； 典型问题的递归函数设计； 分治法与快速排序； 回溯法； 递归在动态规划等算法中的应用。
12
【例12.3】 设计一个求解汉诺塔问题的算法。
这是一个典型的用递归方法求解的问题。要移动n个 盘子，可先考虑如何移动n 1个盘子。分解为以下3 个步骤：
（1）把A上的n-1个盘子借助C移到B。 （2）把A上剩下的盘子（即最大的那个）移到C。 （3）把B上的n-1个盘子借助A移到C。 其中，第（1）步和第（3）步又可用同样的3步继
2021/4/25
华中科技大学计算机学院C语言课程组
2
12.1 递归概述
递归是一种函数在其定义中直接或间接调用 自己的编程技巧。递归策略只需少量代码就 可描述出解题过程所需要的多次重复计算， 十分简单且易于理解。
递归调用：函数直接调用自己或通过另一函 数间接调用自己的函数调用方式
递归函数：在函数定义中含有递归调用的函 数
续分解，依次分解下去，盘子数目n每次减少1，直 至n为1结束。这显然是一个递归过程，递归结束条 件是n为1。
2021/4/25
华中科技大学计算机学院C语言课程组
13
函数move(n,a,b,c)
为了更清楚地描述算法，可以定义一个函数 move(n,a,b,c)。该函数的功能是：将n个盘 子从木桩a上借助木桩b移动到木桩c上。算法 的第（1）步和第（3）步的实现都是递归调 用，分别为move(n-1,a,c,b)和move(n1,b,a,c)。

函数的递归调用_C语言程序设计（第2版）_[共4页]

函数的递归调用_C语言程序设计（第2版）_[共4页]

121 return s; }/*函数名：fac*//*形参：n,int 型*//*返回值：long 型*//*功能：求n!的值*/ long fac(int n) { int i; long t=1;for(i=1;i<=n;i++) t=t*i; return t; }程序运行结果如图5-16所示。

程序分析：在该程序中定义了两个函数，sum 函数用来求1!+2!+…+n!的值，fac 函数用来求n!的值。

由于sum 函数的累加通项为i ！，所以sum 函数中对fac 函数进行了调用。

这里要注意一点，虽然sum 函数和fac 函数的形参都是n ，但它们是不相干的，函数的形参变量只在本函数内有效，离开了本函数，形参变量也就消失了。

在主程序mian 中，调用了sum(x)求分子，sum(y)求分母，由于sum 函数返回值是long 型，因此表达式sum(x)/sum(y)的值也为long 型，这可能导致结果不正确，因此这里需要把分子或分母强制转换类型成float 型。

5.5.2 函数的递归调用一个函数在程序运行的过程中，直接或间接地调用自己称为递归调用。

Ｃ语言允许函数的递归调用，递归调用示意图如图5-17所示。

图5-17 递归调用示意图执行递归函数将反复调用该函数自身，每调用一次就进入新的一层，因此递归函数一定要有控制终止递归调用的语句。

没有控制的递归是毫无意义的，例如：void p() { printf("****");p(); }是一个递归函数，但是该函数将无休止地调用其本身，是一个死循环。

很明显，这种不会终止递归的程序是不正确的。

为了防止递归无终止地进行，常用的办法是在递归中加入条件判断，满足某种条件后就不再作递归调用，然后逐层返回。

下面我们来看一个递归调用的例子。

【例5.9】 用递归法计算n!。

n!可以表示为：图5-16 例5.8程序运行结果。

C语言递归算法PPT演示课件

C语言递归算法PPT演示课件

for (k=1;k<=10;k++)
cin>>a[k];
cin>>x;
search(x,L,R);
system("pause");
} void search(int x,int top,int bot) //二分查找递归过程
{
int mid;
if (top<=bot)
{ mid=(top+bot)/2;
an加入到k个子集中的任一个中去，共有k种加入方式，这样对
于an的每一种加入方式，都可以使集合划分为k个子集，因此
根据乘法原理，划分数共有k * S(n－1，k)个。
•16
综合上述两种情况，应用加法原理，得出n个元素的集合 ｛a1，a2，……，an｝划分为k个子集的划分数为以下递归公 式：S(n，k)＝S(n－1，k－1) + k * S(n－1，k) (n>k，k>0)。
确定n个元素a1 ，a2 ，……，an 放入k个无标号盒子中去
的划分数S(n，k)。
【输入样例】setsub.in
23 7
【输出样例】setsub.out
4382641999117305
•15
【算法分析】
先举个例子，设S＝｛1，2，3，4｝，k＝3，不难得出S有 6种不同的划分方案，即划分数S(4，3)=6，具体方案为：
int s(int n, int k)
//数据还有可能越界，请用高精度计算
{
if ((n < k) || (k == 0)) return 0;
//满足边界条件，退出
if ((k == 1) || (k == n)) return 1;

语言函数的嵌套调用和递归调用 PPT

语言函数的嵌套调用和递归调用 PPT
语言函数的嵌套调用和递归调用
5、4、2 函数得递归调用(嵌套调用得特例 )
概念:函数直接或间接地自我调用称为递归函数。
int fun1(int x)
int fun1(int x)
int fun2(int t)
{
{
{
…
…
…
z=fun1(y);
z=fun2(y);
c=fun1(a);
…
…
…
}
直接引用自身 } 间接引用自身
改定义范围。
G得范围
#define G 9、8 void main(void ) { … } #undef G
#define R 3、0 #define PI 3、14159 #define S PI*R*R printf(“S=%f”,S);
不替换
⑷ 宏定义允许嵌套(在字符串中使用已定义得宏名)。
printf(“\n”);
}
外部变量应用见p143 例 5、
19
综
#include<stdio、h> int i=1;
合 void other(void);
举
void main() { static int a;
例: int b=-10,c=0;
运行结果:
i=1,a=0,b=-10,c=0 i=33,a=4,b=0,c=15 i=33,a=0,b=-10,c=8 i=75,a=6,b=4,c=15
printf(“i=%d,a=%d,b=%d,c=%d\n”,i,a,b,c);
c=c+8;
other();
printf(“i=%d,a=%d,b=%d,c=%d\n”,i,a,b,c);
i=i+10; other();

C语言递推与递归PPT课件

C语言递推与递归PPT课件
• 使用递归函数编程
• void qsort(int array[], int start, int end) • 把数组下标为start到end的元素进行快速排序第18页/共25页快速排序问题5
7
3
8
1
4
2
6
2
7
3
8
1
4
5
6
2
5
3
8
1
4
7
6
2
4
3
8
1
5
7
6
2
4
3
5
1
8
7
6
2
4
3
1
5
8
7
6
1
4
3
2
第16页/共25页
汉诺塔问题
第17页/共25页
快速排序问题
• 快速排序思路如下
• 将要排序的数据放在数组array中 • 取a[0]变在变量m中，通过分区处理把m排在适当的位置，使
m左边的数都比m小，m右边的数都比m大 • 按照常上面的思路分别处理m左边和右边的数据 • 如果分区长度是1，停止处理
• 思路提示
• m个球取出来的n个，包含两种情况：n在其中和n不在其中
• 编程实现
• 使用递归思想 • 编写递归函数 int cmn(int m, int n)
第12页/共25页
计算组合数
第13页/共25页
汉诺塔问题
• 据说在古代印度bramah神庙中，有个和尚整天把3根 柱子上的金盘倒来倒去。初始在柱子A上有64个盘子串 在一起，每一个盘子都比它下面的盘子小，可以在ABC 三个柱子之间互相移动，最终要全部移动到柱子C上。 移动规则如下：每次只允许移动一个，且较大的盘子永 远不能放在较小的盘子上。

函数的递归调用_C语言程序设计教程_[共2页]

函数的递归调用_C语言程序设计教程_[共2页]
第 5 章 函数 105
for(i=0;i<rows;i++) /*输入每个同学的成绩*/ {
printf("请输入第%d 个同学的成绩:",i+1);
for(j=0;j<3;j++)
{
scanf("%d",&a[i][j]);
}
}
return;
}
void cal(int a[ ][3], float b[ ],int len)
图 5-4 函数的递归调用
for(i=0;i<len;i++)
{ printf("第%d 个同学的平均成绩：%.2f\n",i+1,b[i]);
} return; }
与例 4-6 相比较，上面程序的主函数简洁明了，体现了“分而治之”的程序设计思想。
5.4 函数的递归调用
函数直接或间接地调用函数本身，称为函数的递归调用。如果一个函数的函数体内， 通过调用语句调用函数本身，称为直接递归调用；如果某函数调用其他函数，而其他函数又调 用本函数，则称为间接递归调用。函数的直接递归调用和间接递归调用的形式如图 5-4 所示。
{
int i,j;
for(i=0;i<len;i++)
{ for(j=0;j<3;j++) /*将 3 门课程的成绩累加*/
{
b[i]+=a[i][j];
} b[i]/=3;
/*计算 3 门课程的平均成绩*/
}
return;
}
void output(float b[ ],int len)
{Hale Waihona Puke int i;

C语言递归函数调用PPT课件

C语言递归函数调用PPT课件

知识点精讲
【解析】第10天:1个桃子。第9天:设第9天有x个桃子，x-(x/2+1)= 1，解x=4。以此类推计算 出10、22、46、…，得出第n项等于(前一项+1)*2.
列出求某一天桃子数的公式:
#include <stdio.h> int fun(int day) { if(day==1) return 1; /*最后一天桃子的数量为1*/ return(fun(day-1)+1)*2;
知识点精讲
s=f(&a[0],3); printf("%d\n" ,s); } 4.下列程序的运行结果是___f_(_n_)_=_2________ #include″stdio.h″ int f（int n）｛ if（n<=2） return 1; else return f（n-1）+f（n-2）; ｝ main（）｛ int n=5; printf（″f（n）=%d\n″，f（3））; ｝
第八章 递归函数调用
考纲要求
递归函数编程方法。
知识准备
高频考点:递归函数调用、用递归函数设计算法。 重难点分析:用递归函数设计算法。
知识点精讲
知识点1 递归函数
知识点分析 在调用一个函数的过程中出现直接或间接地调用该函数本身，称为函数的递归调用。C语言的 特点之一就在于允许函数的递归调用。 巩固提高 1.下列程序的运行结果是_____5_5______ L1 #include <stdio.h> L2 int fun(int n) L3 { L4 if(n==1) return 1; /*当n==1时，函数调用结束*/ L5 return fun(n-1)+n; /*前n项的和等于前n-1项的和再加上n*/ L6 } L7 void main( ) L8 {
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

时,保证三个塔始终是大盘在下,小盘在上，
并且每次只能移动一个盘子。ABC Nhomakorabean个盘子
9
PPT课件
10
第五章 函数
必须用递归方式解决
1) 先将A塔n –1个盘子借助于C移至B上
2) 将A上剩下的一个移至C上.
3) 将B上n –1个盘子借助于A移至C上.
可以看到: 1)、3)为同一问题,都为n –1个盘子借助于一个 空塔移至另一塔上。
必须有递归结束条件
5
PPT课件
6
第五章 函数
思考如下问题：
例1: 有5个人坐在一起,问第5个人多少岁,
他说比第4个人大2岁;问第4个人岁数,他说比 第3个人大2岁;问第3个人,又说比第2个大2岁; 问第2个人，说比第1个人大2岁；最后问第1 个人，他说他10岁；请问第5个人多大?
我10岁
比她大2岁
age(5)
n=5
n=4
n=3
n=2
n=1
c=age(4)+2 c=age(3)+2 c=age(2)+2 c=age(1)+2 c=10
c=16+2=18 c=14+2=16 c=12+2=14 c=10+2=12
8
PPT课件
9
例2: 汉诺塔(Hanoi)问题
第五章 函数
问题: 将A塔上n个盘子移至C(借助于B)。 移动
…… return(2*z) ; }
int f1(x)
int x ; { int y, z ;
……
z =f2(y) ;
…… return(2*z) ; }
int f2(t)
int t ; { int a, c ;
……
c =f1(a) ;
…… return(3+c) ; }
说明
C语言对递归函数的自调用次数没有限制
6
PPT课件
7
第五章 函数
设 age 表示年龄，则有如下:
age(5) =age(4)+2
age(n) =
age(4) =age(3)+2
10
(n=1)
age(n-1)+2 (n>1)
age(5) =16+2=18
age(4) =14+2=16
age(3) =age(2)+2
age(3) =12+2=14
main() { int n; scanf("%d",&n); hanoi(n,‘A',‘B',‘C'); }
12
PPT课件
13
第五章 函数
运行情况如下：
input the number of diskes:3 The step to moving 3 diskes: A >C A >B
C >B A >C B >A B >C A >C
13
PPT课件
14
第五章 函数
在程序中有两个函数:
move (getone, putone) 表示从getone 塔移一个盘子至putone塔
hanoi(n, one, two, three) 表示n个盘子从one塔借助于two塔(空)移 至three塔，调用时塔用字符常量'A' ,' B ', ' C '表示。
16
PPT课件
后(n 一0)部分与原始问题类似
后一部分是原始问题的简化
3
PPT课件
4
二、程序中的递归方式
第五章 函数
1. 直接递归调用：函数直接调用本身 2. 间接递归调用：函数间接调用本身
4
PPT课件
5 直接调用
第五章 函数 间接调用
int f(x)
int x ; { int y, z ;
……
z =f(y) ;
3
第五章 函数
5.4 函数递归调用
许一多、数函学数函递数都归是的用特递点归的形式定义的：
1、定1义：调用一(n个 0函,1)数时直接或间接调用自身, n! n (n 1称)! 之为(函n 数1) 的递归。
2、一个问题能够成为递归必须具备的条件是：
xn

1

x
x n 1
(n 0)
1
第五章 函数
张福祥 主编
辽宁大学出版社
1
PPT课件
2
第五章 函数
我们先看这样一个例子:
说有一只调皮的小猴子,摘了一堆水果,第一天 吃了水果的一半,又多吃了一个;第二天吃了剩 下水果的一半,又多吃了一个;依次类推….到第 十天,发现只剩下了1个水果,请问这只猴子到 底摘了多少个水果?
2
PPT课件
age(2) =age(1)+2
age(2) =10+2=12
age(1) =10
7
PPT课件
8
main() {
printf(“%d”, age(5)); }
第五章 函数
age(int n) { int c;
if(n==1) c=10; else c = age(n-1)+2; return(c) ; }
10
PPT课件
例11 Hanoi问题
第五章 函数
A
B
C
11
PPT课件
12
程序如下：
A
B
C
A
B
C
A
B
C
A
B
C
第五章 函数
void move(char getone, char putone) {printf("%c--->%c\n",getone,putone); }
void hanoi(int n,char A,char B,char C) { if(n==1) move(A,C); else { hanoi(n-1,A,C,B); move(A,C); hanoi(n-1,B,A,C);} }
14
PPT课件
15
小
第五章 函数
结
本节课主要介绍的内容： 1. 函数递归的定义 2. 函数递归的特点 3.函数递归调用的方式
15
PPT课件
16
第五章 函数
1
(n=10)
上机作业：num(n)= 2* (num(n+1)+1) (n<10)
说有一只调皮的小猴子,摘了一堆水果,第一天 吃了水果的一半,又多吃了一个;第二天吃了剩 下水果的一半,又多吃了一个;依次类推….到第 十天,发现只剩下了10个水果,请问这只猴子到 底摘了多少个水果?