python 递归与高阶函数

发布时间：2018-02-26 10:15:15编辑：admin阅读（3680）

    在函数内部，可以调用其他函数。如果一个函数在内部调用自身本身，这个函数就是递归函数。


    一个简单的递归函数(不正式)

    def calc(n):
    print(n)
    return calc(n)

calc(10)

    执行输出一堆10之后，报错

    RecursionError: maximum recursion depth exceeded while calling a Python object

    提示调用该对象超过最大递归深度


    查看python默认的最大递归深度，需要用sys模块

    import sys
print(sys.getrecursionlimit())

    执行输出 1000


    这个深度，可以通过setrecursionlimit()更改

    sys.setrecursionlimit(2000)

    除非特殊需要，不建议更改，会拖垮机器的。


    比如生活中的一个场景，2面镜子，对立着放着。你会里面，有无数个镜子，递归也是这样的。


    递归特性:


    1. 必须有一个明确的结束条件

    2. 每次进入更深一层递归时，问题规模相比上次递归都应有所减少

    3. 递归效率不高，递归层次过多会导致栈溢出（在计算机中，函数调用是通过栈（stack）这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以，递归调用的次数过多，会导致栈溢出）


    问题规模，指的是传递参数。比如说第一次传进去10，第二次，就不应该还是10，要比10小，否则程序无法结束。


    下面将一个正式的递归函数

    传一个参数进去，每次除以2，直到不能除为止，程序结束。

    def calc(n):
    print(n)
    #余数不能有小数,转换为整形
    if int(n/2) > 0:
        return calc(int(n/2))

calc(10)

    执行输出

    10

    5

    2

    1


    说明:

    1. 传参数10进去，输出10

    2. 10/2 结果为5，输出5

    3. 5/2 结果为2.5，结果取整，输出2

    4. 2/2 结果为1，输出1


    最后一步，1/2 结果小于0，不满足判断条件，程序终止。


    为了验证最后一步，是不是1呢，打印一下就知道了

    def calc(n):
    print(n)
    #余数不能有小数,转换为整形
    if int(n/2) > 0:
        return calc(int(n/2))
    print("end->",n)
    
calc(10)

    执行输出

    10

    5

    2

    1

    end-> 1


    1/2结果为0.5 取整之后，结果0。不满足判断条件，程序终止。


    为了方便查看程序的执行过程，可以通过给程序加断点，通过调试功能，观察过程

    效果如下：

    jindu2.gif


    高阶函数

    变量可以指向函数，函数的参数能接收变量，那么一个函数就可以接收另一个函数作为参数，这种函数就称之为高阶函数。


    def add(a,b,f):
    return f(a)+f(b)

res = add(3,-6,abs)
print(res)

    执行输出 9


    说明:

    abs是python的内置方法，用来取绝对值的，它会返回一个 非负数

    在执行add方法的时候，将abs赋值给f

    那么return的时候，实际是 abs(3)+abs(-6)

    最终结果为9


关键字：

上一篇： python 变量和作用域

下一篇： python 装饰器