1 / 28
文档名称:

第05章_递归.ppt

格式:ppt   页数:28页
下载后只包含 1 个 PPT 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

第05章_递归.ppt

上传人:中国课件站 2011/9/6 文件大小:0 KB

下载得到文件列表

第05章_递归.ppt

文档介绍

文档介绍:第5章递归
递归与递归程序设计
递归程序到非递归程序的转换
递归程序设计的应用实例
递归程序执行过程的分析
递归与递归程序设计 在一个函数的定义中出现了对自己本身的调用,称之为直接递归;或者一个函数p的定义中包含了对函数q的调用,而q的实现过程又调用了p,即函数调用形成了一个环状调用链, 这种方式称之为间接递归。递归技术在算法和程序设计中是一种十分有用的技术,许多高级程序设计语言均提供了支持递归定义的机制和手段。 例1 试编一个递归函数,求正整数n的阶乘值n!。 用fact(n)表示n的阶乘值,据阶乘的数学定义可知: 1 n=0 fact(n) = n*fact(n-1) n>0
该问题的算法为: int Fact ( int n ) { int m; if (n= =0) return(1); else { m=n*Fact(n-1); return(m); } } 例2 试编一个递归函数,i级数的值。 假设使用Fibona(n)i级数的值, i级数的计算公式: 1 n=1 Fibona(n)= 1 n=2 Fibona(n-1)+ Fibona(n-2) n>2
该问题的算法为: int Fibona ( int n ) { int m; if (n= =1) return (1); else if (n= =2) return(1); else { m=Fibona(n-1)+ Fibona(n-2); return (m); } }
递归程序设计具有以下两个特点: (1)具备递归出口。递归出口定义了递归的终止条件,当程序的执行使它得到满足时,递归执行过程便终止。有些问题的递归程序可能存在几个递归出口; (2)在不满足递归出口的情况下,根据所求解问题的性质,将原问题分解成若干子问题,这些子问题的结构与原问题的结构相同,但规模较原问题小。子问题的求解通过以一定的方式修改参数进行函数自身调用加以实现,然后将子问题的解组合成原问题的解。递归调用时,参数的修改最终必须保证递归出口得以满足。
递归程序执行过程的分析 在递归程序的运行过程中,系统内部设立了一个栈,用于存放每次函数调用与返回所需的各种数据,主要包括:函数调用执行完成时的返回地址、函数的返回值、每次函数调用的实在参数和局部变量。 在递归程序的执行过程中,每当执行函数调用时,必须完成以下任务: (1)计算当前被调用函数每个实在参数的值; (2)为当前被调用的函数分配一片存储空间,用于存放其所需的各种数据,并将这片存储空间的首地址压入栈中; (3)将当前被调用函数的实在参数、将来当前函数执行完毕后的返回地址等数据存入上述所分配的存储空间中; (4)控制转到被调用函数的函数体,从其第一个可执行的语句开始执行。
当从被调用的函数返回时,必须完成以下任务: (1)如果被调用的函数有返回值,则记下该返回值,同时通过栈顶元素到该被调用函数对应的存储空间中取出其返回地址; (2)把分配给被调用函数的那片存储空间回收,栈顶元素出栈; (3)按照被调用函数的返回地址返回到调用点,若有返回值,还必须将返回值传递给调用者,并继续程序的执行。
例3 试编写一个递归函数,在第一行打印输出1个1,在第二行打印输出2个2, ……在第n行打印输出n个n。例如,当n=5时,调用该函数的输出结果为: 1 2 2 3 3 3 4 4 4 4 5 5 5 5 5 该问题的算法为:print ( int n ) { int i; if (n!=0) { print(n-1); for(i=1;i<=n;i++) printf("%d",n); printf("\n");} }
Print(5)
print(4)
for(i=1;i<=5;i++) printf(“%d”,5)
printf(“\n”);
print(3)
for(i=1;i<=4;i++) printf(“%d”,4)
printf(“\n”);
print(2)
for(i=1;i<=3;i++) printf(“%d”,3)
Printf(“\n”);
print(1)
for(i=1;i<=2;i++) printf(“%d”,2)
Printf(“\n”);
print(0)
(1)
(2)
(3)
(4)
(5)
(6)
(7)
(8)
(9)
(10)
Fibona(5)
S0
(1)
m=Fibona(4)+Fibona(3);
return(m);
m=Fibona(3)+Fibona(2);
return(m) ;
(2)
m=Fibon

最近更新

辽宁省鞍山市第三十中学高三数学理下学期期末.. 16页

船舶货物运输代理合同 3页

有关动物的寓言故事(集锦15篇) 13页

过时的职场观念更新 2页

施工员的个人工作总结(精选15篇) 37页

酒店员工大会的心得体会 4页

酒店服务标准8s 2页

酸奶可以减肥吗 2页

重庆万州龙宝中学高三物理下学期期末试题含解.. 11页

重庆北碚区田家炳中学2020-2021学年高二物理月.. 4页

重庆垫江县第五中学2020-2021学年高一生物月考.. 10页

小学音乐教师工作总结(通用5篇) 10页

车辆提档全权委托办理 18页

重庆涪陵区第五中学高一数学文联考试卷含解析.. 11页

车辆挂靠经营协议书 13页

大学生交通安全演讲稿(精选7篇) 10页

在酒店的实习报告(精选8篇) 22页

商品混凝土买卖合同(通用6篇) 28页

重庆隆盛中学2021-2022学年高二英语月考试卷含.. 5页

重庆龙山中学高三物理月考试卷含解析 6页

钢筋工安全操作规程(3) 2页

银行大堂经理的岗位职责 3页

关于小学生科普作文集锦8篇 7页

陕西省咸阳市地掌中学2020-2021学年高三英语期.. 5页

促销活动方案(通用9篇) 31页

车辆借条合同范例3篇 96页

陕西省咸阳市杨凌高新中学2020-2021学年高一数.. 5页

中国寓言故事(通用21篇) 18页

陕西省咸阳市白王中学2020-2021学年高一语文期.. 26页

高处安装、维护、拆除高处作业考试题库及答案.. 17页