




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、1,Essential of Lecture Six :,一、递归 二、汉诺塔问题 三、递归与非递归的转化,第七讲 栈与递归,难点,2,一、递归,递归是程序设计中最有力的方法之一。 优点:采用递归编出的程序简洁、清晰,程序结构符合结构化程序设计,可读性好。 问题:编译程序是如何处理这类带有递归调用功能的程序的?如果使用了无递归功能的程序设计语言,应该如何设计和实现这类程序呢?,3,一、递归,递归: 在定义自身的同时又出现了对自身的调用。 直接递归函数:如果一个函数在其定义体内直接调用自己,则称直接递归函数。 间接递归函数:如果一个函数经过一系列的中间调用语句,通过其它函数间接调用自己,则称间接
2、递归函数。,4,数学中常常利用递归手段来定义一些概念,如求阶乘的运算。n的阶乘定义为: n * ( n 1 ) ! n0 n! = 1 n=0,例如:,显然,该递归的出口是 0! =1。,5,求阶乘的算法如下: long fac (int n) long p; if (n=0| n=1) p=1; else p=n*fac(n-1) ; return p; void main() long x=fac(5); cout0的一般情况采用如下分治策略: (1)将1至n-1号盘从 a 轴移动至 b 轴,可递归求解Hanoi(n-1, a, c, b); (2)将 n号盘从 a 轴移动至 c 轴; (
3、3)将1至n-1号盘从b轴移动至c轴,可递归求解 Hanoi(n-1, b, a, c)。 在(1)与(3)中需要移动圆盘次数T(n-1),(2)需要移动一次圆盘。可得如下的关系: T(n)=2T(n-1)+1 展开上式可得: T(n) =2T(n-1)+1 =22T(n-2)+1+1 =22T(n-2)+1+2 =2nT(n-n)+1+2+2n-1 =2n-1,13,二、汉诺塔问题的递归算法,void move (char x, int n, char y) cout移动n号盘子从柱子x到柱子1的情况下有如下递推关系成立: p(i,x)=(2i-1)xp(i-1,x)(i-1)p(i-2,x
4、)/i 显然,可以利用以上递推关系,从i=2开始,逐步增大i的值,依次求解第i阶勒让德多项式的值;当i=n时,便求到了p(n,x)的值。在整个求解过程中不需要进行试探和回溯,因而该问题属于简单递归问题,完全可以使用递推技术加以实现。,勒让德多项式的非递归实现,36,定义两个变量pre1和pre2,分别记录上述递推关系中两个子问题的解,即 pre1=p(i-2,x),pre2=p(i-1,x), 且pre1和pre2的值始终随着i的值的改变而发生变化:每当新求出第i阶多项式的值后,i的值要增加1,而在此之前应该修改pre1和pre2的值,用pre1记录pre2当前的值,而用pre2记录新求出的多
5、项式的值,直至i=n。,float p ( int n, float x ) float pre1,pre2,a,b,valuep; int i; if (n=0) return(1.0); else if (n=1) return(x);,37,else pre1=1.0; pre2=x; for (i=2;i=n;+i) a=2*i-1; b=i-1; valuep=(a*pre2*x-b*pre1)/i; pre1=pre2; pre2=valuep; return(valuep); ,勒让德多项式的非递归算法,38,复杂递归程序到非递归程序的转换,复杂递归问题在求解的过程中无法保证求解
6、动作一直向前,往往需要设置一些回溯点,当求解无法进行下去或当前处理的工作已经完成时,必须退回到所设置的回溯点,继续问题的求解。因此,在使用非递归方式实现一个复杂递归问题的算法时,经常使用栈来记录和管理所设置的回溯点。,39,按中点优先的顺序遍历线性表问题: 已知线性表list以顺序存储方式存储,要求按以下顺序输出list中所有结点的值:首先输出线性表list中点位置上的元素值,然后输出中点左部所有元素的值,再输出中点右部所有元素的值;而无论输出中点左部所有元素的值还是输出中点右部所有元素的值,也均应遵循以上规律。,例如:,40,例如,已知数组list中元素的值为: 18 32 04 09 26
7、 06 10 30 12 08 45 则list中元素按中点优先顺序遍历的输出结果为: 06 04 18 32 09 26 12 10 30 08 45 试采用递归和非递归算法实现该遍历问题。,41,#define MAXSIZE 20 typedef int listarrMAXSIZE; void listorder(listarr list, int left, int right) int mid; if (left=right) mid=(left+right)/2; coutlistmid“ ”; listorder(list,left,mid-1); listorder(list
8、,mid+1,right); ,递归实现算法,42,#define MAXSIZE 20 typedef int listarrMAXSIZE; void listorder(listarr list, int left, int right) typedef struct int l; /*存放待处理数组段的起点下标*/ int r; /*存放待处理数组段的终点下标*/ stacknode; /*栈中每个元素的类型*/ stacknode stackMAXSIZE; int top, i, j, mid; /*top为栈顶指针*/,非递归实现算法,43,if (left=right) /*数组段不为空*/ top= -1; i=left; j=right; while (i=j | top!=-1) /*当前正在处理的数组段非空或栈非空*/ if (i=j) mid=(i+j)/2; coutlistmid“ ”;
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 社区社区服务经济学研究管理基础知识点归纳
- 石大学前儿童保育学课件5-1健康教育
- DDX42在调控RNA剪接与认知功能中的作用研究
- 车辆智能驾驶技术在农业运输中的应用-洞察阐释
- 创新驱动与绿色园区产业链协同发展
- 加快数字化转型助力产业提质增效
- 康师傅一刻馆奶茶上市计划创意制作执行细案
- 2025至2030年中国煮牙盒螺丝行业投资前景及策略咨询报告
- 2025至2030年中国灯笼布行业投资前景及策略咨询报告
- 2025至2030年中国活动板架行业投资前景及策略咨询报告
- 高等职业学校铁道机车车辆制造与维护专业岗位实习标准
- 炸药成型与装药的制备-性能关系
- 2024至2030年中国医疗信息化行业趋势研究及投资前景分析报告
- 2024年山东省德州经开区小升初数学试卷
- 剧毒易制爆化学品防盗、防抢、防破坏及技术防范系统发生故障等状态下的应急处置预案
- HY/T 0409-2024近岸海域水质浮标实时监测技术规范
- 《正常分娩》课件
- JGJ25-2010 档案馆建筑设计规范
- 医之有“道”告别难“咽”之隐-基于5A护理模式在脑卒中恢复期患者改善吞咽障碍中的应用
- CJT163-2015 导流型容积式水加热器和半容积式水加热器
- JT-T-1180.1-2018交通运输企业安全生产标准化建设基本规范第1部分:总体要求
评论
0/150
提交评论