程序员经验分享-hwhale

1691_python学习笔记之week3_递归

2023-05-16

全部学习汇总： GreyZhang/python_basic: My learning notes about python. (github.com)

最初接触递归的时候觉得这个有点不好理解，怎么能够有这种思维方式？这完全不同于之前自己所能够了解的那种一加一等于二的方式。相对于能够看得见的那种直观的理论，这些确实是一种逻辑型的、推理式的描述理论。

递推比较适合解决的问题通常有两个特点：第一，需要解决的复杂问题可以分解或者简化为更小或者更简单的小问题；第二，最小或者最简单的问题能够得出确切的答案。

从之前实现的一个问题来入手说明一下，如果想要求解a*b，在之前的循环中采用的解决方式如下：

a * b = a + a +......+a(b个a)。

如果把上面的公式变化一下，改成：

a *b = a + a + …… + a(b-1个a) + a

以上的描述依然成立，但是右边部分可以理解为a * (b - 1) + a

假设有一个函数f(x) = ax来描述上面的表达，那么a *b 可以理解为f(b)的函数值。而第二个表达式则可以理解为f(b-1) + a的值。而对于f(x)来说，f(x) = f(x-1) + a也是成立的。对于这种描述成立的证明，通常可以使用数学归纳法来证明。证明的过程一般是先验证最初的几个比较小的数值，再假设x = k的时候成立，推导出x = k + 1的时候依然成立。

既然有了上面f(x) = f(x-1) + a的推导关系，而x=1的时候结果我们显然知道。那么求解相应计算的函数可以设计如下：

执行结果如下：

>>> ================================ RESTART ================================

>>>

>>> F(3,5)

15

>>> F(123,456)

56088

通过以上的演示可以看出，在一定范围内的问题处理分析使用递归的思想是可以化繁为简、化腐朽为神奇的。

在程序设计上，个人感觉循环和递归之间很多时候都是可以相互转化的。倒不是说这两种方式等同，只是说能够解决同样的问题。但是在编程实践中发现，递归的方式通常会消耗大量的内存。一般的代码中，递归的嵌套层级也是有限制的。当嵌套的数目过多，程序无法执行。单纯的循环这方面的限制则会少很多。不过，很多时候，递归的方式确实是能够写出更加简洁的代码。如果运算的层级不深，倒是一种不错的选择方式。

常见的递归算法示例莫过于那几个，最常见的便是汉诺塔以及斐波那契函数。下面也写几个简单的递归函数，加深一下印象。

示例1：求阶乘

代码设计如下：

执行结果如下：

>>> ================================ RESTART ================================

>>>

>>> Fun(1)

1

>>> Fun(5)

120

>>> Fun(20)

2432902008176640000L

通过测试，执行结果正确。

示例2：汉诺塔

设计代码如下：

运行测试结果如下：

>>> ================================ RESTART ================================

>>>

>>> Towers(1,'A','B','C')

move from A to B

>>> Towers(2,'A','B','C')

move from A to C

move from A to B

move from C to A

>>> Towers(5,'A','B','C')

move from A to B

move from A to C

move from B to A

move from A to B

move from C to B

move from C to A

move from B to C

move from A to C

move from B to A

move from B to C

move from A to B

move from B to A

move from C to A

move from C to B

move from A to C

move from A to B

move from C to B

move from C to A

move from B to C

move from C to B

move from A to B

move from A to C

move from B to A

move from C to A

move from B to C

move from B to A

move from C to B

move from B to C

move from A to C

move from A to B

move from C to A

示例3：斐波那契数列

设计代码如下：

运行结果如下：

>>> ================================ RESTART ================================

>>>

>>> Fibnacci(1)

1

>>> Fibnacci(0)

1

>>> Fibnacci(13)

377

>>> Fibnacci(25)

121393

这里特意尝试试了一个比较多层的运算，运算报错，在一大堆的提示后面有一个错误的描述：

RuntimeError: maximum recursion depth exceeded

递归或者迭代的层级超限。这就是前面说到的缺点了。其实，除了这个缺点以外，还有一个比较大的缺点便是执行速度。通常递归的运算在层级比较深的时候慢到足以用需要人来久久等待，通过一个简单的循环计算阶乘的算法比较一下就能够很明显感觉出这种差异。不过，递归确实是一种很好的计算机思维，就像前面所说，很多时候它能够化繁为简。用到合适的地方，这确实是一个简单而有效的方式。

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

1691_python学习笔记之week3_递归 的相关文章

  • 分析各家2440开发板的性价比（初学者如何选择开发板）

    分析各家2440开发板的性价比 xff08 初学者如何选择开发板 xff09 作者 xff1a gooogleman 邮箱 xff1a gooogleman 64 foxmail com 地址 xff1a http blog csdn ne

  • 一个机械专业小混混（gooogleman）学习嵌入式ARM的真实经历

    我记得在我毕业一周年的时候 xff0c 写过一篇文章 xff0c 大概是讲我学习嵌入式wince驱动的经历 xff08 http topic csdn net u 20090704 01 43492b64 f7bf 4953 a31f db

  • 是时候想想再上一个台阶的时候了

    刚才 xff0c 被一个蚊子吵醒 xff0c 脑子里就想着一件事 xff1a 我这些年也是过的够淡定的了 xff0c 不管旁边发生任何事情 xff0c 我也不去做什么得失比较 xff0c 我乐于享受目前的现状 xff0c 一台还算稳定的国产

  • 关于wince6.0 升级全年包的注意事项（作者：gooogleman）

    作者 xff1a gooogleman Email xff1a gooogleman 64 foxmail com 最近在S5pv210 wince6 0 系统定制上更新了几个包 xff0c 发现了一些微软更新补丁包的问题 xff0c 现在

  • 二级域名绑定二级目录的两种方法

    当用WordPress建站后 xff0c WordPress位于二级目录 xff08 v ar www html xff09 下 xff0c 进行域名解析时如何把域名解析到二级目录下 xff0c 网络上一般有两种方法 xff0c 一是利用接

  • PMP 真的没用吗？

    最近在备考2018 3 24 的pmp 认证考试 xff0c 有不少收获 xff0c 此前我曾在群里邀请大家一起备考 xff0c 一些人跳出来就说考这些有啥用 xff1f 干技术的把技术干好就行了 xff0c 技术人员最烦这些没点技术的项目

  • 一个嵌入式产品的从研发到量产的流程（作者：gooogleman@foxmail.com）

    作者 xff1a gooogleman 64 foxmail com 一个嵌入式产品的开发流程是 1 了解清楚客户需求 2 模具开发 3 硬件工程师准备硬件 xff0c 物料选型 xff0c 原理图 xff0c PCB和模具工程师商议PCB

  • 【电赛国赛备赛笔记】【赛题经验分享会】

    存在的问题 光流问题 起飞后定不住飞行过程中方向太偏光照度对飞行稳定性的影响纹理变化对飞行稳定性的影响 目前还没有很好的解决办法 xff0c 但如果不限制使用器材的话 xff0c 用双目摄像头可能可以解决问题 赛题准备 视觉方面的算法和代码

  • APM32f003替换STM32进行低成本系统开发

    STM32F003是基于Arm Cortex M0内核的32位MCU xff0c 工作电压为2 4 3 6V xff0c 主频48MHz xff0c 内置16KB Flash 定时器 ADC 通信接口 APM32F003系列主频与STM32

  • 【VSCode】Windows 下搭建 C++ 环境

    文章目录 Part I 预备知识Part II 搭建过程Part III 安装较高版本的MinGW Part I 预备知识 MinGW 提供了一套简单方便的Windows下的基于GCC 程序开发环境 MinGW 收集了一系列免费的Windo

  • 路由器开发————概念理解

    区别 xff1a 静态ip 可以直接使用Internet上网的IP xff08 相当于公网IP xff09 pppoe 从运营商那里动态获取的静态IP的过程就是PPPOE 运营商为了提高他手上拥有的静态IP的利用率 xff0c 而做出的动态

  • 干了三年java外包，我转AI了....

    谈及到程序员外包这件事 xff0c 我想我是比较有发言权的一个 xff0c 即使我现在已经从一个外包公司的JAVA开发转行做人工智能算法 我是2018年毕业的 xff0c 一毕业找的第一份工作就是一家外包公司 xff0c 主要做的是承接甲方

  • 人工智能的算法有哪些？AI常用算法

    人工智能 xff08 AI xff09 是一个非常广泛的领域 xff0c 其中包含许多不同的算法和技术 以下是一些常见的人工智能算法 xff1a 人工智能的算法有哪些 xff1f 机器学习 xff08 Machine Learning xf

  • 卡尔曼滤波五个公式各个参数的意义

    卡尔曼滤波五个公式各个参数的意义 wccsu1994 2018 11 30 10 49 33 45928 收藏 218 分类专栏 xff1a 卡尔曼滤波 版权 系统的状态方程为 xff1a 这个状态方程是根据上一时刻的状态和控制变量来推测此

  • FutureTask 示例

    1 简单示例 2 泡茶 1 简单示例 创建 FutureTask FutureTask lt Integer gt futureTask 61 new FutureTask lt gt gt 1 43 2 创建并启动线程 Thread t1

  • Centos6.5下进行PHP版本升级

    统计插件 WP Statistics 要求PHP5 4以上 xff0c 可本机PHP为5 3 3 xff0c 无奈只有对服务器PHP进行升级 xff0c 遂写下本文 Step1 xff1a 查看安装服务器当前安装版本 php V Step2

  • 一段日子的结束， 也是一段日子的开始

    一个朋友说的 xff0c 一段日子的结束 xff0c 也是另一段日子的开始 也正是我现在的状态 xff0c 我结束了一段往事 xff0c 也因此开始了一段日子 xff0c 曾经的曾经已离我远去 昨天和好朋友聊天到很晚 xff0c 谈了很多

  • 岁月静好

    不是说马年会马上转运的 xff0c 是不是蛇年的时候前半年太幸福了 xff0c 用了太多的好人品 xff0c 各种奖学金 xff0c 各种申请中标 xff0c 各种荣誉 xff0c 然后我要还了 小猴子说我开始会依赖人了 xff0c 哈哈

  • STM32 中重定向printf 和 scanf

    uart c 如果使用 pragma import use no semihosting 则在MDK中不勾选use Microlib 当前代码直接重定向没使用 pragma import use no semihosting 故需要选择us

  • Ubuntu环境下Pixhawk原生固件PX4的编译

    Ubuntu下Pixhawk原生固件PX4的编译这个问题困扰了两天时间 xff0c 可能是博主脑力不够 xff0c 主要是环境搭建不起来 xff0c 主要原因应该是路径的原因 xff0c 最后在大师傅的帮助下还好成功将路径搭建好 xff0c

随机推荐

  • 远程连接虚拟机的Network error: Connection timed out问题

    MobaXterm远程连接虚拟机的Network error Connection timed out问题 我使用的是MobaXterm远程连接我使用VMware创建的虚拟机 更新一下 xff1a 如果出现这种问题 xff0c 极大可能是服

  • springboot项目接入天猫精灵

    springboot项目接入天猫精灵 最近工作需要使用到天猫精灵的语音功能 xff0c 大体是通过呼叫对应的 调用词 实现携带参数 xff0c 然后调用我项目中的接口 xff0c 以实现对应的业务 所以在此简单的记录下使用过程 实际上 xf

  • Lesson 9.2&9.3&9.4 黑箱：不可解释的深层神经网络&探索多层神经网络：层vsh（z）

    二 黑箱 xff1a 深层神经网络的不可解释性 首先从结构上来看 xff0c 多层神经网络比单层神经网络多出了 中间层 中间层常常被称为隐藏层 xff08 hidden layer xff09 xff0c 理论上来说可以有无限层 xff0c

  • UnicodeEncodeError: 'gbk' codec can't encode character ...

    使用Python写文件的时候 xff0c 或者将网络数据流写入到本地文件的时候 xff0c 大部分情况下会遇到 xff1a UnicodeEncodeError 39 gbk 39 codec can 39 t encode charact

  • 一文简单了解并构建DockerFile

    GreatSQL社区原创内容未经授权不得随意使用 xff0c 转载请联系小编并注明来源 GreatSQL是MySQL的国产分支版本 xff0c 使用上与MySQL一致 作者 xff1a 蟹黄瓜子文章来源 xff1a GreatSQL社区投稿

  • 头文件中定义和声明的问题

    头文件中定义和声明的问题 1 头文件中不可以放变量的定义 xff01 一般头文件中只是放变量的声明 xff0c 因为头文件要被其他文件包含 include xff0c 如果把定义放在头文件的话 xff0c 就不能避免多次定义变量 C 43

  • Apache中更改PHP版本型号

    如何对服务器PHP版本进行升级 xff0c 详看我另外一篇博文 xff0c 这篇文章我们将讲述如何在Apache中更改PHP版本型号 Step1 xff1a 查看Apache用的PHP什么版本 新建一个文档 xff0c 命名为info ph

  • 简述AGV通信接口标准-VDA5050

    引言 德国汽车工业协会 德语 xff1a Verband der Automobilindustrie e V 简称VDA xff0c 通过 其 34 VDA 5050 34 接口 xff0c 早在2019年起 xff0c 不同制造商的车辆

  • C语言结束输入（两种方法）

    方法1 xff1a 输入数据 while getchar 61 39 n 39 scanf 34 d 34 amp Data data i 43 43 61 Data 方法2 xff1a for i 61 0 i lt 100 amp am

  • OpenCV（项目）车牌识别3 -- 模板匹配

    目录 一 基础理论 1 思想 2 大致过程 二 详细过程 1 首先需要模板库 2 得到模板 3 原图限定大小 4 模板匹配 5 匹配所有子文件夹 xff0c 保存最佳得分 xff08 最匹配项 xff09 三 大致过程 xff08 细分类

  • PMP项目管理中的重要角色

    PMP及PMBOK有个大问题 xff0c 就是没有统一的角色职责及流程 xff0c 考试也是随意性很强 xff0c 这给考生带来很多困扰 一个管理体系 xff0c 首先是人员分工安排 比如 xff1a PRINCE2 xff0c 明确的组织

  • 书房再次升级啦～～

    国庆长假 xff0c 在家里面一顿折腾 xff0c 墙全部重新粉刷 xff0c 书房 卧室 客厅三种不同颜色 书房的颜色是当时在装饰城的展厅里面偷偷扣的墙皮 xff0c 在多乐士店色卡里面对出来的 xff0c 哈哈 ps 这篇日志的照片是用

  • 基于K近邻法的手写数字图像识别

    数字图像处理课程论文 题目 xff1a 数字图像识别 摘要 模式识别 PatternRecognition 是一项借助计算机 xff0c 就人类对外部世界某一特定环境中的客体 过程和现象的识别功能 xff08 包括视觉 听觉 触觉 判断等

  • Ubuntu 16.04升级内核到20.04

    一 首先需要从16 04 18 04 sudo mv etc apt sources list sudo mv etc apt sources list d list 1 改变源 xff08 粘贴下面这一段到终端并运行 xff09 cat

  • 互斥和二进制信号量的使用

    1 二进制信号量 semBCreate SEM Q FIFO SEM Q PRIORITY SEM EMPTY SEM FULL 有两个作用 xff1a xff08 1 xff09 任务间的互斥 xff0d xff0d 同一个任务获取和释放

  • 【C++】关于以下划线开头的变量名

    系 统头文件里将宏名 变量名 内部函数名用 34 34 开 头就是为了避免与用户用的名字冲突 因为当你 xff03 include 系 统头文件时 xff0c 这些文件里的名字都有了定义 xff0c 如果与你用的名字冲突 xff0c 就可能

  • 1689_MATLAB处理Excel文件提升篇

    全部学习汇总 xff1a GreyZhang g matlab MATLAB once used to be my daily tool After many years when I go back and read my old lea

  • 1690_Python中的复数数据类型

    全部学习汇总 xff1a GreyZhang python basic My learning notes about python github com 之前总结的知识中设计的数据类型有整形 浮点 字符串等 xff0c 这些类型表示的都是

  • linux 命令终端提示符显示-bash-4.1#

    昨晚对服务器自带Python升级后 xff0c 终端就不是以前root 64 主机 43 路径的显示方式了 查了很多资料 xff0c 有人说是root目录下 bash profile和 bash两个文件缺失 xff0c 但我的这两个文件是存

  • 1691_python学习笔记之week3_递归

    全部学习汇总 xff1a GreyZhang python basic My learning notes about python github com 最初接触递归的时候觉得这个有点不好理解 xff0c 怎么能够有这种思维方式 xff1

热门标签