详解python中递归函数

函数执行流程

def foo1(b,b1=3):
   print("foo1 called",b,b1)

 def foo2(c):
    foo3(c)
    print("foo2 called",c)
 def foo3(d):
   print("foo3 called",d)
 def main():
   print("main called")
   foo1(100,101)
   foo2(200)
   print("main ending ")

函数执行过程：

  1. 全局帧中生成foo1、foo2、foo3、main函数对象
  2. main函数调用
  3. main中查找内建函数print压栈，将常量字符串压栈，调用函数，弹出栈顶，返回值。
  4. main中全局查找foo1压栈，将常量100、101压栈，调用函数foo1，创建栈帧。print函数压栈，字符串和变量b、b1压栈，调用函数，弹出栈顶，返回值。
  5. main中全局查找foo2函数压栈，将常量200压栈，调用foo2，创建栈帧。foo3函数压栈，变量c引用压栈，调用foo3函数，创建栈帧，foo3中内建函数中查找print压栈，将字符常量和变量d压栈。foo3完成print函数调用后返回。foo2恢复调用，执行print后，返回值，main中foo2调用结束后弹出栈顶，main继续执行print函数调用，弹出栈顶，main函数返回

函数中压栈,执行流程。

递归Recursion

  1. 函数直接或者间接调用自身就是递归
  2. 递归需要有边界条件、递归前进段，递归返回段
  3. 递归一定需要有边界条件
  4. 当边界条件不满足的时候，递进前进
  5. 当边界条件满足的时候，递归返回

 递归要求

  1. 递归一定要有退出条件，递归调用一定执行到这个退出条件。没有退出条件的递归调用，就是无限调用
  2. 递归调用的深度不宜过深
  3. python对递归调用的深度做了限制，以保护解释器，cpython中递归深度为1000，ipython中递归深度为3000
  4. 超过递归深度限制，抛出RecursionError:maxinum recursion depth exceeded 超出最大深度
  5. sys.getrecursionlimit()是显示最大限制
  6. 对于基于前面或者换位置的时候使用封装和解构更有效

斐波那契数列实现（f(1)=1,f(2)=1,f(3)=f(1)+f(2),f(4)=f(2)+f(3)……）

#斐波那契数列普通循环实现
a,b=0,1
for i in range(4):
  a,b=b,a+b
print(a)

#斐波那契数列函数递归实现
def foo(n): #大量的重复计算
   return 1 if n<3 else foo(n-1)+foo(n-2) 

#斐波那契数列函数循环实现
def fn(n,a=0,b=1):
  a,b=b,a+b
  if n==1:
    return a
  return fn(n-1,a,b)

递归的性能

循环稍微复杂一些，但是只要不是死循环，可以多次迭代直至算出结果
递归还有深度限制，如果递归复杂，函数反复压栈，栈内存很快会溢出

间接递归

def foo1():
  foo2()
def foo2():
  foo1()

间接递归，是通过别的函数调用了函数自身，但是如果构成了循环递归调用是非常危险的，但是往往这种情况在代码复杂的情况下，还是有可能发生这种调用的，要用代码的规范来避免这种递归调用的发生

递归总结

  1. 递归是一种很自然的表达，符合逻辑思维
  2. 递归相对运行效率低，每一次调用函数都要开辟新的栈帧
  3. 递归有深度限制，如果递归层次太深，函数反复压栈，栈内存很快就溢出了
  4. 如果是有限次数的递归，可以使用递归调用，或者使用循环代替，循环代码稍微复杂一些，但是只要不是死循环，过次迭代直至算出结果
  5. 绝大多数递归，都可以使用循环实现
  6. 即使递归代码很简洁，能不用尽量不使用递归

以上所述是小编给大家介绍的python递归函数详解整合，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对我们网站的支持！

赞 (0)

相关推荐

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

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

    Python递归函数实例 1.打开Python开发工具IDLE,新建'递归.py'文件,并写代码如下: def digui(n): if n == 0 : print ('') return print ('*'*n) digui(n-1) if __name__ == '__main__': digui(5) 这里递归打印*号,先打印后递归 2.F5运行程序,打印内容如下: ***** **** *** ** * 3.更改一下打印和递归的 顺序,先递归后打印,代码如下: def digui(n

  • python递归函数绘制分形树的方法

    python递归函数绘制分形树的方法

    分形几何学的基本思想:客观事物具有自相似性的层次结构,局部和整体在形态,功能,信息,时间,空间等方面具有统计意义上的相似性,称为自相似性,自相似性是指局部是整体成比例缩小的性质. 我们先看一下我们最终要绘制的图形: 案例分析: 代码: ## 绘制分型树,末梢的树枝的颜色不同 import turtle def draw_brach(brach_length): if brach_length > 5: if brach_length < 40: turtle.color('green') el

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

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

  • 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 递归函数详解及实例

    Python 递归函数详解及实例

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

  • 详解Python中递归函数的原理与使用

    详解Python中递归函数的原理与使用

    目录 什么是递归函数 递归函数的条件 定义一个简单的递归函数 代码解析 内存栈区堆区 死递归 尾递归 实例 什么是递归函数 如果一个函数,可以自己调用自己,那么这个函数就是一个递归函数. 递归,递就是去,归就是回,递归就是一去一回的过程. 递归函数的条件 一般来说,递归需要边界条件,整个递归的结构中要有递归前进段和递归返回段.当边界条件不满足,递归前进,反之递归返回.就是说递归函数一定需要有边界条件来控制递归函数的前进和返回. 定义一个简单的递归函数 # 定义一个函数 def recursion

  • 详解python中递归函数

    函数执行流程 def foo1(b,b1=3): print("foo1 called",b,b1) def foo2(c): foo3(c) print("foo2 called",c) def foo3(d): print("foo3 called",d) def main(): print("main called") foo1(100,101) foo2(200) print("main ending &qu

  • 一文详解Python中生成器的原理与使用

    目录 什么是生成器 迭代器和生成器的区别 创建方式 生成器表达式 基本语法 生成器函数 yield关键字 yield和return yield的使用方法 生成器函数的基本使用 send的使用 可迭代对象的优化 总结 我们学习完推导式之后发现,推导式就是在容器中使用一个for循环而已,为什么没有元组推导式? 原因就是“元组推导式”的名字不是这样的,而是叫做生成器表达式. 什么是生成器 生成器表达式本质上就是一个迭代器,是定义迭代器的一种方式,是允许自定义逻辑的迭代器.生成器使用generator表

  • 详解python中executemany和序列的使用方法

    详解python中executemany和序列的使用方法 一 代码 import sqlite3 persons=[ ("Jim","Green"), ("Hu","jie") ] conn=sqlite3.connect(":memory:") conn.execute("CREATE TABLE person(firstname,lastname)") conn.executeman

  • 详解python中 os._exit() 和 sys.exit(), exit(0)和exit(1) 的用法和区别

    详解python中 os._exit() 和 sys.exit(), exit(0)和exit(1) 的用法和区别 os._exit() 和 sys.exit() os._exit() vs sys.exit() 概述 Python的程序有两中退出方式:os._exit(), sys.exit().本文介绍这两种方式的区别和选择. os._exit()会直接将python程序终止,之后的所有代码都不会继续执行. sys.exit()会引发一个异常:SystemExit,如果这个异常没有被捕获,那

  • 详解 Python中LEGB和闭包及装饰器

    详解 Python中LEGB和闭包及装饰器 LEGB L>E>G?B L:local函数内部作用域 E:enclosing函数内部与内嵌函数之间 G:global全局作用域 B:build-in内置作用域 python 闭包 1.Closure:内部函数中对enclosing作用域变量的引用 2.函数实质与属性 函数是一个对象 函数执行完成后内部变量回收 函数属性 函数返回值 passline = 60 def func(val): if val >= passline: print (

  • 详解python中的文件与目录操作

    详解python中的文件与目录操作 一 获得当前路径 1.代码1 >>>import os >>>print('Current directory is ',os.getcwd()) Current directory is D:\Python36 2.代码2 如果将上面的脚本写入到文件再运行 Current directory is E:\python\work 二 获得目录的内容 Python代码 >>> os.listdir (os.getcwd

  • 详解python中的 is 操作符

    大家可以与Java中的 == 操作符相互印证一下,加深一下对引用和对象的理解.原问题: Python为什么直接运行和在命令行运行同样语句但结果却不同,他们的缓存机制不同吗? 其实,高票答案已经说得很详细了.我只是再补充一点而已. is 操作符是Python语言的一个内建的操作符.它的作用在于比较两个变量是否指向了同一个对象. 与 == 的区别 class A(): def __init__(self, v): self.value = v def __eq__(self, t): return

  • 详解python中asyncio模块

    一直对asyncio这个库比较感兴趣,毕竟这是官网也非常推荐的一个实现高并发的一个模块,python也是在python 3.4中引入了协程的概念.也通过这次整理更加深刻理解这个模块的使用 asyncio 是干什么的? 异步网络操作并发协程 python3.0时代,标准库里的异步网络模块:select(非常底层) python3.0时代,第三方异步网络库:Tornado python3.4时代,asyncio:支持TCP,子进程 现在的asyncio,有了很多的模块已经在支持:aiohttp,ai

  • 详解python中的线程

    Python中创建线程有两种方式:函数或者用类来创建线程对象. 函数式:调用 _thread 模块中的start_new_thread()函数来产生新线程. 类:创建threading.Thread的子类来包装一个线程对象. 1.线程的创建 1.1 通过thread类直接创建 import threading import time def foo(n): time.sleep(n) print("foo func:",n) def bar(n): time.sleep(n) prin

随机推荐