递归算法与递归算法的应用

北方先森丶IP属地: 北京
0.06字数 835

这一讲,我们来聊聊递归法算。

概念

什么是递归算法?若一个算法直接地或间接地调用自己本身,则称这个算法是递归的。

概念很容易理解吧~也就是方法调用自己本身,但是,递归算法的使用是有条件的!

条件

适用于递归算法求解问题的充分必要条件有以下两点:

①. 该问题具有某种可借用的类同自身的子问题描述的性质。(我也知道这个根本看不懂说的是神马)

②. 某一有限步骤的子问题(也称作本原问题)有直接的解存在。:)

当一个问题存在上述两个基本要素的时候,设计该问题的递归算法时应注意以下两点:

①. 把对原问题的求解表示成对子问题求解的形式

②. 设计递归出口(很重要,不然就成死循环啦!)

概念固然是枯燥的,结合实际应用才能更好的理解,首先先看第一个应用,很简单哦!

递归算法应用实例一:求 n! 问题

就说了,很简单:)

废话少说,直接上图

阶乘的实现很简单,不过却能很好的体现递归的思想!

递归算法应用实例二:设计折半查找递归算法

折半查找 ,也称二分查找(binary search),是一个查找效率快的方法。

折半查找的基本过程:从数组的中间元素开始,如果中间元素正好是要查找的元素,则查找结束;如果我们要查找的元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。每一次的查找,都能将查找范围缩小一半。

我们同样也可以用递归算法来实现它!

递归算法应用实例三:求斐波那契数列前N项之和

斐波那契数列:1、1、2、3、5、8、13.........

从第三项起,每项是前两项之和。

同样可以用递归方式的解决~上图!

递归算法应用实例四:求两个正整数的最大公约数

原理大家应该很明白了~

总结

我们总结一下递归算法的执行过程中的特点

①. 函数名相同。

②. 不断的自调用。

③. 最后被调用的函数要最先被执行。

递归算法并不难理解,但不是什么情况都能用的哦,理解递归的要求和特点,就不会用错了!

下一讲我们将介绍回溯法以及迷宫算法 大家持续关注阿:)

PS:有什么问题或者不解的地方可以评论,我都会一一就行回复的,如果有错误或者言语不明的地方,还请大神多多指点!

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。
4人点赞
总资产1共写了1.3W字获得30个赞共19个粉丝

推荐阅读更多精彩内容

  • Spring Cloud为开发人员提供了快速构建分布式系统中一些常见模式的工具(例如配置管理,服务发现,断路器,智...
    卡卡罗2017阅读 134,837评论 18 139
  • 今天继续忙碌,因为小姨一家及儿媳妇年后都过来玩,想着年后的家族大聚,又想添置多一点的物品。 然后带妈妈一家人去了宜...
    米小喆阅读 119评论 0 0
  • 村长突然想到海明威。 最初吸引村长的是海明威的作品,后来引起村长深思的是他的死。 海明威被誉为硬汉,有人还称他为英...
    那株柏阅读 200评论 0 0
  • 0213 1.Android内存泄露总结 (1)Java内存分配策略:分别是静态分配,栈式分配,和堆式分配,对应的...
    小甜妮子__阅读 414评论 0 0
  • 参考资料:1.《Android开发艺术探索》 http://www.jianshu.com/p/057832528...
    zhaoyubetter阅读 190评论 0 0