您的位置:首页 > 脚本大全 > > 正文

python语言中的递归(详解python中递归函数)

更多 时间:2021-10-15 00:18:12 类别:脚本大全 浏览量:2024

python语言中的递归

详解python中递归函数

函数执行流程

  • ?
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 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)……)

  • ?
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • #斐波那契数列普通循环实现
  • 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)
  • 递归的性能

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

    间接递归

  • ?
  • 1
  • 2
  • 3
  • 4
  • def foo1():
  •   foo2()
  • def foo2():
  •   foo1()
  • 间接递归,是通过别的函数调用了函数自身,但是如果构成了循环递归调用是非常危险的,但是往往这种情况在代码复杂的情况下,还是有可能发生这种调用的,要用代码的规范来避免这种递归调用的发生

    递归总结

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

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

    原文链接:https://blog.csdn.net/qq_36883141/article/details/89319035

    您可能感兴趣