函数递归

一、介绍

函数不仅仅可以嵌套定义，并且还可以进行嵌套调用，也就是在调用一个函数的过程中，函数内部又调用另一个函数，而函数的递归调用指的是在调用一个函数的过程中又直接或者间接的调用该函数本身。

1、函数直接调用自己

比如说：再调用func1的过程中，又调用func1，这就是直接调用函数func1本身

def func1():
    print('From func1')
    func1()
func1()

2、函数简介调用自己

在调用func1的过程中，又调用func2，而在调用func2的过程中又调用func1，这就是间接调用函数func1本身。

def func1():
    print('From func1')
    func2()

def func2():
    print('From func2')
    func1()

func1()

从上图中可以看出，两种情况下的递归调用都是一个无限循环的过程，但是Python对函数的递归调用的深度做了限制，因而并不会像大家所想的那样进入无限的循环，会抛出异常，要避免出现这种情况，就必须让递归调用在满足某个特定条件下终止。

3、温馨提示

可以使用sys.getrecursionlimit()去查看递归深度，默认值为1000，虽然可以使用sys.setrecursionlimit()去设定该值，但仍受限于主机操作系统栈大小的限制

import sys
print(sys.getrecursionlimit())

# 结果
1000

Python不是一门函数式编程语言，无法对递归进行尾递归优化,所以大家不必关注这个知识点

二、回溯与递归

1、算薪水

1.例子

接下来我们使用一个浅显的例子，为了让读者阐释递归的原理和使用：

某公司四个员工坐在一起。

问第四个人的薪水，他说比第三个人多1000

问第三个人的薪水，他说比第二个人多1000

问第二个人的薪水，他说比第一个人多1000

最后问第一个人的薪水，他说自己的薪水是5000，那么请问第四个人的薪水是多少？？？

思路解析：

2.数学表达式

要知道第四个人的月薪，就必须知道第三个人的，第三个人的又取决于第二个人的，第二个人又取决于第一个人的，因此数学表达式可以是以下这个样子

salary(4) = salary(3) + 1000
salary(3) = salary(2) + 1000
salary(2) = salary(1) + 1000
salary(1) = 5000

总结为：
salary(n) = salary(n-1) + 1000 (n>1)
salary(1) = 5000 (n=1)

很明显这是一个递归的过程，可以将该过程分为两个阶段：回溯和递推

在回溯阶段，要求第n个员工的薪水，需要回溯得到(n-1)个员工的薪水，依此类推，直到得到第一个员工的薪水，此时，salary(1)已知，因而不必再向前回溯了，然后进入递推阶段：从第一个员工的薪水可以推算出第二个员工的薪水(6000)，从第二个员工的薪水可以推算出第三个员工的薪水(7000)，以此类推，一直推算出第四个员工的薪水(8000)为止，递归结束。需要注意的一点是，递归一定要有一个结束条件，这里n=1就是结束条件。

3.用python表示

def salary(n):
    if n==1:
        return 5000
    return salary(n-1) + 1000

s = salary(4)
print(s)

在未满足n == 1的条件的时候，一直进行递归调用，即一直回溯。而在满足n == 1的条件的时候，终止递归调用，即结束回溯，从而进入递推阶段，依次推导直到得到最终的结果。

4.小案例

递归本质就是在做重复的事情，所以理论上递归可以解决的问题循环也都可以解决，只不过在某些情况下，使用递归会更容易实现，比如有一个嵌套多层的列表，要求打印出所有的元素，代码实现如下：

l = [[1, 2], 3, [4, [5, [6, 7]]]]

def foo(items):
    for i in items:
        if type(i) is list:
            foo(i)  # 满足未遍历完items以及if判断成立的条件时，一直进行递归调用
        else:
            print(i, end='')


foo(l)

# 结果
1234567

或者

• type() 不会认为子类是一种父类类型，不考虑继承关系。
• isinstance() 会认为子类是一种父类类型，考虑继承关系。

items = [[1, 2], 3, [4, [5, [6, 7]]]]


def foo(items):
    for i in items:
        if isinstance(i, list):
            foo(i)  # 满足未遍历完items以及if判断成立的条件时，一直进行递归调用
        else:
            print(i, end=' ')

foo(items)

# 结果
1 2 3 4 5 6 7

使用递归，我们只需要分析出要重复执行的代码逻辑，然后提取进入下一次递归调用的条件或者说递归结束的条件即可，代码实现起来简洁清晰。

三、二分法

算法：是高效解决问题的方法

我们可以利用二分法来实现高效查找元素，比如说:

需求：

有一个按照从小到大顺序排列的数字列表

需要从该数字列表中找到我们想要的那个一个数字

如何更高效？？？

num_lis = [-3, 0, 2, 4, 5, 7, 8, 10, 12, 15, 25, 27, 35, 45, 55, 65, 75, 85, 95, 105]


def search2(find_num, num_lis):
    print(num_lis)
    if num_lis.__len__() == 0:
        print(f'不存在')
        return
    mid_index = num_lis.__len__() // 2
    if find_num > num_lis[mid_index]:
        # 在右边
        new_num_lis = num_lis[mid_index + 1:]  # 做一个切片
        search2(find_num, new_num_lis)
    elif find_num < num_lis[mid_index]:
        # 在左边
        new_num_lis = num_lis[:mid_index]
        search2(find_num, new_num_lis)
    else:
        # 就是他自己
        print('找到了')


search2(35, num_lis)

# 结果
[-3, 0, 2, 4, 5, 7, 8, 10, 12, 15, 25, 27, 35, 45, 55, 65, 75, 85, 95, 105]
[27, 35, 45, 55, 65, 75, 85, 95, 105]
[27, 35, 45, 55]
[27, 35]
找到了