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
|
# ### 递归函数"""递归函数 : 自己调用自己的函数 , 叫做递归函数递 : 去归 : 回一去一回叫做递归"""def digui(n): print(n,"<==1==>") if n > 0: digui(n-1) print(n,"<==2==>")digui(5)"""# 去的过程n = 5 print(5,"<==1==>") if 5 > 0: digui(5-1) => digui(4) 代码阻塞在第12行n = 4 print(4,"<==1==>") if 4 > 0: digui(4-1) => digui(3) 代码阻塞在第12行n = 3 print(3,"<==1==>") if 3 > 0: digui(3-1) => digui(2) 代码阻塞在第12行n = 2 print(2,"<==1==>") if 2 > 0: digui(2-1) => digui(1) 代码阻塞在第12行n = 1 print(1,"<==1==>") if 1 > 0: digui(1-1) => digui(0) 代码阻塞在第12行n = 0 print(0,"<==1==>") if 0 > 0: 不成立 print(0,"<==2==>") 到此最后一层函数空间彻底执行完毕# 回的过程回到上一层函数空间 n = 1 代码在第12行的位置,继续往下执行 print(1,"<==2==>")回到上一层函数空间 n = 2 代码在第12行的位置,继续往下执行 print(2,"<==2==>")回到上一层函数空间 n = 3 代码在第12行的位置,继续往下执行 print(3,"<==2==>")回到上一层函数空间 n = 4 代码在第12行的位置,继续往下执行 print(4,"<==2==>")回到上一层函数空间 n = 5 代码在第12行的位置,继续往下执行 print(5,"<==2==>")到此递归函数执行结束..打印 543210012345""""""每次调用函数时,都要单独在内存当中开辟空间,叫做栈帧空间,以运行函数中的代码递归总结: (1)递归实际上是不停的开辟栈帧空间和释放栈帧空间的过程,开辟就是去的过程,释放就是回的过程 (2)递归什么时候触发归的过程: 1.当最后一层栈帧空间执行结束的时候,触发归的过程. 2.当遇到return返回值的时候终止当前函数,触发归的过程. (3)递归不能无限的去开辟空间,可能造成内存溢出,蓝屏死机的情况,所以一定要给予跳出的条件(如果递归的层数太大,不推荐使用) (4)开辟的一个个栈帧空间,数据是彼此独立不共享的."""# 递归不能不限开辟空间"""官方说法最大默认是1000层."""def deepfunc(): deepfunc()deepfunc() |
2. 递归练习
|
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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
|
# ### 1.使用递归实现任意数n的阶乘 # 普通实现# 5! =5 *4*3*2*1n = 5total = 1for i in range(n,0,-1): total *= iprint(total) # 120# 递归实现def jiecheng(n): if n <= 1: return 1 return jiecheng(n-1) * nprint(jiecheng(2))# jiecheng(1) => 1 # jiecheng(2) => jiecheng(1) * 2 => 1 * 2# jiecheng(3) => jiecheng(2) * 3 => 1 * 2 * 3# jiecheng(4) => jiecheng(3) * 4 => 1 * 2 * 3 * 4# jiecheng(5) => jiecheng(4) * 5 => 1 * 2 * 3 * 4 * 5print(jiecheng(5))"""代码解析:去的过程:n = 5 return jiecheng(n-1) * n => jiecheng(4) * 5n = 4 return jiecheng(n-1) * n => jiecheng(3) * 4n = 3 return jiecheng(n-1) * n => jiecheng(2) * 3n = 2 return jiecheng(n-1) * n => jiecheng(1) * 2n = 1 return 1回的过程:n = 2 return jiecheng(1) * 2 => 1 * 2n = 3 return jiecheng(2) * 3 => 1 * 2 * 3n = 4 return jiecheng(3) * 4 => 1 * 2 * 3 * 4n = 5 return jiecheng(4) * 5 => 1 * 2 * 3 * 4 * 5到此程序结束:返回 1 * 2 * 3 * 4 * 5"""print("<====================>")# ### 2. 使用尾递归来实现任意数的阶乘""" return 在哪调用,在哪返回 """"""自己调用自己,且返回时非运算表达式,只是函数本身""""""特点: 尾递归只开辟一个空间,不会无限的开辟,在一个空间里面去计算最后的结果进行返回,比较节省空间,有的解释器支持尾递归的调用特点 但是cpython解释器目前不支持写法: 所有运算的值都在函数的参数中计算完毕,最后返回运算的参数;"""def jiecheng(n,endval): if n <= 1: return endval return jiecheng(n-1 , n * endval)res = jiecheng(5,1) # 5*4*3*2*1print(res)"""代码解析:去的过程n = 5 ,endval = 1 return jiecheng(n-1 , n * endval) => jiecheng(4,5*1) => 5*1*4*3*2n = 4 ,endval = 5*1 return jiecheng(n-1 , n * endval) => jiecheng(3,5*1*4) => 5*1*4*3*2 n = 3 ,endval = 5*1*4 return jiecheng(n-1 , n * endval) => jiecheng(2,5*1*4*3) => 5*1*4*3*2 n = 2 ,endval = 5*1*4*3 return jiecheng(n-1 , n * endval) => jiecheng(1,5*1*4*3*2) => 5*1*4*3*2 n = 1 ,endval = 5*1*4*3*2 if n <= 1 成立 return endvalendval = 5*1*4*3*2 最下层空间的返回值 是 5*4*3*2*1 最上层接收到的返回值也是 5*4*3*2*1最下层和最上层返回的结果是一致的,所以对于尾递归来说,只需要考虑去的过程,无需考虑回的过程即可完成;"""# 优化代码1def jiecheng(n,endval=1): if n <= 1: return endval return jiecheng(n-1 , n * endval)res = jiecheng(5,100) # 5*4*3*2*1print(res,"<00000>")# 优化代码2 [把尾递归需要的参数值隐藏起来,避免篡改.]def outer(n): def jiecheng(n,endval=1): if n <= 1: return endval return jiecheng(n-1 , n * endval) return jiecheng(n,1)# 120print(outer(5))# 优化代码3(扩展)# 闭包实现def outer(n): endval = 1 def jiecheng(n): nonlocal endval if n <= 1: return endval endval *= n return jiecheng(n-1) return jiechengfunc = outer(5)print(func(5),"<===111==>")print("<================>")# ### 3.使用递归来完成斐波那契数列""" 1 1 2 3 5 8 13 21 34 ... """def feib(n): if n == 1 or n == 2: return 1 # 上一个结果 + 上上个结果 return feib(n-1) + feib(n-2)print(feib(5))"""# 代码解析:n = 5 feib(5) => 3 + 2 => return 5 feib(4) + feib(3) feib(3)+feib(2) feib(2)+feib(1) => 1 + 1 => 2feib(2)+feib(1)+feib(2) => 1 + 1 + 1 => 3 """ |
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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
|
# (选做)# 1.可滑动的序列 自定义一个函数 根据参数n的值 , 变成对应个元素的容器 （zip）"""listvar = [1,2,3,4,5,6,7,8,9]n = 2listvar = [[1,2],[3,4],[5,6],[7,8]]n = 3listvar = [[1,2,3],[4,5,6],[7,8,9]]n = 4listvar = [[1,2,3,4],[5,6,7,8]]""""""lst1 = [1,3,5,7,9]lst2 = [2,4,6,8]zip(lst1,lst2)"""listvar = [1,2,3,4,5,6,7,8,9]n = 2lst1 = [1,3,5,7,9]lst2 = [2,4,6,8]# lst1 = listvar[0::2] <=> [1,3,5,7,9]# lst2 = listvar[1::2] <=> [2,4,6,8]print(lst2,"1111")print(list( zip(lst1,lst2) ))n = 3lst1 = [1,4,7]lst2 = [2,5,8]lst3 = [3,6,9]# lst1 = listvar[0::3] <=> [1,4,7]# lst2 = listvar[1::3] <=> [2,5,8]# lst3 = listvar[2::3] <=> [3,6,9]print(lst1,"2222")print(list( zip(lst1,lst2,lst3) ))n = 4lst1 = [1,5]lst2 = [2,6]lst3 = [3,7]lst4 = [4,8]# lst1 = listvar[0::4] <=> [1,5,9]# lst2 = listvar[1::4] <=> [2,6]# lst3 = listvar[2::4] <=> [3,7]# lst4 = listvar[3::4] <=> [4,8]print(lst1,"3333")print(list( zip(lst1,lst2,lst3,lst4) ))print("<=============>")n = 3lst = [ listvar[i::n] for i in range(n) ]print(lst) # [[1, 4, 7], [2, 5, 8], [3, 6, 9]]# zip(*lst) => zip([1,4,7],[2,5,8],[3,6,9])it = zip(*lst)print(list(it))func = lambda n : zip( *[ listvar[i::n] for i in range(n) ] )it = func(2)# 把里面的元组强转成列表print(list(map(list,it)))# 2.青蛙跳台阶 (递归实现)'''一只青蛙要跳上n层高的台阶一次能跳一级,也可以跳两级请问这只青蛙有多少种跳上这个n层高台阶的方法?n = 1 1 => 1n = 2 2 => 1 1 | 2n = 3 3 => 1 1 1 | 1 2 | 2 1 n = 4 5 => 1 1 1 1 | 1 2 1 | 2 1 1 | 1 1 2 | 2 2n = 5 8 => 1 1 1 1 1 | 1 1 1 2 |2 1 1 1 | 1 2 1 1 | 1 1 2 1 | 2 2 1 | 1 2 2 | 2 1 2 '''def func(n): if n == 1 or n == 2: return n return func(n-1) + func(n-2)print(func(5))# 3.递归反转字符串 "将14235 反转成53241" (递归实现)# 把后面的字符往前挪动 方法一strvar = "14235"# lst.append(5)# lst.append(3)# lst.append(2)# lst.append(4)# lst.append(1)# lth = 字符串的总长度 lst 要插入的列表def func(lth,lst=[]): if lth == 0: return lst res = strvar[lth-1] lst.append(res) return func(lth-1)lth = len(strvar)lst = func(lth)print(lst) # ['5', '3', '2', '4', '1']print("".join(lst))# 简写def func(lth,lst=[]): if lth == 0: return "".join(lst) res = strvar[lth-1] lst.append(res) return func(lth-1)print(func(lth))# 把前面的字符往后挪动 方法二strvar = "14235"def func(strvar): if len(strvar) == 1: return strvar return func(strvar[1:])+strvar[0]res = func(strvar)print(res)"""递:return func(4235) + 1return func(235) + 4return func(35) + 2return func(5) + 3return 5归:return func(5) + 3 => 5 + 3return func(35) + 2 => 5 + 3 + 2return func(235) + 4 => 5 + 3 + 2 + 4return func(4235) + 1 => 5 + 3 + 2 + 4 + 1return 5 + 3 + 2 + 4 + 1"""# 4.斐波那契数列用尾递归实现a,b = 0,1i = 0n = 5while i < n: print(b) a,b = b,a+b i +=1a,b = 0,1n = 5while n > 0: print(b) a,b = b,a+b n -= 1print("<==============>")def func(n,a=0,b=1): if n == 1: return b return func(n-1,b,a+b)print(func(6)) |
总结
本篇文章就到这里了，希望能够给你带来帮助，也希望您能够多多关注服务器之家的更多内容!
原文链接：https://blog.csdn.net/weixin_46818279/article/details/121186680
