python-递归函数_实例分析_尾递归_递归函数python例子

递归函数

1. 递归函数

递归函数 : 自己调用自己的函数就是递归

递 : 去

归 : 回

一去一回就是递归

栈帧空间 : 每次调用函数时,在内存当中都会单独开辟一个空间,配合函数运行,这个空间叫做栈帧空间

def digui(n):
	print(n,"<===1===>")
	if n > 0:
		func(n-1)
	print(n,"<===2===>")
digui(5)    
1
2
3
4
5
6

代码解析 :

​ 去的过程 :

​ n = 5 print(5,"<=1=>") 5>0 条件成立 -> func(5-1) => func(4) 代码阻塞在第四行

​ n = 4 print(4,"<=1=>") 4>0 条件成立 -> func(4-1) => func(3) 代码阻塞在第四行

​ n = 3 print(3,"<=1=>") 3>0 条件成立 -> func(3-1) => func(2) 代码阻塞在第四行

​ n = 2 print(2,"<=1=>") 2>0 条件成立 -> func(2-1) => func(1) 代码阻塞在第四行

​ n = 1 print(1,"<=1=>") 1>0 条件成立 -> func(1-1) => func(0) 代码阻塞在第四行

​ n = 0 print(0,"<=1=>") 0>0 条件不成立 -> print(0,"<=2=>")

​ 当前这层空间代码已经执行结束

​ 此刻触发回的过程

​ 回的过程 :

​ n = 1 从上一次第四行的代码阻塞位置,继续向下执行 print(1,"<=2=>")

​ n = 2 从上一次第四行的代码阻塞位置,继续向下执行 print(2,"<=2=>")

​ n = 3 从上一次第四行的代码阻塞位置,继续向下执行 print(3,"<=2=>")

​ n = 4 从上一次第四行的代码阻塞位置,继续向下执行 print(4,"<=2=>")

​ n = 5 从上一次第四行的代码阻塞位置,继续向下执行 print(5,"<=2=>")

​ 到此,递归函数彻底执行结束

总结

1. 递归是一去一回的过程

   调用函数时,会开辟栈帧空间,函数执行结束之后,会释放栈帧空间

   递归实际上就是不停的开辟和释放空间的过程

   每次开辟栈帧空间,都是独立的一份,其中的资源不共享

2. 触发回的过程

   1. 当最后一层栈帧空间全部执行结束的时候,会触底反弹,回到上一层空间的调用处
   2. 遇到return ,会触底反弹,回到上一层空间的调用处

3. 写递归的要求

   写递归时,必须给予递归跳出的条件,否则会发生内存溢出,蓝屏死机的情况

   如果递归层数过多,不推荐使用递归

   官方说法 : 默认递归调用最多可以是1000层,实际996层左右

   def func():
   	func()
   func()     
   1
   2
   3

2. 递归练习

用递归计算n的阶乘

# 常规方法
def func(n):
	total = 1
	for i in range(n,0,-1):
		total *= i
	return total
res = func(5)
print(res)

# 递归写法
def func(n):
	if n <= 1:
		return 1
	return n*func(n-1)
res = func(5)
print(res)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

代码解析 :

​ return 后面的表达式,一定是先计算再返回

​ 去的过程 :

​ n = 5 return 5 * func(5-1) => 5 * func(4)

​ n = 4 return 4 * func(4-1) => 4 * func(3)

​ n = 3 return 3 * func(3-1) => 3 * func(2)

​ n = 2 return 2 * func(2-1) => 2 * func(1)

​ n = 1 return 1

​ 回的过程 :

​ n = 2 return 2 * func(2-1) => 2 * func(1) => 2 * 1

​ n = 3 return 3 * func(3-1) => 3 * func(2) => 3 * 2 * 1

​ n = 4 return 4 * func(4-1) => 4 * func(3) => 4 * 3 * 2 * 1

​ n = 5 return 5 * func(5-1) => 5 * func(4) => 5 * 4 * 3 * 2 * 1

​ return 5 * 4 * 3 * 2 * 1 => return 120

​ 额外解析 :

​ func(1) => 1

​ func(2) => 2 * func(1) => 2 * 1

​ func(3) => 3 * func(2) => 3 * 2 * 1

​ func(4) => 4 * func(3) => 4 * 3 * 2 * 1

​ func(5) => 5 * func(4) => 5 * 4 * 3 * 2 * 1

3. 尾递归

尾递归 : 自己调用自己 , 并且非表达式 , 计算的结果要在参数当中完成

注意 : 尾递归无论调用多少次函数 , 都只占用一份空间 , 但是目前cpython不支持

def func(n,endval):
	if n <= 1:
		return endval
	return func(n-1,endval*n)	
res = func(5,1)
print(res)
1
2
3
4
5
6

代码解析 :

​ 去的过程 :

​ n = 5 endval = 1 return func(5-1,endval*5) => func(4,1*5)

​ n = 4 endval = 1*5 return func(4-1,endval*4) => func(3,1*5*4)

​ n = 3 endval = 1*5*4 return func(3-1,endval*3) => func(2,1*5*4*3)

​ n = 2 endval = 1*5*4*3 return func(2-1,endval*2) => func(1,1*5*4*3*2)

​ n = 1 endval = 1*5*4*3*2 return 120

​ 回的过程 :

​ n = 2 return 120

​ n = 3 return 120

​ n = 4 return 120

​ n = 5 return 120

​ 因为最后一层空间的返回值就是第一层空间的返回值 , 所以在使用尾递归的时候

​ 不需要考虑回的逻辑过程 , 就能解决问题 , 推荐使用

优化代码 :

# 方法一
def func(n,endval=1):
	if n <= 1:
		return endval
	return func(n-1,endval*n)
res = func(5)
print(res)

# 方法二
"""为了避免用户乱传参数,把endval这个参数隐藏起来"""
def outer(n):
	def func(n,endval=1):
		if n <= 1:
			return endval
		return func(n-1,endval*n)
	return func(n)
res = outer(5)
print(res)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

递归计算斐波那契数列

1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 …

n = 3 => 2

n = 5 => 5

n = 6 => 8

# 设定数列长度为n 上一个 n-1 上上个 n-2
def feb(n):
	# 递归跳出的条件
	if n <= 2: # n == 1 or n == 2 => 1
		return 1
	return feb(n-1) + feb(n-2)
res = feb(5)
print(res)
1
2
3
4
5
6
7
8

代码解析 :

​ n = 5 return feb(5-1) + feb(5-2) => feb(4) + feb(3)

​ feb(4) -> 3 + feb(3) -> 2 => 5

​ feb(3) + feb(2) feb(2) + feb(1)

​ feb(2) + feb(1) + 1 1 + 1

​ 1 + 1 + 1

4. 练习

1.面试题

1. 下面这段代码打印多少?

def extendList(val,list=[]):
    list.append(val)
    return list

"""使用默认参数列表,内存中提前开辟好的列表 list = []"""
list1 = extendList(10)   
print(list1)  # [10]

"""用户给与的实参列表和默认列表是两个完全不同的列表"""
list2 = extendList(123, []) 
print(list2)  # 往实参列表中存入 123 => [123]

"""使用默认参数列表"""
list3 = extendList('a')   
print(list3)  # [10,'a'] 基于默认列表往里面存值

"""
默认参数: 
	当用户给与实参时,那么使用用户的实际参数
	如果用户没有给与实参,那么使用默认参数自带的值
	
此刻 list = [] 是内存中提前开辟好的一个空间
是 list 的默认值,每次都拿出这个默认值进行操作
默认值只有一个,不是多个默认值
"""
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

2. 可滑动的序列 自定义一个函数 根据参数n的值，变成对应个元素的容器 （zip）

"""
listvar = [1,2,3,4,5,6,7,8,9]
n = 2
listvar = [[1,2],[3,4],[5,6],[7,8]]
n = 3
listvar = [[1,2,3],[4,5,6],[7,8,9]]
n = 4
listvar = [[1,2,3,4],[5,6,7,8]]
"""

listvar = [1,2,3,4,5,6,7,8,9]

# 单独处理 n = 2
n = 2
listvar = [[1,2],[3,4],[5,6],[7,8]]
# 方法一
lst1 = [1,3,5,7,9]
lst2 = [2,4,6,8]
# 方法二
lst1 = listvar[0::2]
lst2 = listvar[1::2]
# 打印输出结果
it = zip(lst1,lst2)
lst = list(it)
print(lst)
# 方法三
lst = [listvar[i::2] for i in range(2)]
it = zip(*lst)
print(list(map(list,it)))

# 单独处理 n = 3
n = 3
listvar = [[1,2,3],[4,5,6],[7,8,9]]
# 方法一
lst1 = [1,4,7]
lst2 = [2,5,8]
lst3 = [3,6,9]
# 方法二
lst1 = [0::3]
lst2 = [1::3]
lst3 = [2::3]
# 打印输出结果
it = zip(lst1,lst2,lst3)
print(list(it))
# 方法三
lst = [listvar[i::3] for i in range(3)]
print(lst)

# 单独处理 n = 4
n = 4
listvar = [[1,2,3,4],[5,6,7,8]]
# 方法一
lst1 = [1,5]
lst2 = [2,6]
lst3 = [3,7]
lst4 = [4,8]
# 方法二
lst1 = [0::4]
lst2 = [1::4]
lst3 = [2::4]
lst4 = [3::4]
# 打印输出结果
it = zip(lst1,lst2,lst3,lst4)
print(list(it))
# 方法三
lst = [listvar[i::4] for i in range(4)]
it = zip(*lst)
print(list(map(list,it)))

# 普通方法
def func(n):
	return zip(*[listvar[i::n] for i in range(n)])
it = func(3)
print(list(map(list,it)))

# lambda 表达式
func = lambda n : zip(*[listvar[i::n] for i in range(n)])
print(list(map(list,func(3))))
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

2.递归题

1. 青蛙跳台阶

    	​	一只青蛙要跳上n层高的台阶
    一次能跳一级,也可以跳两级
    请问这只青蛙有多少种跳上这个n层高台阶的方法?
   1
   2
   3

"""
分析台阶高度和跳法的关系:
n = 1  => 1
1: 1
n = 2  => 2
2: 1 1 | 2
n = 3  => 3
3: 1 1 1 | 1 2 | 2 1
n = 4  => 5
5: 1 1 1 1 | 1 1 2 | 1 2 1 | 2 1 1 | 2 2
n = 5  => 8
8: 1 1 1 1 1 | 1 1 1 2 | 1 1 2 1 | 1 2 1 1 | 2 1 1 1 | 2 2 1 | 2 1 2 | 1 2 2

1 2 3 5 8 ... => 斐波那契数列
"""

def jump(n):
	if n == 1 or n == 2:
		return n
	return jump(n-1) + jump(n-2)
res = jump(5)
print(res)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

2. 递归反转字符串 “将14235 反转成53241”

# 方法一
strvar = "14235"
lth = len(strvar) # 5
def func(lth,lst=[]):
	if lth == 0:
		return lst
	res = strvar[lth-1]
	lst.append(res)    
	return func(lth-1)
lst = func(lth)
print(lst)
print("".join(lst))

# 改造升级版
def outer(lth):
	# 递归函数
	def func(lth,lst=[]):
        if lth == 0:
            return lst
        res = strvar[lth-1]
        lst.append(res)
        return func(lth-1)
	lst = func(lth)
	# 后期处理    
	return "".join(lst)
strvar = "14235"
lth = len(strvar) # 5
print(outer(lth))    

# 方法二
strvar = "12345"
def func(strvar):
	if len(strvar) == 1:
		return strvar
	return func(strvar[1:]) + strvar[0]
res = func(strvar)
print(res) # 54321

"""
代码解析:
递: 去的过程
return func(2345) + 1
return func(345) + 2
return func(45) + 3
return func(5) + 4
return 5

归: 回的过程
return 5 + 4
return 5 + 4 + 3
return 5 + 4 + 3 + 2
return 5 + 4 + 3 + 2 + 1
"""
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53