Python:递归函数

一、函数的递归

　　什么是函数的递归：函数的递归就是函数的递归调用：是函数嵌套调用的一种形式。

　　具体是指：在调用一个函数的过程中又直接或者间接的调用到本身。

# 1、直接调用本身（简单理解为死循环 ）
def f1():
    print('直接调用本身实例：')
    f1()

# 调用
f1()

# 由于没有设定退出条件，抛出异常
# RecursionError: maximum recursion depth exceeded while calling a Python object。
# python对递归做了限制1000层，否则无限的调用下去，不断的申请内存空间，直到内存溢出。
# 了解python的递归层级

import sys

>>> sys.getrecursionlimit()  # 可以使用sys.getrecursionlimit()去查看递归深度，默认值为1000

 1000 

>>> sys.getrecursionlimit(2000) # 可以自己定义对限制进行修改为2000，不建议这样做，容易造成内存溢出。 
>>> sys.getrecursionlimit() 
2000

python不是一门函数式编程语言，无法对递归进行尾递归优化（了解）

函数的递归：直接调用示意图：

# 2、间接调用本身()
def f1():
    print("===>f1")
    f2()

def f2():
    print("===>f2")
    f1()

f1()
# 打印之后，抛出对应异常
# RecursionError: maximum recursion depth exceeded while calling a Python object

函数的递归：间接调用示意图：

二、递归与循环

# 递归与循环:递归的本质就是循环，递归能做的，while循环都能做。
# 一段diamond循环的方案有两种
# 方式一：while、for循环
# while True:
#     print(1111)
#     print(2222)
#     print(3333)
# 这个不能停止

# 方式二：使用递归
def f1():
    print(1111)
    print(2222)
    print(3333)
    f1()

f1()
# RecursionError: maximum recursion depth exceeded while calling a Python object

# 需要强调一点：
# 1、递归不应该无限的调用下去，必须在满足某种条件下结束递归

# 使用while循环：输出1-10的数据
# n = 0
# while n<10:
#     print(n)
#     n +=1

# 使用递归：输出1-10的数据
def f1(n):
    if n == 10:
        return
    print(n)
    n += 1
    f1(n)
f1(0)

三、回溯和递推

# 递归两个阶段：回溯与递推

# 回溯：一层一层的调用下去
# 递推：满足某种结束条件后，结束递归调用，然后一层一层返回。

# 举例：询问年龄
# A比B大10岁，B比C大10岁，C比D大10岁，D比E大10岁，E为18岁  # 回溯：

# age(5) = age(4) + 10
# age(4) = age(3) + 10
# age(3) = age(2) + 10
# age(2) = age(1) + 10
# age(1) = 18

def age(n):
    if n == 1:
        return 18
    return age(n -1) + 10

res = age(5)
print(res)

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

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

res = salary(4)
print(res)

思路解析：

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

# salary(4)-->salary(3)+1000-->salary(2)+1000 + 1000-->salary(1)+1000+1000+1000-->5000+1000+1000+1000
# salary(4)-->salary(3)+1000-->salary(2)+1000《==None+1000（TypeError: unsupported operand type(s) for +: 'NoneType' and 'int'）《==5000+1000
# TypeError: unsupported operand type(s) for +: 'NoneType' and 'int' 翻译：None类型和整型进行了加操作。
# 解决办法：添加返回值return
# salary(4) = 8000《==5000+1000+1000+1000《==5000+1000+1000《==5000+1000《==5000
#                      salary(4)            salary(3)         salary(2)    salary(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) 

回溯和递推示意图如下：

  四、递归的应用

# 需求：把如下列表的所有值取出来，并打印。
# l = [1,2,[3,[4,[5,[6,[7,[8,[9,10,11]]]]]]]]

# 方式一：使用循环实现需求
# l = [1,2,[3,4]]
# for x in l:
#     if type(x) is list:
#         # 如果是列表，应该再次循环，再次判读，再次打印，即重新运行本身的代码。
#         for a in x:
#             if type(a) is list:
#                 pass
#             else:
#                 print(a)
#     else:
#         print(x)
# 运行结果：1 2 3 4 


# 方式二：使用递归实现需求
l = [1,2,[3,4]]
def f1(list1):
    for x in list1:
        if type(x) is list:
            # 如果是列表，应该再次循环，再次判读，再次打印，即重新运行本身的代码。
            f1(x)
        else:
            print(x)

f1(l)  # 运行结果：1 2 3 4 5 6 7 8 9 10 11