搜索
当前位置: 678彩票官网 > 递归算法 >

什么是递归算法?有什么作用?

gecimao 发表于 2019-04-18 14:23 | 查看: | 回复:

  可选中1个或多个下面的关键词,搜索相关资料。也可直接点“搜索资料”搜索整个问题。

  在过程和函数的学习中,我们知道调用子程序的一般形式是:主程序调用子程序A,子程序A调用子程序B,如图如示,这个过程实际上是:

  @当主程序执行到调用子程序A语句时,系统保存一些必要的现场数据,然后执行类似于BASIC语言的GOTO语句,跳转到子程序A(为了说得简单些,我这里忽略了参数传递这个过程)。

  @子程序B执行完所有语句后,跳转回子程序A调用子程序B语句的下一条语句(我这又忽略了返回值处理)

  做个比较:我在吃饭(执行主程序)吃到一半时,某人叫我(执行子程序A),话正说到一半,电话又响了起来(执行子程序B),我只要先接完电话,再和某人把话说完,最后把饭吃完(我这饭吃得也够累的了J)。

  也就是说要求3!,我们必须先求出2!,要求2!,必须先求1!,要求1!,就必须先求0!,而0!=1,所以1!=0!*1=1,再进而求2!,3!。分别用函数表示,则如图:

  我们可以观察到,除计算0!子程序外,其他的子程序基本相似,我们可以设计这么一个子程序:

  那么当执行主程序语句s=factorial(3)时,就会执行factorial(3),但在执行factorial(3),又会调用factorial(2),这时大家要注意,factorial(3)和factorial(2)虽然是同一个代码段,但在内存中它的数据区是两份!而执行factorial(2)时又会调用factorial(1),执行factorial(1)时又会调用factorial(0),每调用一次factorial函数,它就会在内存中新增一个数据区,那么这些复制了多份的函数大家可以把它看成是多个不同名的函数来理解;

  但我们这个函数有点问题,在执行factorial(0)时,它又会调用factorial(-1)。。。造成死循环,也就是说,在factorial函数中,我们要在适当的时候保证不再调用该函数,也就是不执行res=factorial(I-1)*i;这条调用语句。所以函数要改成:

  本来这个问题我们过去常用循环累加的方法。而这里如要用递归的方法,必须考虑两点:

  @执行第一次调用inorder1,T指向顶结点,T不为空,所以第二次调用inorder2;

  @T指向顶结点的左子树结点也就是B,不为空,所以第三次调用inorder3;

  @T指向B结点的左子树结点,为空,所以什么都不执行,返回inorder2;

  @T指向B结点的右子树结点,为空,所以什么都不执行,返回inorder2;

  @T指向A结点的右子树结点,为空,所以什么都不执行,返回inorder1;

  展开全部我感觉递归较接近思维的方式,用于解一些光用循环解起来较复杂的问题

本文链接:http://windsorflowers.net/diguisuanfa/109.html
随机为您推荐歌词

联系我们 | 关于我们 | 网友投稿 | 版权声明 | 广告服务 | 站点统计 | 网站地图

版权声明:本站资源均来自互联网,如果侵犯了您的权益请与我们联系,我们将在24小时内删除。

Copyright @ 2012-2013 织梦猫 版权所有  Powered by Dedecms 5.7
渝ICP备10013703号  

回顶部