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

定义:

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

例子:

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

程序语言中的递归:

程序调用自身的编程技巧称为递归( 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 条评论
登录 后参与评论

相关文章

来自专栏追不上乌龟的兔子

[多少懂点位运算]找出唯一的数字

大家都知道现代计算机的底层是以二进制为基础的,计算机所有的操作最后都归结到了简单的二进制位运算上:与,或,非和异或。

2465
来自专栏Danny的专栏

面向对象三大特征

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/huyuyang6688/article/...

1712
来自专栏Vamei实验室

纸上谈兵: 排序算法简介及其C实现

排序的目标是将一组数据 (即一个序列) 重新排列,排列后的数据符合从大到小 (或者从小到大) 的次序。这是古老但依然富有挑战的问题。Donald Knuth的经...

2479
来自专栏专注数据中心高性能网络技术研发

[LeetCode]HashTable主题系列{第3题}

1. 内容介绍 开一篇文章记录在leetcode中HashTable主题下面的题目和自己的思考以及优化过程,具体内容层次按照{题目,分析,初解,初解结果,优化解...

3329
来自专栏码云1024

c++ 虚继承

3317
来自专栏移动端开发

快速排序OC、Swift版源码

前言: 你要问我学学算法在工作当中有什么用,说实话,当达不到那个地步的时候,可能我们不能直接的感觉到它的用处!你就抱着这样一个心态,当一些APP中涉及到算法...

2198
来自专栏海天一树

Codeforces 976E 题解报告

http://codeforces.com/contest/976/problem/E

1263
来自专栏章鱼的慢慢技术路

C语言简明数据类型指南

1907
来自专栏编舟记

函数式编程简介

1900年,Hilbert 提出了数学界悬而未决的10大问题,后续陆续添加成了23个问题,被称为著名的 Hilbert 23 Problem。针对其中第2个决定...

1834
来自专栏小红豆的数据分析

小蛇学python(6)python实现经典排序算法并可视化分析复杂度

排序算法在算法界是一个怎么样的存在?就好像在学术界中数学的地位,说直接用好像用不上,可是不会做起事情来总会捉襟见肘,左支右绌。找工作的时候,有的面试官甚至会让我...

2032

扫码关注云+社区

领取腾讯云代金券