python之函数递归与调用

一、什么是函数递归调用？

• 递归调用是函数嵌套调用的一种特殊形式
• 函数在调用时, 直接或间接调用了本身, 这就是递归调用
• 递归的本质就是循环

二、直接和间接调用示例

• 直接调用：死循环，无意义

def f1():
    print('from f1')
    f1()
f1()    # 当超过递归最大深度时报错 "RecursionError"

• 间接调用

def bar():
    print('sa')
    foo()

def foo():
    print('sds')
    bar()

foo()   # 这样来回调用无意义, 当超过递归最大深度时报错 "RecursionError"

三、递归最大深度设置与查看

死循环与递归的差别：

死循环并不会产生新的内存空间, 而函数的递归要不断的申请内存空间. 所以函数的递归要设置最大递归深度.

递归最大深度设置与查看

• 调用函数会产生局部的名称空间，占用内存，因为上述这种调用会无休止调用本身
• 为了防止其无限制占用内存，python 解释器的内存管理机制对函数的递归调用做了最大的层级限制

ps : 虽然可以修改, 但应该有边界, 不可能无限制的递归, 那样无意义, 递归应分为明确的两个阶段 (回溯, 递推)

示例:

# 查看递归深度: 默认值1000
import sys
print(sys.getrecursionlimit())  # 1000

# 指定递归深度: 但最终会受限于主即操作系统大小的限制
sys.setrecursionlimit(2000)
print(sys.getrecursionlimit())  # 2000

四、递归的本质

# 方式一: while, for循环
while True:
    print(111)
    print(222)
    print(333)
    
    
# 方式二: 递归的本质就是循环
def func():
    print(111)
    print(222)
    print(333)
    func()
func()  

五、强调：递归调用必须在满足某种条件下结束，不能无限递归调用下去

# while循环示例
i = 0
# 1. while循环
while i < 10:  # 2. 循环结束条件
    print(i, end=' ')  # 0 1 2 3 4 5 6 7 8 9
    i += 1  # 3. 累加条件
    
# 递归本质就是循环示例
def func(i):
    if i == 10:  # 2. 指定同while循环一样的结束循环的条件
        return
    print(i, end=' ')  # 0 1 2 3 4 5 6 7 8 9
    i += 1  # 3. 指定同while循环一样的累加条件

    func(i)  # 1. 同while循环一样让函数循环起来

func(0)

六、递归的两个阶段

• 回溯
  • 回溯就是从外向里层一层一层递归调用下去
  • 回溯阶段必须要有一个明确的结束条件
  • 每次进入下一次递归时, 问题的规模应该减少,否则单纯的无限的递归毫无意义
• 递推
  • 当某一层满足某种结束条件，结束了递归调用，然后从里到外一层一层返回结束递归调用

示例

# "回溯阶段"
age(5)=age(4)+2
age(4)=age(3)+2
age(3)=age(2)+2
age(2)=age(1)+2
age(1)=18  # 求 age(5) 的值

# 先研究表达式如何成立
n > 1 : age(n) = age(n-1) + 2
n = 1 : age(n) = 18

# 写函数计算 : "递推阶段"
def age(n):
    if n == 1:
        return 18
    return age(n-1)+2  # age(4)+2 = age(3)+2+2 = age(2)+2+2+2 = age(1)+2+2+2+2 = 18+8 = 26
print(age(5))          # 26

案例：

# 示例一: 有5个人, 第5个人说我的薪资比第4个人多1000, 第4个人说我的薪资比第3个人多1000, 第3个人说我的薪资比第2个人多1000, 第1个人说我的薪资是5000, 求第5个人的薪资?
def salary(n):
    if n == 1:  # 结束条件
        return 5000    
    return salary(n - 1) + 1000  # salary(4) + 1000 + salary(3) + 1000 + salary(2) + 1000 + salary(1) + 1000

s = salary(5)
print(s)  # 9000

# 示例二: 有5个人, 第5个人说我的年龄比第4个人大2岁, 第4个人说我的年龄比第3个人大2岁,第3个人说我的年龄比第2个人大2岁,第2个人说我的年龄比第1个人大2岁, 第1个人说我的年龄是38, 求第5个人年龄?
def age(n):
    if n == 1:  # 结束条件
        return 38
    return age(n-1) + 2  # 循环条件age(n-1) + 累加条件2  

print(age(5))  # 46

# 应用场景: 需求, 取出列中的每一个值
items = [1, 2, [3, [4, [5, [6, [7, [8, [9, 10, 11, [12, [13, ]]]]]]]]]]
def func(li: list):
    for item in li:  # 结束条件: li被迭代取值完毕
        if isinstance(item, list):
            func(item)  # 循环条件: 如果item不是列表, 那么继续递归
        else:
            print(item, end=' ')

func(items)  # 1 2 3 4 5 6 7 8 9 10 11 12 13 

七、总结

• 递归调用一定要有一个明确的结束条件（必须在满足某种条件下结束）
• 每次进入下一次递归，问题的规模都应该减少
• 在python中没有尾递归优化

问题规模减少简单示例:

# 将不是列表的值打印出来
l = [1, [2, [3, [4, [5, [6, [7, [8, [9]]]]]]]]]

def outter(itmes):
    for line in itmes:
        if type(line) is not list:
            print(line)
        else:
            outter(line)

outter(l)  # 1,2,3,4,5,6,7,8,9