首页 / PYTHON / python 递归函数

python 递归函数

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了python 递归函数，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2671字，纯文字阅读大概需要4分钟。

内容图文

1、函数执行流程：

            def foo1(a, a1=1):
　　print("foo1 called", a, a1)
    
def foo2(b):
　　foo3(b)
　　print("foo2 called", b)
    
def foo3(c):
　　print("foo3 called", c)
    
def main():
　　print("main called")
　　foo1(100, 101)
　　foo2(200)
　　print("main ending")
    
main()
    
# 函数执行流程：
1.全局帧中生成 foo1、foo2、foo3、main 函数对象；
2.main 函数调用；
3.main 中查找内建函数 print 压栈，将常量字符串压栈，调用函数，弹出栈顶；
4.main 中全局查找函数 foo1 压栈，将常量 100、101 压栈，调用函数 foo1，创建栈帧。print 函数压栈，字符串和变量 a、a1 压栈，调用函数，弹出栈顶，返回值；
5.main 中全局查找 foo2 函数压栈，将常量 200 压栈，调用 foo2，创建栈帧。foo3 函数压栈，变量 b 引用压栈，调用 foo3，创建栈帧。foo3 完成 print 函数调用后返回。foo2 恢复调用，执行 print 后，返回值。main 中 foo2 调用结束弹出栈顶，main 继续执行 print 函数，弹出栈顶，main 函数返回。

 

            def
             foo(a):
    
            print(‘foo‘)
    
def main():
    print(‘main start‘)
    foo([])     # 在内存中即堆中开辟一个列表，压栈地址，弹出
    foo([])     # 在堆中再开辟一个列表，压栈地址，弹出print(‘main ending‘)
    
main()
    
    
def foo1(a):
    print(‘foo1‘)
    
def main():
    print(‘main start‘)
    lst = []    # 先在堆中开辟一个列表，压栈
    foo1(lst)   # 引用地址，弹出，列表不消亡
    foo1(lst)   # 再引用地址print(‘main ending‘)
    
main()

 

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

            import
             sys

            print(sys.getrecursionlimit())    # cpython 对递归调用的深度做了限制，限制 1000 下调用def foo1():
    foo1()
foo1()    # 最大递归深度(函数栈太大)限制，报错

 

　　例：斐波那契数列 Fibonacci number：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
　　如果设 F(n) 为该数列的第n项 (n∈N*)，那么这句话可以写成如下形式：F(n)=F(n-1)+F(n-2)
　　F(0)=0, F(1)=1, F(n)=F(n-1)+ F(n-2)

            #
             循环实现
a, b = 0, 1
for i in range(35):
    a, b = b, a+b
print(a)
    
# 递归实现def fib(n):    # 函数调用特别多，一层一层if n < 3:  # 定义边界return 1
    return fib(n-1) + fib(n-2)
    print(fib(4))

def fib1(n):
    return 1 if n < 3 else fib(n-1) + fib(n-2)
    print(fib(4))
    
# 递归解析：层层解析，循环计算，效率低下
fib(5) = fib(4) + fib(3)
fib(4) = fib(3) + fib(2)
fib(3) = fib(2) + fib(1)

 

　　递归要求：
　　　　递归一定要有退出条件，递归调用一定要执行到这个退出条件。没有退出条件的递归调用，就是无限调用
　　　　递归调用的深度不宜过深
　　　　　　Python 对递归调用的深度做了限制，以保护解释器
　　　　　　超过递归深度限制，抛出 RecursionError: maxinum recursion depth exceeded 超出最大深度
　　　　　　sys.getrecursionlimit()，查看最大深度
　　递归的性能：
　　　　循环稍微复杂一些，但是只要不是死循环，可以多次迭代直至算出结果。
　　　　fib 函数代码极简易懂，但是只能获取到最外层的函数调用，内部递归结果都是中间结果。而且给定一个 n 都要进行近 2n 次递归，深度越深，效率越低。为了获取斐波那契数列需要外面再套一个 n 次的循环，效率就更低了。
　　　　递归还有深度限制，如果递归复杂，函数反复压栈，栈内存很快就溢出了。

　　思考：这个极简的递归代码能否提高性能呢?

            #
             函数调用模拟循环
            def fib(n, a=0, b=1):
    a, b = b, a + b
    if n == 1:
        return a
    return fib(n-1, a, b)
print(fib(4))

 

　　间接递归，是通过别的函数调用了函数自身

            def
             foo1():
    foo2()
    

            def
             foo2():
    foo1()

　　但是，如果构成了循环递归调用是非常危险的，但是往往这种情况在代码复杂的情况下，还是可能发生这种调用。要用代码的规范来避免这种递归调用的发生。
　　递归总结：
　　　　递归是一种很自然的表达，符合逻辑思维；
　　　　递归相对运行效率低，每一次调用函数都要开辟栈帧；
　　　　递归有深度限制，如果递归层次太深，函数反复压栈，栈内存很快就溢出了；
　　　　如果是有限次数的递归，可以使用递归调用，或者使用循环代替，循环代码稍微复杂一些， 但是只要不是死循环，可以多次迭代直至算出结果；
　　　　绝大多数递归，都可以使用循环实现；
　　　　即使递归代码很简洁，但是能不用则不用递归。

 

3、递归练习：

　　求 n 的阶乘：

            #
             循环实现
n = 6
value = 1
for i in range(1, n+1):
    value = (i * value)
print(value)

# 递归实现def fib(n):
    return 1 if n == 1 else n * fib(n-1)
print(fib(6))

 

原文：https://www.cnblogs.com/zyybky/p/12795665.html

内容总结

以上是互联网集市为您收集整理的python 递归函数全部内容，希望文章能够帮你解决python 递归函数所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1245052.html

来源：【匿名】