Python递归及尾递归优化操作实例分析
作者:dayL_W 发布时间:2022-06-17 16:09:10
本文实例讲述了Python递归及尾递归优化操作。分享给大家供大家参考,具体如下:
1、递归介绍
递归简而言之就是自己调用自己。使用递归解决问题的核心就是分析出递归的模型,看这个问题能拆分出和自己类似的问题并且有一个递归出口。比如最简单的就5的阶乘,可以把它拆分成5*4!,然后求4!又可以调用自己,这种问题显然可以用递归解决,递归的出口就是求1!,可以直接返回1。用Python实现如下:
def fact(n):
if n==1:
return n
return n*fact(n - 1);
print(fact(5))
运行结果:
120
2、尾递归优化
在上面的求递归中,也有一定的缺点,假如说求1000!的阶乘,会出现栈溢出的问题,因为在函数执行中,没调用一个函数都会把当前函数的调用位置和内部变量保存在栈里面,由于栈的空间不是无限大(具体栈的最大空间还没有查找到),假如说调用层数过多,就是出现栈溢出的情况。
这个时候就可以用尾递归优化来解决,尾调用的概念非常简单,一句话就能说清楚,就是指某个函数的最后一步是调用另一个函数。
function f(x){
return g(x);
}
尾递归优化后的阶乘函数如下:
def fact(n):
return fact_iter(n,1);
def fact_iter(num, product):
if num == 1:
return product
return fact_iter(num - 1, num * product)
print(fact(5))
print(fact(1000))
尾调用由于是函数的最后一步操作,所以不需要保留外层函数的调用记录,因为调用位置、内部变量等信息都不会再用到了。所以尾递归优化可以有效的防止栈溢出,但是尾递归优化需要编译器或者解释器的支持,遗憾的是,大多数编程语言没有针对尾递归做优化,Python解释器也没有做优化,所以,即使把上面的fact(n)函数改成尾递归方式,也会导致栈溢出。
3、汉诺塔问题
汉诺塔问题也是一个经典的递归问题,具体题目就不说了,这里分析思路。假设hanoi(n, a, b, c)实现把a上的n个盘子移到c上。
当只有一个盘子时,直接从A移动到C即可
如果有3个盘子,可以这样:
# A --> C
# A --> B
# C --> B
# A --> C
# B --> A
# B --> C
# A --> C
如果有很多盘子,我们分析一下该怎么移动,首先,我们需要把n-1个盘子移动到b中,才可以实现最简单的一步,把a中最大的盘子移动到c中,具体怎么转移到b中后面再讨论。移动最大的盘子后,a和c都可以看成是空的,接下来,把b看成是a,把a看成是b,把a中的n-1个盘子(这里的n是已经减1的n)移动到b后,又可以移动第二大的盘子。这显然是一个递归问题。
递归的出口就是n等于1,直接从a移动到c即可。
那么怎么接下来讨论,怎么把n-1个盘子移动到b,这不又是一个递归问题嘛!可以调用它自己呀,只不过需要把b看成是c,把c看成是b。所以代码如下:
def hanoi(n,a,b,c):
#只有一个盘子,直接移动
if n==1:
print(a,'->',c)
else:
#通过c把n-1个盘子移动到b
hanoi(n-1, a,c,b)
#移动最大的盘子
print(a,'->',c)
#通过a把n-1个盘子移动到c
hanoi(n-1, b,a,c)
hanoi(3,'A','B','C')
运行结果:
A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C
转自https://www.liaoxuefeng.com/wiki/0014316089557264a6b348958f449949df42a6d3a2e542c000/001431756044276a15558a759ec43de8e30eb0ed169fb11000
希望本文所述对大家Python程序设计有所帮助。
来源:https://blog.csdn.net/u013181595/article/details/76336181
猜你喜欢
- 如下所示:import serialimport sysimport osimport timeimport redef wait_for_
- 从字节码角度看描述器在前面的内容当中我们已经详细分析了描述器的使用和其相关的应用,我们通常使用描述器都是将其作为类的一个类属性使用,而使用的
- 前言在Django的模型字段参数中,有一个参数叫做validators,这个参数是用来指定当前字段需要使用的验证器,也就是对字段数据的合法性
- 1.建立Recordset对象 代码如下:Dim objMyRst Set objMyRst=Server.C
- python socket多线程实现客户端与服务器连接,供大家参考,具体内容如下之前因为一些作业需要完成一个服务器监听多个客户端的程序,于是
- append() 方法向列表的尾部添加一个新的元素。只接受一个参数。>>> num = [1,2]>>>
- global语句的作用在编写程序的时候,如果想为一个在函数外的变量重新赋值,并且这个变量会作用于许多函数中时,就需要告诉python这个变量
- 最近发现一常见的加载进度条(loadding)的问题,所以试试,觉得还不错,大家可以看下.当然这个只是一个效果而已!呵呵,用的着的时候,你就
- 粒子群算法粒子群算法源于复杂适应系统(Complex Adaptive System,CAS)。CAS理论于1994年正式提出,CAS中的成
- 写完调用天气接口的demo之后,小程序调用天气接口并且渲染在页面,顺便再调用了一下美图的接口API:美图APIurlwxml:<vie
- 在IE 浏览器中使用 jquery的fadeIn() 效果 英文字符字体加粗的解决方法分享。<div id='tes
- python代码运行助手是能在网页上运行python语言的工具。因为python的运行环境在很多教程里都是用dos的,黑乎乎的界面看的有点简
- SMTP协议首先了解SMTP(简单邮件传输协议),邮件传送代理程序使用SMTP协议来发送电邮到接收者的邮件服务器。SMTP协议只能用来发送邮
- 前言本来打算写的标题是XPath语法,但是想了一下Python中的解析库lxml,使用的是Xpath语法,同样也是效率比较高的解析方法,所以
- 一、原型模式原型是相对于复制、克隆而言的,但是不同于模板,模板创造出的东西是一模一样,而原型创造出的东西是允许存在差异化和个性化的。原型模式
- 函数javascript函数相信大家都写过不少了,所以我们这里只是简单介绍一下.创建函数:function f(x) {........}v
- 脚本架构:domain_test.py:批量解析运行主程序DomainResult.txt:域名解析结果文件domains.txt:解析的域
- 上文:成为一个顶级设计师的第二准则英文原文成为一个顶级设计师的第三准则:对比,对比,对比在设计里面,好的对比和你对颜色选择是密切相关的。对比
- 1、psutil是一个跨平台库(https://github.com/giampaolo/psutil)能够实现获取系统运行的进程和系统利用
- 从百度百科中扣去的这个图片轮播代码,图片向左不间断滚动,有停顿:<!DOCTYPE html PUBLIC "-//W3C/