高阶函数-递归

1.高阶函数

1.1高阶函数定义

变量可以指向函数，函数的参数能接受变量，那么一个函数就可以接收另一个函数作为参数，这种函数就称为高阶函数。
只要满足以下任意一个条件，即是高阶函数
1.接收一个或多个函数作为输入
2.return返回另外一个函数

#!/usr/bin/env python
# -*- coding:utf-8 -*-
# Author: vita

def add(x, y, func):
    return func(x) + func(y)
res = add(3, -6, abs)
print(res)

E:\PythonProject\python-test\venvP3\Scripts\python.exe E:/PythonProject/python-test/BasicGrammer/test.py
9

Process finished with exit code 0

2.递归

2.1递归定义

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

#!/usr/bin/env python
# -*- coding:utf-8 -*-
# Author: vita

def calc(n):
    print(n)
    if int(n/2) == 0:
        return n
    return calc(int(n/2))
calc(4)

E:\PythonProject\python-test\venvP3\Scripts\python.exe E:/PythonProject/python-test/BasicGrammer/test.py
4
2
1

Process finished with exit code 0

2.2递归的执行过程

#!/usr/bin/env python
# -*- coding:utf-8 -*-
# Author: vita

def calc(n):
    print(n)
    if int(n/2) > 0:
        calc(int(n/2))
    print(n)
calc(4)

E:\PythonProject\python-test\venvP3\Scripts\python.exe E:/PythonProject/python-test/BasicGrammer/test.py
4
2
1
1
2
4

Process finished with exit code 0

2.3递归特性

1.必须有一个明确的结束条件
2.每次进入更深一层递归时，问题规模相比上次递归都应有所减少
3.递归效率不高，递归层次过多会导致栈溢出（在计算机中，函数调用时通过栈(stack)这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以递归调用的次数过多，会导致栈溢出）

    #!/usr/bin/env python
# -*- coding:utf-8 -*-
# Author: vita

def recursion(n):
    print(n)
    recursion(n + 1)

recursion(1)
运行
...
996
997
998
Process finished with exit code 1
"到998程序就自动停止了，是因为递归的最大深度是有限制的，防止栈溢出"

2.4二分法查找

    #!/usr/bin/env python
# -*- coding:utf-8 -*-
# Author: vita

data = [1, 3, 5, 7, 8, 10, 30, 34, 35]

def binary_search(source_data, search_data):
    print(source_data)
    if len(source_data) > 1:
        mid_data_index = int(len(source_data)/2)
        if source_data[mid_data_index] == search_data:
            print("excellent,you have found it!")
        elif source_data[mid_data_index] > search_data:
            source_data = source_data[0:mid_data_index]
            binary_search(source_data, search_data)
        elif source_data[mid_data_index] < search_data:
            source_data = source_data[mid_data_index + 1:]
            binary_search(source_data, search_data)
    else:
        if len(source_data) == 0:
            print("source data is null now!")
        else:
            if source_data[0] == search_data:
                print("you have found it!")
            else:
                print("there is not this number!")
binary_search(data, 30)

E:\PythonProject\python-test\venvP3\Scripts\python.exe E:/PythonProject/python-test/BasicGrammer/test.py
[1, 3, 5, 7, 8, 10, 30, 34, 35]
[10, 30, 34, 35]
[10, 30]
excellent,you have found it!

Process finished with exit code 0
"找4"
binary_search(data, 4)
E:\PythonProject\python-test\venvP3\Scripts\python.exe E:/PythonProject/python-test/BasicGrammer/test.py
[1, 3, 5, 7, 8, 10, 30, 34, 35]
[1, 3, 5, 7]
[1, 3]
[]
source data is null now!

Process finished with exit code 0

2.5求阶乘

#!/usr/bin/env python
# -*- coding:utf-8 -*-
# Author: vita

def multi(n):
    if n == 1:
        return 1
    else:
        return n*multi(n-1)

print(multi(4))

E:\PythonProject\python-test\venvP3\Scripts\python.exe E:/PythonProject/python-test/BasicGrammer/test.py
24

Process finished with exit code 0

2.6斐波那契

    #!/usr/bin/env python
# -*- coding:utf-8 -*-
# Author: vita
# 1 1 2 3 5 8 13
a = 0
b = 1
n = 0
def fibs(a, b):
    global n
    a, b = b, a + b
    print(a)
    if n == 5:
        return
    n += 1
    fibs(a, b)

fibs(a,b)

E:\PythonProject\python-test\venvP3\Scripts\python.exe E:/PythonProject/python-test/BasicGrammer/test.py
1
1
2
3
5
8

Process finished with exit code 0

2.7尾递归

再讲递归特性时，我们说递归效率不高，因为每递归一次，就多了一层栈，递归次数过多就会栈溢出，这也是Python默认会限制递归次数的原因。但有一种方式是可以在递归过程中不产生多层栈，即尾递归。
如果一个函数中所有递归形式的调用都出现在函数的末尾，我们称这个递归函数是尾递归的。当递归调用时整个函数体重最后执行的语句且它的返回值不属于表达式的一部分，这个递归调用就是尾递归。尾递归函数的特点是在回归过程中不用做任何操作，这个特性很重要，因为大多数现代的编译机会利用这个特点自动生成优化的代码。
当编译器检测到一个函数调用时尾递归，就会覆盖当前活动记录，而不是在栈中去创建新的。编译器可以做到这点，因为递归调用时当前活跃期内最后执行的一条语句，于是当这个调用返回时帧栈中并没有其他事情可做，因此也就没有保存栈帧的必要了。通过覆盖当前的栈帧而不是重新添加一个，这样就节省了栈帧的使用，运行效率变高。

"尾递归的例子"
#!/usr/bin/env python
# -*- coding:utf-8 -*-
# Author: vita

def calc(n):
    print(n)
    if n > 0:
        return calc(n-1)
calc(8)

那么阶乘的例子是尾递归吗？
不是尾递归，因为每个活跃的返回值都依赖于用n乘以下一个活跃期的返回值，因此每次调用产生的栈帧不得不保存在栈上直到下一个子调用的返回值确定。

python中实际是没有做尾递归的优化，但别的语言有优化的