一 递归函数
    定义：在调用一个函数的过程中又直接或间接地调用该函数本身
代码循环运行的两种方案
    方式一： while、for 循环
    方式二： 递归的本质就是循环。当一段代码要重复运行，可以考虑递归，
总结递归的使用：
    1.必须有一个明确的结束条件
        x +=1
        if x <10: return
        ---------------------
        x = x//2
        if  x >0 : f(x)
    2.每次进入更深一层递归时，问题规模相比上次递归都应有所减少
    3.递归效率不高，递归层次过多会导致栈溢出
回溯与递推
     回溯就是从外向里一层一层递归调用下去，
     回溯阶段必须要有一个明确地结束条件，每进入下一次递归时，问题的规模都应该有所减少（否则，单纯地      重复调用自身是毫无意义的）
     递推就是从里向外一层一层结束递归
   
三、递归案例
   **1.可以满足某个条件下调用本身函数，当条件不满足时候，递归停止**。

   **2.满足某个条件，用return来中止递归**
    3.用计数器 return 递归函数
    

image.png

一 递归函数

定义：在调用一个函数的过程中又直接或间接地调用该函数本身

在调用f1的过程中，又调用f1，这就是直接调用函数f1本身

def f1():
    print('from f1')
    f1()
f1()

image.png

在调用f1的过程中，又调用f2，而在调用f2的过程中又调用f1，这就是间接调用函数f1本身

def f1():
    print('from f1')
    f2()

def f2():
    print('from f2')
    f1()

f1()

image.png

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

提示：

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

>>> import sys
>>> sys.getrecursionlimit()
1000
>>>

#2. python不是一门函数式编程语言，无法对递归进行尾递归优化。

代码循环运行的两种方案

• 方式一： while、for 循环
• 方式二： 递归的本质就是循环

while True:
    print(11)

def foo():
    print(11)
    foo()

递归不应该无限地调用下去，必须在满足某种条件下结束递归

n =0
while n <10:
    print(n)
    n +=1

def func(n):
    if n == 10: # 满足条件 结束递归
        return
    print(n)
    n += 1
    func(n)

func(0)

总结递归的使用：

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

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

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

二、递归的应用

• 需求：嵌套多层的列表，要求打印出所有的元素，代码实现如下

# 需求：嵌套多层的列表，要求打印出所有的元素，代码实现如下
a = [1,2,[3,4,[5,6]]]
for i in a:
    if isinstance(i,list):
        # 如果是列表，应该再循环、再判断。即重新运行本身代码
        for m in i:
            if isinstance(m, list):
                pass
            else:
                print(m)
    else:
        print(i)

循环不知道多少层，上面这种方式就不可取

用递归怎么写
def f1(a):
    for i in a:
        if isinstance(i,list):
            # 如果是列表，应该再循环、再判断。即重新运行本身代码
            f1(i)
        else:
            print(i)
a = [1,3,4,[3,5,[7,8],[9,10]]]

print("--------------")
f1(a)
发现有重复一段代码要运行，就放在一个函数里面，在需要重复的地方调用自己。

二 回溯与递推

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

例4.5

某公司四个员工坐在一起，问第四个人薪水，他说比第三个人多1000，问第三个人薪水，第他说比第二个人多1000，问第二个人薪水，他说比第一个人多1000，最后第一人说自己每月5000，请问第四个人的薪水是多少？

思路解析：

要知道第四个人的月薪，就必须知道第三个人的，第三个人的又取决于第二个人的，第二个人的又取决于第一个人的，而且每一个员工都比前一个多一千，数学表达式即：

#1、递归调用应该包含两个明确的阶段：回溯，递推
回溯就是从外向里一层一层递归调用下去，
回溯阶段必须要有一个明确地结束条件，每进入下一次递归时，问题的规模都应该有所减少（否则，单纯地重复调用自身是毫无意义的）
递推就是从里向外一层一层结束递归
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就是结束条件。

image.png

代码实现：

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

s=salary(4)
print(s)

执行结果：

8000

程序分析：

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

递归本质就是在做重复的事情，所以理论上递归可以解决的问题循环也都可以解决，只不过在某些情况下，使用递归会更容易实现.

三、递归案例

上面总结了：递归要有一个明确的条件结束

1.可以满足某个条件下调用本身函数，当条件不满足时候，递归停止。

2.满足某个条件，用return来中止递归

image.png

见下面2个案例

案例一
def func(n):
    if n == 10: # 满足条件 结束递归
        return
    print(n)
    n += 1
    func(n)

func(0)

#递归的执行过程
def func_re(n):
    n = n // 2  # 地板除，商保留整数
    print(n)
    if n > 0:
        func_re(n)
    print(n) 
func_re(13)
'''
python中递归执行的逻辑是一层层调用，再一层层退出，可通过调试断点查看
6
3
1
0
0
1
3
6
'''

了解了递归调用的过程，那么如果我不想它一直调用下去，而是满足某一条件就返回，不再执行了呢？该怎么做呢？

用1个计算器count 来控制本身函数执行多少次，每次递增1.当不满足条件是递归结束
def calc(n,count):
    '''
    :param n: 需要进行递归的对象
    :param count: 计数器
    :return: 条件不成立时，返回最终值
    '''
    print(n,count)
    if count < 5: #运行第五次时退出
        return calc(n//2,count+1) #每一层接收它下一层的值，return必不可少，否则倒数第三层无法接收倒数第二层的返回值
    else:
        return n  # 在上一个return 递归函数被中止
f = calc(199,1)
print('res运算第五次时的结果：',f) # 输出>>res运算第五次时的结果： 12
结果：
199 1
99 2
49 3
24 4
12 5
res运算第五次时的结果： 12