实例分析递归算法实例分析递归算法
(作者:武冈职业中专 陈小亮 林文芳)
摘要
本文是根据我多年教学的经验结合学生学习过程中的难点、理解缺陷,并密切配合《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,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。