为了正常的体验网站,请在浏览器设置里面开启Javascript功能!

实例分析递归算法

2017-09-19 4页 doc 37KB 46阅读

用户头像

is_977556

暂无简介

举报
实例分析递归算法实例分析递归算法 (作者:武冈职业中专 陈小亮 林文芳) 摘要 本文是根据我多年教学的经验结合学生学习过程中的难点、理解缺陷,并密切配合《C程序设计》教材内容所写。本文采用实例验证,实例讲解介绍了我对递归算法的认识,主要从递归的概念,递归过程的描述,递归算法的适用范围,优缺点及编程实例验证几个部分进行说明。 关键字:递归; 递归算法; 函数; 指针 递归分析 一、递归的概念 一个过程(或函数)直接或间接调用自己,这种过程(或函数)叫递归过程(或函数).递归算法是把问题转化为规模缩小了的同类问题的子问题。 二、递归算法 递归过程...
实例分析递归算法
实例递归算法 (作者:武冈职业中专 陈小亮 林文芳) 摘要 本文是根据我多年教学的经验结合学生学习过程中的难点、理解缺陷,并密切配合《C程序设计》教材内容所写。本文采用实例验证,实例讲解介绍了我对递归算法的认识,主要从递归的概念,递归过程的描述,递归算法的适用范围,优缺点及编程实例验证几个部分进行说明。 关键字:递归; 递归算法; 函数; 指针 递归分析 一、递归的概念 一个过程(或函数)直接或间接调用自己,这种过程(或函数)叫递归过程(或函数).递归算法是把问题转化为规模缩小了的同类问题的子问题。 二、递归算法 递归过程一般通过函数或子过程来实现。递归算法:在函数或子过程的内部,直接或者间接地调用自己的算法。 三、递归算法的特点 (1) 递归就是在过程或函数里调用自身。 (2) 在使用递归策略时,必须有一个明确的递归结束条件,称为递归出口。 (3) 递归算法解题通常显得很简洁,但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。 (4) 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。 四、递归算法要求 递归算法所体现的“重复”一般有三个要求: 一、每次调用在规模上都有所缩小; 二、是相邻两次重复之间有紧密的联系,前一次要为后一次做准备(通常前一次的输出就作为后一次的输入); 三、在问题的规模极小时必须用直接给出解答而不再进行递归调用,因而每次递归调用都是有条件的,无条件递归调用将会成为死循环而不能正常结束。 实例分析递归算法 一、程序(1)分析递归调用 f(8)=8-f(6)   f(8)=8-1 f(6)=6-f(4) f(6)=6-5 f(4)=4-f(2) f(4)=4-(-1) f(2)= 2-f(0) f(2)=2-3 f(0)=3 f (int x) 递归出口 {int p; if(x==0||x==1)return 3; 递推 过程 回推 过程 p=x-f(x-2); return p; } main() {printf("%d\n",f(8));}_ 分析:因为f(8)=8-f(6),因此,必先求出f(6),f(6)=6-f(46),因此,必先求出f(4),f(4)=4-f(2),因此,必先求出f(2),f(2)=2-f(0),而f(0)=3,由此也就能求出f(2);又因为 f(4)=4-f(2),因此,如果能求出f(4),则也就能求出f(6),又由f(6)得出f(8)。这是按回推过程逆推回去,整个过程就叫递归。 根据上述分析可知,求解可分成两个阶段:第一阶段是由未知逐步推得已知的过程,称为“回推”;第二阶段是与回推过程相反的过程,即由已知逐步推得最后的结果的过程,称为“递推”。                                      根据算法图及运行结果分析如下: 函数的递归调用与一般的函数调用相比,在下面三个方面是一样的: ①每次调用都把该函数看作是一个单独函数。 ②该函数的形参和有关变量也被看作是局部变量。 ③每调用一次该函数,就建立一个属于本次调用的动态数据区,即为局部变量在栈区分配一定的空间;直到控制返回时,才撤销该动态数据区。 递归调用的优点是程序简洁、清晰,代码紧凑;缺点是存储空间占用较多,且时间效率很差。 二、(在递归中通过指针变化分析)——运用递归法将输入的一个3位数按相反的顺序输出,例输入123,输出字符”321”。 程序一:重点注意指针变量a 在递归运行中的变化。 #include 递归出口并修改下次调用条件 int x=0; void fun(char *a,int n) {int i;printf("%d:%o  ",x++,a); if((i=n/10)!=0) {fun(a++,i);printf("%d:%o  ",x++,a);} *a=n%10+'0';  } char str[10]=""; main() {int number;scanf("%d",&number); fun(str,number);puts(str);} 运行结果是: 根据程序及运行结果得知: 指针变量a++运算后a 的值在递归过程中因不断发生变化,但系统不能准确地记忆其值,回推过程中没有变化,在递推过程中不能准确地递推,导致指针a 的数据出现漏洞,最终只保留了数字1与3丢失中间数据2。 程序二:将上面程序稍作修改,同样重点注意指针变量a 在递归运行中的变化。 #include 递归出口并修改下次调用条件 int x=0; void fun(char *a,int n) {int i;printf("%d:%o  ",x++,a); if((i=n/10)!=0) {fun(a+1,i);printf("%d:%o  ",x++,a);} *a=n%10+'0';  } char str[10]=""; main() {int number;scanf("%d",&number); fun(str,number); putchar('\n'); printf("%o  %o  %o\n",&str[0],&str[1],&str[2]); putchar(str[0]);putchar(str[1]);putchar(str[2]);} 运行结果为: 根据程序及运行结果得知: 指针变量a+1作为再次递归的实参,因a自始至终没有发生过变化,回推与递推都能顺利地进行,a 初始地址是626加1后成627 再加1后成630(8进制),递推完成后最终又恢复到626,最后626地址中保存了字符’3’, 627地址中保存了字符’2’, 630地址中保存了字符’1’。最后达到了题目的要求按相反的顺序输出了字符”321”。 递归小结 递归是《C程序设计》课程中一个较难理解的内容之一,主要原因是我们从程序的代码上只能看到回推的过程,不能直接看到递推的过程,递推的过程在程序运行中自动完成,我们只能过回推的算法递归回去才能得到最终的结果。只有理清递归的运算过程才能按需要设计递归设计程序,只有看懂了递归设计思路才能知道递归后的运算结果。 参考文献 [1]、谭浩强著.C语序设计(第四版).北京:清华大学出版社,2010 [2]、谭浩强著.C++语序设计.北京:清华大学出版社,2004 [3]、C语言教程 :凯利(Kelley(Pohl): 机械工业 出版时间: 2007 [4]、(美)福伊尔著,杨涛等译出版社:人民邮电出版社出版日期:2007
/
本文档为【实例分析递归算法】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑, 图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。 本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。 网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。

历史搜索

    清空历史搜索