专栏首页编程直播室读书笔记:《算法图解》第三章 递归

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

定义:

在数学与计算机科学中,是指在函数的定义中使用函数自身的方法。递归一词还较常用于描述以自相似方法重复事物的过程。例如,当两面镜子相互之间近似平行时,镜中嵌套的图像是以无限递归的形式出现的。也可以理解为自我复制的过程。

例子:

  • 从前有座山,山里有座庙,庙里有个老和尚,正在给小和尚讲故事呢!故事是什么呢?“从前有座山,山里有座庙,庙里有个老和尚,正在给小和尚讲故事呢!故事是什么呢?‘从前有座山,山里有座庙,庙里有个老和尚,正在给小和尚讲故事呢!故事是什么呢?……’”
  • 一只狗来到厨房,偷走一小块面包。厨子举起杓子,把那只狗打死了。于是所有的狗都跑来了,给那只狗掘了一个坟墓,还在墓碑上刻了墓志铭,让未来的狗可以看到:“一只狗来到厨房,偷走一小块面包。厨子举起杓子,把那只狗打死了。于是所有的狗都跑来了,给那只狗掘了一个坟墓,还在墓碑上刻了墓志铭,让未来的狗可以看到:‘一只狗来到厨房,偷走一小块面包。厨子举起杓子,把那只狗打死了。于是所有的狗都跑来了,给那只狗掘了一个坟墓,还在墓碑上刻了墓志铭,让未来的狗可以看到……’”

程序语言中的递归:

程序调用自身的编程技巧称为递归( recursion)。递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。

递归的条件:

一般来说,递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时,递归前进;当边界条件满足时,递归返回。

  • 基线条件 base case 函数不再调用自己
  • 递归条件 函数调用自己

构成递归需具备的条件:

  1. 子问题须与原始问题为同样的事,且更为简单;
  2. 不能无限制地调用本身,须有个出口,化简为非递归状况处理。

递归的缺点:

递归算法解题相对常用的算法如普通循环等,运行效率较低。因此,应该尽量避免使用递归,除非没有更好的算法或者某种特定情况,递归更为适合的时候。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。 栈:

实例:求阶乘

def factorial(n):
    if n == 1:
        return n
    else:
        return n*factorial(n-1)

上例中,n==1是基线条件(base case),n $\neq$ 1是递归条件(recursive case)。

栈(stack)又名堆栈,它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。

栈是限定仅在表头进行插入和删除操作的线性表。

堆叠数据结构使用两种基本操作:推入(push)和弹出(pop):

  • 推入:将数据放入堆叠的顶端(阵列形式或串列形式),堆叠顶端top指标加一。
  • 弹出:将顶端数据资料输出(回传),堆叠顶端资料减一。

栈的基本特点:

  • 先入后出,后入先出。
  • 除头尾节点之外,每个元素有一个前驱,一个后继。

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Canvas 显示图片

    孙亖
  • 折腾git pages+hexo+NexT初识hexo开始本地试运行准备服务器准备上传工具先告一段落发表文章主题

    孙亖
  • git page 绑定域名

    孙亖
  • 超全递归技巧整理,这次一起拿下递归

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

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

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

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

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

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

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

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

    袁承兴
  • 什么是递归?

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

    阿珏
  • Python之路_递归

    py3study

扫码关注云+社区

领取腾讯云代金券