Python 函数的递归调用

Python 函数的递归调用

函数的嵌套调用

1
2
3
4
5
6
7
8
def bar():
print('from bar')

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

foo()

函数递归

函数的递归调用,就是函数嵌套调用的一种特殊格式
函数递归调用,在调用一个函数的过程中又直接或间接地调用了自己
本质就是一个重复的过程,递归必须要有一个明确的结束条件,在满足该条件的情况下,会终止递归
每一次重复问题的规模都应该有所减少

直接调用

1
2
3
4
5
6
7
8
9
10
11
def bar():
print('from bar')

def foo():
print('from foo')
foo()

foo()

# 执行结果
RecursionError: maximum recursion depth exceeded while calling a Python object

注:Python 中没有伪递归优化这一说

间接调用

1
2
3
4
5
6
7
8
9
10
11
12
def bar():
print('from bar')
foo()

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

foo()

# 执行结果
RecursionError: maximum recursion depth exceeded while calling a Python object

Python 限制递归调用最大层级是多少?

1
2
3
4
5
6
7
8
9
def foo(n):
print('from foo', n)
foo(n+1)

foo(0)

# 执行结果
from foo 997 # 这里看到的并不精准
RecursionError: maximum recursion depth exceeded while calling a Python object

使用 sys.getrecursionlimit() 可以查看到

1
2
3
4
5
import sys
print(sys.getrecursionlimit())

# 执行结果
1000

递归的最大层级这个值是可以修改的,但是没有多大的意义
sys.setrecursionlimit(10000)

递归必须满足两个阶段

  1. 回溯:一层一层地递归调用下去
  2. 递推:递归必须要有一个明确的结束条件,在满足该条件的情况下,会终止递归,往回一层一层地结束调用

练习

猜年龄

第一个人 18 岁
第二个人比第一个人大2岁
第三个人比第二个人大2岁
第四个人比第三个人大2岁
第五个人比第四个人大2岁
问第五个人的年龄是多少岁?

1
2
3
4
5
6
7
8
age(5) = age(4) + 2
age(4) = age(3) + 2
age(3) = age(2) + 2
age(2) = age(1) + 2
age(1) = 18

age(n) = age(n-1) + 2 # n > 1
age(n) = 18 # n = 1
1
2
3
4
5
6
7
8
9
def age(n):
if n == 1:
return 18
return age(n-1) + 2

print(age(5))

# 执行结果
26

回溯递推

递归是一次重复的过程,每一次重复问题的规模都应该有所减少

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
l = [1, [2, [3, [4, [5, [6, [7, [8, [9, ]]]]]]]]]

def tell(l):
for item in l:
if type(item) is not list:
print(item)
else:
tell(item)

tell(l)

# 执行结果
1
2
3
4
5
6
7
8
9

递归 vs while循环

递归只需要把控住结束或进入递归的条件,至于循环次数无需考虑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
l = [1, [2, [3, [4, [5, [6, [7, [8, [9, ]]]]]]]]]

def tell(l):
for item in l:
if type(item) is list:
# item 是列表
# 再次调用本身的逻辑,传入item
tell(item)
else:
# item 是单独的元素
print(item)

tell(l)

# 执行结果
1
2
3
4
5
6
7
8
9

递归的应用

二分法

数字列表,数字从小打大排列
需求:判断某一个值是否存在于这个列表中

1
2
3
4
5
6
7
8
9
10
11
12
nums = [3, 11, 13, 15, 23, 27, 43, 51, 72, 81, 93, 101]

find_num = 27
for num in nums:
if find_num == num:
print('find it')
break
else:
continue

# 执行结果
find it

以上方式效率较低

算法:就是高效解决某个问题的方法
二分法是算法中的其中之一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
nums = [3, 11, 13, 15, 23, 27, 43, 51, 72, 81, 93, 101]

# l1 = [3, 11, 13, 15, 23, 27]
# l2 = [23, 27]
# l3 = [23]

def binary_search(nums, find_num):
mid_index = len(nums) // 2
if find_num > nums[mid_index]:
# in the right
# 从一个大列表中取出一个子列表
nums = nums[mid_index+1:]
# 重复调用本身的逻辑,传入切分之后的结果
binary_search(nums, find_num)
elif find_num < nums[mid_index]:
# in the left
nums = nums[:mid_index]
# 重复调用本身的逻辑,传入切分之后的结果
binary_search(nums, find_num)
else:
print('find it')

binary_search(nums, 23)

# 执行结果
find it

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
nums = [3, 11, 13, 15, 23, 27, 43, 51, 72, 81, 93, 101]

def binary_search(nums, find_num):
print(nums) # 获取查找次数
mid_index = len(nums) // 2
if find_num > nums[mid_index]:
# in the right
# 从一个大列表中取出一个子列表
nums = nums[mid_index+1:]
# 重复调用本身的逻辑,传入切分之后的结果
binary_search(nums, find_num)
elif find_num < nums[mid_index]:
# in the left
nums = nums[:mid_index]
# 重复调用本身的逻辑,传入切分之后的结果
binary_search(nums, find_num)
else:
print('find it')

binary_search(nums, 23)

# 执行结果
[3, 11, 13, 15, 23, 27, 43, 51, 72, 81, 93, 101]
[3, 11, 13, 15, 23, 27]
[23, 27]
[23]
find it

传入一个不存在的值,会抛超出列表索引超出范围异常

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
nums = [3, 11, 13, 15, 23, 27, 43, 51, 72, 81, 93, 101]

def binary_search(nums, find_num):
print(nums)
mid_index = len(nums) // 2
if find_num > nums[mid_index]:
nums = nums[mid_index+1:]
binary_search(nums, find_num)
elif find_num < nums[mid_index]:
nums = nums[:mid_index]
binary_search(nums, find_num)
else:
print('find it')

binary_search(nums, 94) # 传入一个不存在的值,会抛超出列表索引超出范围异常

# 执行结果
IndexError: list index out of range

改进

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
nums = [3, 11, 13, 15, 23, 27, 43, 51, 72, 81, 93, 101]

def binary_search(nums, find_num):
print(nums)
if len(nums) == 0:
print('not exists')
return
mid_index = len(nums) // 2
if find_num > nums[mid_index]:
nums = nums[mid_index+1:]
binary_search(nums, find_num)
elif find_num < nums[mid_index]:
nums = nums[:mid_index]
binary_search(nums, find_num)
else:
print('find it')

binary_search(nums, 94)

# 执行结果
[3, 11, 13, 15, 23, 27, 43, 51, 72, 81, 93, 101]
[51, 72, 81, 93, 101]
[93, 101]
[93]
[]
not exists
---------------- The End ----------------
0%