搜索
当前位置: 678彩票官网 > 递归例程 >

什么情况下可以利用递归来解决问题?再写递归程序时应注意是什么

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

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

  比如阶乘,也就是说求n可以先求n-1,以此类推,到1,这类问题都可以用递归解决,菲波拉锲数也可以递归。因为递归是总是调用自身解决问题,所以,必须有结束条件,否则会出问题,导致内存卡爆

  如果一个对象的描述中包含它本身,我们就称这个对象是递归的,这种用递归来描述的算法称为递归算法。

  从前有座山,山上有座庙,庙里有个老和尚在给小和尚讲故事,他说从前有座山,山上有座庙,庙里有个老和尚在给小和尚讲故事,他说……

  在设计递归算法中,如何将一个问题转化为递归的问题,是初学者面临的难题,下面我们通过分析汉诺塔问题,看看如何用递归算法来求解问题;

  例1:汉诺塔问题,有A、B、C三根柱子。A柱子上按从小到大的顺序堆放了N个盘子,现在要把全部盘子从A柱移动到C柱,移动过程中可以借助B柱。移动时有如下要求:

  如果N比较大时,需要很多步才能完成,我们先考虑是否能把复杂的移动过程转化为简单的移动过程,如果要把A柱上最大的盘子移动到C柱上去,必须先把上面的N-1个盘子从A柱移动到B柱上暂存,按这种思路,就可以把N个盘子的移动过程分作3大步:

  其中N-1个盘子的移动过程又可按同样的方法分为三大步,这样就把移动过程转化为一个递归的过程,直到最后只剩下一个盘子,按照移动一个盘子的方法移动,递归结束。

  从上面的例子我们可以看出,在使用递归算法时,首先弄清楚简单情况下的解法,然后弄清楚如何把复杂情况归纳为更简单的情况。

  在信息学奥赛中有的问题的结构或所处理的数据本身是递归定义的,这样的问题非常适合用递归算法来求解,对于这类问题,我们把它分解为具有相同性质的若干个子问题,如果子问题解决了,原问题也就解决了。

  [问题描述]给出一棵二叉树的中序与后序排列。求出它的先序排列。(约定树结点用不同的大写字母表示,长度≤8)。

  从遍历的定义可知,后序排列的最后一个字符即为这棵树的根节点;在中序排列中,根结点前面的为其左子树,根结点后面的为其右子树;我们可以由后序排列求得根结点,再由根结点在中序排列的位置确定左子树和右子树,把左子树和右子树各看作一个单独的树。这样,就把一棵树分解为具有相同性质的二棵子树,一直递归下去,当分解的子树为空时,递归结束,在递归过程中,按先序遍历的规则输出求得的各个根结点,输出的结果即为原问题的解。

  递归算法不仅仅是用于求解递归描述的问题,在其它很多问题中也可以用到递归思想,如回溯法、分治法、动态规划法等算法中都可以使用递归思想来实现,从而使编写的程序更加简洁。

  比如上期回溯法所讲的例2《数的划分问题》,若用递归来求解,程序非常短小且效率很高,源程序如下

  有些问题本身是递归定义的,但它并不适合用递归算法来求解,如斐波那契(Fibonacci)数列,它的递归定义为:

  上面的递归过程,调用一次产生二个新的调用,递归次数呈指数增长,时间复杂度为O(2n),把它改为非递归:

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

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

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

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

回顶部