python 递归与高阶函数

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

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

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