03.递归
# 01.递归
# 1.1 递归讲解
1、定义
- 在函数内部,可以调用其他函数。
- 如果一个函数在内部调用自身本身,这个函数就是递归函数。
2、递归特性
1.必须有一个明确的结束条件
2.每次进入更深一层递归时,问题规模相比上次递归都应有所减少
3.递归效率不高,递归层次过多会导致栈溢出(在计算机中,函数调用是通过栈(stack)这种数据结构实现的
4.每当进入一个函数调用,栈就会加一层栈帧,每当函数返回,栈就会减一层栈帧。
5.由于栈的大小不是无限的,所以,递归调用的次数过多,会导致栈溢出)
# 1.2 递归原理讲解
1.每一次函数调用都会有一次返回,并且是某一级递归返回到调用它的那一级,而不是直接返回到main()函数中的初始调用部分。
2.第一次递归:n=3入栈【3】
3.第二次递归:n=2入栈【3,2】
4.第三次递归:n=1入栈【3,2,1】
5.当n=0时0>0为False,不再递归,print num=0,函数返回到调用他的上一级,即栈顶n=1
6.接着位置digui(num-1)向下执行:此时打印printnum=1,1出栈,栈中元素:【3,2】
7.依次类推会打印2,3所以最终打印结果如右图
8.图解
#! /usr/bin/env python
# -*- coding: utf-8 -*-
def digui(num):
print num
if num > 0:
digui(num - 1)
else:
print '------------'
print num
digui(3)
''' 执行结果
3
2
1
0
------------
0
1
2
3
'''
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 1.3 结果剖析
1.为什么会得出上面的结果呢?因为都把调用函数本身之后的代码给忘记了,就是else之后的python 代码。
2.在调用函数本身时,它之后的代码并没有结束,而是在等待条件为False 时,再接着执行之后的代码,同一个颜色的print()语句等待对应颜色的函数。
3.下面我把此递归函数做了一个分解,详解递归函数,当调用递归函数digui(3)时,执行过程如下:
# 02.求阶乘代码
# 2.1 代码
#! /usr/bin/env python
# -*- coding: utf-8 -*-
def test(n):
if n == 1:
return 1
else:
res = n*test(n-1)
print( "n:%s-----ret:%s"%(n, res) )
return res
print( test(4) ) # 24
'''
n:2-----ret:2
n:3-----ret:6
n:4-----ret:24
24
'''
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 2.2 求4的阶乘递归推演
# 1、递归步骤
'''
1、第一层:test(4) = 4*test(4-1)
2、第二层:test(3) = 3*test(3-1)
3、第三层:test(2) = 2*test(2-1)
4、第四层:test(1) = 1
'''
# 2、返回步骤
'''
注:上层调用的位置都是:res = n*test(n-1),所以返回上层后会接着这里向下执行知道return
5、n=1那么就会执行if代码块内的代码return 1此时第四层函数结束: ret = 1
6、第四层函数结束后会接着第三层调用的位置向下执行直到return: ret = 1 * 2
7、第三层函数返回后会回到第二层调用位置return: ret = 1 * 2 * 3
8、第二层函数返回后会回到第一层调用位置return: ret = 1 * 2 * 3 * 4
到达第一层调用位置后,没有上层的递归调用位置,此时函数才会正真返回。
'''
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
步骤图解
# 03.将字典中整数转换成字符串
d1 = {"a":1,"b":2, "f":{'c':3,'d':4,"h":{"k":10}}}
def get_k(data_json):
if isinstance(data_json, dict): # 判断当前传入的值是否是字典
for key in data_json.keys(): # 如果是字典,就以key循环字典
if isinstance(data_json[key], dict): # 如果是字典就递归调用,传入这个字典
get_k(data_json[key])
else:
data_json[key] = str(data_json[key]) # 如果不是字典,就将value转换成str
return data_json
print( get_k(d1) ) # {'a': '1', 'b': '2', 'f': {'c': '3', 'd': '4', 'h': {'k': '10'}}}
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
# 04.求树的高度
# 4.1 代码
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def maxDepth(root):
if root is None: return 0
l = maxDepth(root.left)
r = maxDepth(root.right)
return max(l, r) + 1
if __name__ == '__main__':
root = TreeNode(3,
left=TreeNode(9),
right=TreeNode(20, TreeNode(15), TreeNode(7, TreeNode(10)))
)
print(maxDepth(root)) # 4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 4.2 步骤解释
- 第一步:在节点1执行第一句代码
- 很明显1节点不为None,执行
l = maxDepth(root.left)
- 很明显1节点不为None,执行
- 第二步:递归节点2
- 节点2有左子树,继续执行
l = maxDepth(root.left)
- 节点2有左子树,继续执行
- 第三步:递归节点4
- 节点4没有左子树,执行
if root is None: return 0
,4节点的 L=0 - 然后执行
r = maxDepth(root.right)
4节点没有右子树,4 节点的 R=0 - 最后执行
return max(l, r) + 1
此时L=0,R=0,所以返回1 - 此时返回到调用节点2,节点2的 L=1
- 节点4没有左子树,执行
- 第四步:此时出栈,返回到调用节点2,节点2的 L=1
- 执行
r = maxDepth(root.right)
,2节点有右节点,递归到节点5
- 执行
- 第五步:此时递归节点5
- 节点5没有左子树,执行
if root is None: return 0
,5节点的 L=0 - 然后执行
r = maxDepth(root.right)
5节点没有右子树,5 节点的 R=0 - 最后执行
return max(l, r) + 1
此时L=0,R=0,所以返回1 - 此时返回到调用节点2,节点2的 L=1
- 节点5没有左子树,执行
- 第六步:此时返回到调用节点2,节点2的 L=1,R=1
- 执行节点2上的,
return max(l, r) + 1
- 此时的 L=1,R=1所以 return 2
- 执行节点2上的,
- 第七步:此时返回到调用节点 1,1节点的 L=2
- 然后执行
r = maxDepth(root.right)
- 递归1节点的右节点
- 然后执行
- 第八步:递归节点3
- 节点3有左子树,继续执行
l = maxDepth(root.left)
- 递归节点6
- 节点3有左子树,继续执行
- 第九步:递归节点6
- 节点6没有左子树,执行
if root is None: return 0
,6节点的 L=0 - 然后执行
r = maxDepth(root.right)
6节点没有右子树,6节点的 R=0 - 最后执行
return max(l, r) + 1
此时L=0,R=0,所以返回1 - 此时返回到调用节点3,节点3的 L=1
- 节点6没有左子树,执行
- 第十步:此时出栈,返回到调用节点3,节点3的 L=1
- 节点7没有左子树,执行
if root is None: return 0
,7节点的 L=0 - 然后执行
r = maxDepth(root.right)
7节点没有右子树,7 节点的 R=0 - 最后执行
return max(l, r) + 1
此时L=0,R=0,所以返回1 - 此时返回到调用节点3,节点3的R=1
- 节点7没有左子树,执行
- 第十一步:此时返回到调用节点3,节点3的 L=1,R=1
- 执行节点3上的,
return max(l, r) + 1
- 此时的 L=1,R=1所以 return 2
- 执行节点3上的,
- 第十二步:此时返回到调用节点 1,1节点的 L=2,R=2
- 执行节点3上的,
return max(l, r) + 1
- 此时L=2,R=2,所以return 3
- 执行节点3上的,
第十三步:所以最终返回二叉树的高为 3
编辑 (opens new window)
上次更新: 2024/3/13 15:35:10