《算法图解》NOTE 3 递归1.定义2递归结构2.适用场合3.应用案例

这是《算法图解》的第二篇读书笔记,内容主要涉及递归。

1.定义

递归是一种解决问题的方式。其基本思路是将问题分解为与原问题的解决原理相同但规模更小的子问题后,解决并获得子问题的答案,之后逐步将子问题的答案合并,以获取原文提的答案。

2递归结构

递归在编程中展示的明显特为函数在运行过程中调用函数自身。 形如下方的示例

def recursion_fun(i=0):
    #基递归停止条件 base case
    if i==100:
        return None
    #递归条件 recursive case
    i=I+1
    print ('running the function the' + str (i)+'tiem')
    recursion_fun(i)

上述在运行过程中函数会调用本身,但为避免造成死循环,递归函数会有一个基线条件(base case)用于判断函数何时终止递归。 因此,递归函数的结构分为两部分,基线条件:用于终止递归;递归条件:递归函数用于递归的代码。

2.适用场合

递归主要适用于将问题分解为子问题后,子问题的解法与原问题相同的场合。如简单的阶乘、斐波拉切数列的求和、深度优先搜索和广度优先搜索等。 递归算法能够很好地展示解决问题的思路,但其缺点也很明显,内存的使用率高。因为递归算法运行时,递归函数会不断调用本身。此时,外层的递归函数仍在运行,会占用内存。因此,递归函数的调用次数越多,占用的内存就越大。 综上所述,若对算法的性能要求较高,可考虑使用循环替代递归的思路来解决问题。 例如,有向图的深度优先搜索递归算法,可使用栈结构添加未访问的访问节点,并使用循环来访问由栈结构获取的节点。

3.应用案例

#阶乘,n!为阶乘数
def factor(n,i=0):
    if n<0:
        return None
    if i>n or n=0 or i=1:
        return 1
    i=I+1
    return i*factor(n,i)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏老九学堂

【干货】小白如何熟练掌握C语言随机数!

随机数的使用,是不少小伙伴在学C语言过程中都会遇到的一个坎,今天老九为大家讲解如何在C语言中使用随机数。 通常情况下,使用最多的方法的就是使用rand函数随机生...

3727
来自专栏xiaoxi666的专栏

今日头条笔试题:“最小数字*区间和”的最大值【单调栈】

  利用单调栈,从前向后和从后向前分别遍历一遍数组,得到每个元素的左边界和右边界(边界的定义即为碰到比该元素更小的即停止),最后用每个元素乘以每个元素对应的区间...

861
来自专栏无所事事者爱嘲笑

正则表达式零宽断言详解(?=,?<=,?!,?<!)

1575
来自专栏Java技术栈

递归算法介绍及Java应用实战

什么是递归算法 递归算法是把问题转化为规模缩小了的同类问题的子问题,然后递归调用函数(或过程)来表示问题的解。一个过程(或函数)直接或间接调用自己本身,这种过程...

34010
来自专栏李智的专栏

pandas多表操作,groupby,时间操作

使用场景:有两张表left和right,一般要求它们的表格结构一致,数据量也一致,使用right的数据去填补left的数据缺漏 如果在同一位置left与ri...

501
来自专栏PPV课数据科学社区

Pandas速查卡-Python数据科学

Josh Devlin 2017年2月21日 Pandas可以说是数据科学最重要的Python包。 它不仅提供了很多方法和函数,使得处理数据更容易;而且它已经...

3747
来自专栏游戏杂谈

EditPlus中有用的快捷键

点击到该标记(全选或光标落在里面即可)按下ctrl+[就可以找到匹配的标签了。权支持HTML标签的匹配。

252
来自专栏HTML5学堂

游戏开发 - Math对象相关知识讲解

前几期小编给大家总结了JavaScript的基础知识,为我们后期深入学习JS打下了一定的基础。在后面的几期文章当中我们要来进行JS小游戏的开发,但是开发小游戏的...

27710
来自专栏nummy

numpy入门

numpy中最主要的对象是同质数组array,也就是说数组中的元素类型都是一样的。数组的维度也称之为axis,axis的的个数称之为秩rank。

662
来自专栏糊一笑

非比较排序算法总结与实现

之前一篇文章介绍了几种常用的比较排序算法,下面介绍的是几种非比较排序算法。 非比较排序算法内部引用的都是计数排序,当然你也可以将计数排序换为其他的比较排序算法。...

2958

扫码关注云+社区