提升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效率之使用循环机制代替递归函数,希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对我们网站的支持！
如果你觉得本文对你有帮助，欢迎转载，烦请注明出处，谢谢！

赞 (0)

相关推荐

  • 浅谈Python中的可迭代对象、迭代器、For循环工作机制、生成器

    浅谈Python中的可迭代对象、迭代器、For循环工作机制、生成器

    1.iterable iterator区别 要了解两者区别,先要了解一下迭代器协议: 迭代器协议是指:对象需要提供__next__()方法,它返回迭代中的元素,在没有更多元素后,抛出StopIteration异常,终止迭代. 可迭代对象就是:实现了迭代器协议的对象. 协议是一种约定,可迭代对象实现迭代器协议,Python的内置工具(如for循环,sum,min,max函数等)通过迭代器协议访问对象,因此,for循环并不需要知道对象具体是什么,只需要知道对象能够实现迭代器协议即可. 迭代器(ite

  • Python进阶之递归函数的用法及其示例

    作者是一名沉迷于Python无法自拔的蛇友,为提高水平,把Python的重点和有趣的实例发在简书上. 一.递归 是指函数/过程/子程序在运行过程序中直接或间接调用自身而产生的重入现象.在计算机编程里,递归指的是一个过程:函数不断引用自身,直到引用的对象已知.使用递归解决问题,思路清晰,代码少.但是在主流高级语言中(如C语言.Pascal语言等)使用递归算法要耗用更多的栈空间,所以在堆栈尺寸受限制时(如嵌入式系统或者内核态编程),应避免采用.所有的递归算法都可以改写成与之等价的非递归算法. (来源

  • 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中的递归函数

    在函数内部,可以调用其他函数.如果一个函数在内部调用自身本身,这个函数就是递归函数. 举个例子,我们来计算阶乘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递归函数定义与用法示例

    本文实例讲述了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 递归函数详解及实例

    Python 递归函数 如果一个函数体直接或者间接调用自己,那么这个函数就称为递归函数．也就是说,递归函数体的执行过程中可能会返回去再次调用该函数．在python里,递归函数不需要任何特殊的语法,但是它需要付出一定的努力去理解和创建． 我们会以一个简单的例子开始:写一个函数求一个自然数中所有数字的和．在设计递归函数的时候,我们会寻找能把问题分解成简单的问题的方法．在这道题中,运算符%和//可以用来把一个数分成两部分:最低位和不包含最低位数字两部分． 18117的数字和为:1+8+1+1+7＝18

  • 提升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语言开发垃圾回收机制原理教程

    python语言开发垃圾回收机制原理教程

    目录 一.什么是垃圾回收机制 二.为什么要有垃圾回收机制 三.垃圾回收机制的原理 1.引用计数 直接引用 间接引用 2.栈区 / 堆区 3.总结 四.标记清除 1.循环引用问题(也叫交叉引用) 2.循环引用导致的结果 3.解决方法 : 清除-标记 五.分代回收 1.效率问题 2.解决方法 : 分代回收 分代 回收 总结 一.什么是垃圾回收机制 垃圾回收机制(简称GC), 解释器自带的一种机制 它是一种动态存储管理技术,自动释放不再被程序引用的对象所占用的内存空间 二.为什么要有垃圾回收机制 程序

  • python语法 之垃圾回收机制

    目录 一 引入 二.什么是垃圾回收机制? 三.为什么要用垃圾回收机制? 四.垃圾回收机制原理分析 4.1.什么是引用计数? 4.2.引用计数扩展阅读 4.2.1 标记-清除 4.2.2 分代回收 一 引入 ​ 解释器在执行到定义变量的语法时,会申请内存空间来存放变量的值,而内存的容量是有限的,这就涉及到变量值所占用内存空间的回收问题,当一个变量值没有用了(简称垃圾)就应该将其占用的内存给回收掉,那什么样的变量值是没有用的呢? ​ 由于变量名是访问到变量值的唯一方式,所以当一个变量值不再关联任何变

  • JavaScript 关于事件循环机制的刨析

    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的事件循环机制

    目录 单线程的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 异常. 如: >>&

随机推荐