提升Python效率之使用循环机制代替递归函数
斐波那契数列
当年,典型的递归题目,斐波那契数列还记得吗?
def fib(n): if n==1 or n==2: return 1 else: return fib(n-1)+fib(n-2)
当然, 为了程序健壮性,加上 try...except...
def fib(n): if isinstance(n, int): print('兄弟,输入正整数哈') return try: if n==1 or n==2: return 1 elif n <= 0: print('兄弟别输入0或负数呀') else: return fib(n-1)+fib(n-2) except RecursionError: print('兄弟,超过了最大递归深度'
是的,无论时间还是空间复杂度,递归真的是不太好使哈!这是递归的写法:
def fib(n): if n==1 or n == 2: return 1 a, b = 1, 1 for i in range(2, n): a, b = b, a+b return b
我稍微解释三点:
- 为啥是
range(2, n)
,因为,斐波那契数列从 1 开始,所以 fib(n) 就是数列的第 n 项 - 由于前两项都为 1 ,所以要少两项,为
range(2, n)
(要循环 n-2 次) - a, b = b, a+b 这里你也许也有困惑,我简单说说,一般Python解释器会将逗号分隔的变量直接看做一个元组,
- 又因为,解释器先执行等式右边的,所以,这样相当于 元组拆包
- a, b = b, a+b 这句话的精髓在于,在等式右边将 b 视为
fib(n-2)
,将 a+b 视为 fib(n-1)
杨辉三角
同样,先写递归写法(我这里不考虑特殊情况了,时间有限):
def YH_tri(a, b): if a == b or b == 0: return 1 else: return YH_tri(a-1, b)+YH_tri(a-1, b-1)
老铁们自己先想想该怎么写??
总结
以上所述是小编给大家介绍的提升Python效率之使用循环机制代替递归函数,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对我们网站的支持!
如果你觉得本文对你有帮助,欢迎转载,烦请注明出处,谢谢!
相关推荐
-
Python进阶之递归函数的用法及其示例
作者是一名沉迷于Python无法自拔的蛇友,为提高水平,把Python的重点和有趣的实例发在简书上. 一.递归 是指函数/过程/子程序在运行过程序中直接或间接调用自身而产生的重入现象.在计算机编程里,递归指的是一个过程:函数不断引用自身,直到引用的对象已知.使用递归解决问题,思路清晰,代码少.但是在主流高级语言中(如C语言.Pascal语言等)使用递归算法要耗用更多的栈空间,所以在堆栈尺寸受限制时(如嵌入式系统或者内核态编程),应避免采用.所有的递归算法都可以改写成与之等价的非递归算法. (来源
-
讲解Python中的递归函数
在函数内部,可以调用其他函数.如果一个函数在内部调用自身本身,这个函数就是递归函数. 举个例子,我们来计算阶乘n! = 1 x 2 x 3 x ... x n,用函数fact(n)表示,可以看出: fact(n) = n! = 1 x 2 x 3 x ... x (n-1) x n = (n-1)! x n = fact(n-1) x n 所以,fact(n)可以表示为n x fact(n-1),只有n=1时需要特殊处理. 于是,fact(n)用递归的方式写出来就是: def fact(n):
-
浅析python递归函数和河内塔问题
关于递归函数: 函数内部调用自身的函数. 以n阶乘为例: f(n) = n ! = 1 x 2 x 3 x 4 x...x(n-1)x(n) = n x (n-1) ! def factorial(n): if n==1: return 1 return n * f(n-1) //调用过程如下: >>f(5) >>5 * f(4) >>5 * 4 * f(3) >>5 * 4 * 3 * f(2) >>5 * 4 * 3 * 2 * f(1) &
-
浅谈Python中的可迭代对象、迭代器、For循环工作机制、生成器
1.iterable iterator区别 要了解两者区别,先要了解一下迭代器协议: 迭代器协议是指:对象需要提供__next__()方法,它返回迭代中的元素,在没有更多元素后,抛出StopIteration异常,终止迭代. 可迭代对象就是:实现了迭代器协议的对象. 协议是一种约定,可迭代对象实现迭代器协议,Python的内置工具(如for循环,sum,min,max函数等)通过迭代器协议访问对象,因此,for循环并不需要知道对象具体是什么,只需要知道对象能够实现迭代器协议即可. 迭代器(ite
-
Python 递归函数详解及实例
Python 递归函数 如果一个函数体直接或者间接调用自己,那么这个函数就称为递归函数.也就是说,递归函数体的执行过程中可能会返回去再次调用该函数.在python里,递归函数不需要任何特殊的语法,但是它需要付出一定的努力去理解和创建. 我们会以一个简单的例子开始:写一个函数求一个自然数中所有数字的和.在设计递归函数的时候,我们会寻找能把问题分解成简单的问题的方法.在这道题中,运算符%和//可以用来把一个数分成两部分:最低位和不包含最低位数字两部分. 18117的数字和为:1+8+1+1+7=18
-
Python递归函数定义与用法示例
本文实例讲述了Python递归函数定义与用法.分享给大家供大家参考,具体如下: 递归函数 在函数内部,可以调用其他函数.如果一个函数在内部调用自身本身,这个函数就是递归函数. 举个例子,我们来计算阶乘 n! = 1 * 2 * 3 * ... * n,用函数 fact(n)表示,可以看出: fact(n) = n! = 1 * 2 * 3 * ... * (n-1) * n = (n-1)! * n = fact(n-1) * n 所以,fact(n)可以表示为 n * fact(n-1),只有
-
python实现斐波那契递归函数的方法
本文以一个简单的实例讲述了python实现斐波那契数列数列递归函数的方法,代码精简易懂.分享给大家供大家参考之用. 主要函数代码如下: def fab(n): if n==1: return 1 if n==0: return 0 else: result=int(fab(n-1))+int(fab(n-2)) return result 测试代码如下: for i in range(10): print fab(i) 希望本文所述对大家Python程序设计的学习有所帮助.
-
提升Python效率之使用循环机制代替递归函数
斐波那契数列 当年,典型的递归题目,斐波那契数列还记得吗? def fib(n): if n==1 or n==2: return 1 else: return fib(n-1)+fib(n-2) 当然, 为了程序健壮性,加上 try...except... def fib(n): if isinstance(n, int): print('兄弟,输入正整数哈') return try: if n==1 or n==2: return 1 elif n <= 0: print('兄弟别输入0或负
-
python如何提升爬虫效率
单线程+多任务异步协程 协程 在函数(特殊函数)定义的时候,使用async修饰,函数调用后,内部语句不会立即执行,而是会返回一个协程对象 任务对象 任务对象=高级的协程对象(进一步封装)=特殊的函数 任务对象必须要注册到时间循环对象中 给任务对象绑定回调:爬虫的数据解析中 事件循环 当做是一个装载任务对象的容器 当启动事件循环对象的时候,存储在内的任务对象会异步执行 特殊函数内部不能写不支持异步请求的模块,如time,requests...否则虽然不报错但实现不了异步 time.sleep --
-
提升python处理速度原理及方法实例
这篇文章主要介绍了提升python处理速度原理及方法实例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 导读:作为日常生产开发中非常实用的一门语言,python广泛应用于网络爬虫.web开发.自动化测试.数据分析和人工智能等领域.但python是单线程的,想要提升python的处理速度,涉及到一个很关键的技术--协程.本篇文章,将讲述python协程的理解与使用. 1.操作系统相关概念 在理解与使用协程之前,先简单的了解几个与操作系统相关的概念
-
python语言开发垃圾回收机制原理教程
目录 一.什么是垃圾回收机制 二.为什么要有垃圾回收机制 三.垃圾回收机制的原理 1.引用计数 直接引用 间接引用 2.栈区 / 堆区 3.总结 四.标记清除 1.循环引用问题(也叫交叉引用) 2.循环引用导致的结果 3.解决方法 : 清除-标记 五.分代回收 1.效率问题 2.解决方法 : 分代回收 分代 回收 总结 一.什么是垃圾回收机制 垃圾回收机制(简称GC), 解释器自带的一种机制 它是一种动态存储管理技术,自动释放不再被程序引用的对象所占用的内存空间 二.为什么要有垃圾回收机制 程序
-
python语法 之垃圾回收机制
目录 一 引入 二.什么是垃圾回收机制? 三.为什么要用垃圾回收机制? 四.垃圾回收机制原理分析 4.1.什么是引用计数? 4.2.引用计数扩展阅读 4.2.1 标记-清除 4.2.2 分代回收 一 引入 解释器在执行到定义变量的语法时,会申请内存空间来存放变量的值,而内存的容量是有限的,这就涉及到变量值所占用内存空间的回收问题,当一个变量值没有用了(简称垃圾)就应该将其占用的内存给回收掉,那什么样的变量值是没有用的呢? 由于变量名是访问到变量值的唯一方式,所以当一个变量值不再关联任何变
-
JavaScript 关于事件循环机制的刨析
目录 前言: 一.事件循环和任务队列产生的原因: 二.事件循环机制: 三.任务队列: 3.1 任务队列的类型: 3.2 两者区别: 3.3 更细致的事件循环过程 四.强大的异步专家 process.nextTick() 4.1 process.nextTick()在何时调用? 前言: 这次主要整理一下自己对 Js事件循环机制,同步,异步任务,宏任务,微任务的理解,大概率暂时还有些偏差或者错误.如果有,十分欢迎各位纠正我的错误! 一.事件循环和任务队列产生的原因: 首先,JS是单线程,这样设计也是
-
Go语言提升开发效率的语法糖技巧分享
目录 前言 可变长参数 声明不定长数组 init函数 忽略导包 忽略字段 json序列化忽略某个字段 json序列化忽略空值字段 短变量声明 类型断言 切片循环 判断map的key是否存在 select控制结构 前言 哈喽,大家好,我是asong. 每门语言都有自己的语法糖,像java的语法糖就有方法变长参数.拆箱与装箱.枚举.for-each等等,Go语言也不例外,其也有自己的语法糖,掌握这些语法糖可以助我们提高开发的效率,所以本文就来介绍一些Go语言的语法糖,总结的可能不能全,欢迎评论
-
深入了解Javascript的事件循环机制
目录 单线程的Javascript 同步 vs 异步 宏任务 vs 微任务 定时器 To Be Continued 单线程的Javascript JavaScript是一种单线程语言,它主要用来与用户互动,以及操作DOM.多线程需要共享资源.且有可能修改彼此的运行结果,且存在上下文切换. 在 JS 运行的时候可能会阻止 UI 渲染,这说明两个线程是互斥的.这是因为 JS 可以修改 DOM,如果在 JS 执行的时候 UI 线程还在工作,就可能导致不能安全的渲染 UI. JS 是单线程运行的,可以达
-
pypy提升python项目性能使用详解
目录 一.PyPy介绍 二.PyPy安装 三.PyPy和Python测试对比 四.PyPy注意事项 一.PyPy介绍 PyPy是用Python实现的Python解释器的动态编译器,是Armin Rigo开发的产品,能够提升我们python项目的运行速度.PyPy 是利用即时编译的 Python 的替代实现. 背后的原理是 PyPy 开始时就像一个解释器,直接从源文件运行我们的 Python 代码.但是,PyPy 不是逐行运行代码,而是在执行它们之前将部分代码编译为机器代码. 根据官方文档的介绍可
-
python异常和文件处理机制详解
本文实例讲述了python异常和文件处理机制.分享给大家供大家参考,具体如下: 1 异常处理 Python的异常用 try except finally 来处理. 并且except后还可以跟 else . 引发异常用 raise 如果抛出的异常没有被处理. 在Python IDE中是显示一些红色的信息. 在真正的Python程序运行时. 会导致程序终止. 在以前我们已经见到过一下几种异常: 在 Dictionary 中如果使用的 key 不存在. 会引发 KeyError 异常. 如: >>&
随机推荐
- 实现React单页应用的方法详解
- vbs实现的eMule电驴自动关机脚本代码
- Python文件操作之合并文本文件内容示例代码
- python实现的希尔排序算法实例
- 使用C++中string实现任意长度的正小数、整数之间加减法方法实例
- Docker volume使用详解及实例
- Android RecyclerView基本使用详解
- php自定义的格式化时间示例代码
- java实现仿windows 字体设置选项卡实例
- 深入浅析NodeJs并发异步的回调处理
- rman恢复方案和oracle异机恢复
- Flask框架学习笔记(一)安装篇(windows安装与centos安装)
- js focus不起作用的解决方法(主要是因为dom元素是否加载完成)
- 非常实用的小功能 Android应用版本的更新实例
- vue cli使用绝对路径引用图片问题的解决
- babel的使用及安装配置教程
- Opencv实现轮廓提取功能
- python统计指定目录内文件的代码行数
- SpringCloud客户端的负载均衡Ribbon的实现
- JS中判断字符串存在和非空的方法