专栏首页python读书笔记《算法图解》NOTE 3 递归1.定义2递归结构2.适用场合3.应用案例

《算法图解》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 条评论
登录 后参与评论

相关文章

  • 《python算法教程》Day3 - 递归递归简介代码示例

    这是《python算法教程》的第3篇读书笔记。由于之前看书的效率太低了,所以拖了一个多星期才写第三篇读书笔记。这次主要简单总结一下递归(recursion)。 ...

    billyang916
  • python 数据分析基础 day6-xlrd,xlwt读写单个excel

    今天的内容为使用xlrd和xlwt这两个模块来读取单个excel文件, 思路和读取csv文件大致相同,分别设置输入和输出的excel文件对象,然后遍历输入对象...

    billyang916
  • python 数据分析基础 day11-mysql安装

    今天是读《python数据分析基础》的第10天,今天的笔记内容是安装mysql数据库。 mysql数据库是一个关系型数据库,分为社区版(免费)以及专业版(收费...

    billyang916
  • 读书笔记:《算法图解》第三章 递归

    孙亖
  • 讨厌算法的程序员 | 第七章 归并排序的时间复杂度分析

    上一篇归并排序基于分治思想通过递归的调用自身完成了排序,本篇是关于归并排序的最后一部分——分析其时间复杂度。 这个过程中会解释清楚在各种时间复杂度中经常看到的一...

    用户1332428
  • 超全递归技巧整理,这次一起拿下递归

    大家好,我是多选参数的程序锅,一个正在 neng 操作系统、学数据结构和算法以及 Java 的硬核菜鸡。本篇将主要介绍递归相关的内容,下面是本篇的内容提纲。

    syy
  • 算法导论第四章分治策略剖根问底(二)

       在上一篇中,通过一个求连续子数组的最大和的例子讲解,想必我们已经大概了然了分治策略和递归式的含义,可能会比较模糊,知道但不能用语言清晰地描述出来。但没关系...

    CloudDeveloper
  • Python之路_递归

    py3study
  • 讨厌算法的程序员 7 - 归并排序的时间复杂度分析

    ? 递归树 上一篇归并排序基于分治思想通过递归的调用自身完成了排序,本篇是关于归并排序的最后一部分——分析其时间复杂度。 这个过程中会解释清楚在各种时间复杂度...

    袁承兴
  • 什么是递归?

    一上来你肯定觉得读这句话好绕,好吃力。 其实你用递归来读就很简单了: 递归要有一个终点(小鲤鱼) 当递归尚未达到终点的时候,函数会反复调用自己。 ...

    阿珏

扫码关注云+社区

领取腾讯云代金券