1. 遞歸函數(shù)
|
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
|
# ### 遞歸函數(shù)"""遞歸函數(shù) : 自己調用自己的函數(shù) , 叫做遞歸函數(shù)遞 : 去歸 : 回一去一回叫做遞歸"""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==>") 到此最后一層函數(shù)空間徹底執(zhí)行完畢# 回的過程回到上一層函數(shù)空間 n = 1 代碼在第12行的位置,繼續(xù)往下執(zhí)行 print(1,"<==2==>")回到上一層函數(shù)空間 n = 2 代碼在第12行的位置,繼續(xù)往下執(zhí)行 print(2,"<==2==>")回到上一層函數(shù)空間 n = 3 代碼在第12行的位置,繼續(xù)往下執(zhí)行 print(3,"<==2==>")回到上一層函數(shù)空間 n = 4 代碼在第12行的位置,繼續(xù)往下執(zhí)行 print(4,"<==2==>")回到上一層函數(shù)空間 n = 5 代碼在第12行的位置,繼續(xù)往下執(zhí)行 print(5,"<==2==>")到此遞歸函數(shù)執(zhí)行結束..打印 543210012345""""""每次調用函數(shù)時,都要單獨在內存當中開辟空間,叫做棧幀空間,以運行函數(shù)中的代碼遞歸總結: (1)遞歸實際上是不停的開辟棧幀空間和釋放棧幀空間的過程,開辟就是去的過程,釋放就是回的過程 (2)遞歸什么時候觸發(fā)歸的過程: 1.當最后一層棧幀空間執(zhí)行結束的時候,觸發(fā)歸的過程. 2.當遇到return返回值的時候終止當前函數(shù),觸發(fā)歸的過程. (3)遞歸不能無限的去開辟空間,可能造成內存溢出,藍屏死機的情況,所以一定要給予跳出的條件(如果遞歸的層數(shù)太大,不推薦使用) (4)開辟的一個個棧幀空間,數(shù)據(jù)是彼此獨立不共享的."""# 遞歸不能不限開辟空間"""官方說法最大默認是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.使用遞歸實現(xiàn)任意數(shù)n的階乘 # 普通實現(xiàn)# 5! =5 *4*3*2*1n = 5total = 1for i in range(n,0,-1): total *= iprint(total) # 120# 遞歸實現(xiàn)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. 使用尾遞歸來實現(xiàn)任意數(shù)的階乘""" return 在哪調用,在哪返回 """"""自己調用自己,且返回時非運算表達式,只是函數(shù)本身""""""特點: 尾遞歸只開辟一個空間,不會無限的開辟,在一個空間里面去計算最后的結果進行返回,比較節(jié)省空間,有的解釋器支持尾遞歸的調用特點 但是cpython解釋器目前不支持寫法: 所有運算的值都在函數(shù)的參數(shù)中計算完畢,最后返回運算的參數(shù);"""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最下層和最上層返回的結果是一致的,所以對于尾遞歸來說,只需要考慮去的過程,無需考慮回的過程即可完成;"""# 優(yōu)化代碼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>")# 優(yōu)化代碼2 [把尾遞歸需要的參數(shù)值隱藏起來,避免篡改.]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))# 優(yōu)化代碼3(擴展)# 閉包實現(xiàn)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.使用遞歸來完成斐波那契數(shù)列""" 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.可滑動的序列 自定義一個函數(shù) 根據(jù)參數(shù)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.青蛙跳臺階 (遞歸實現(xiàn))'''一只青蛙要跳上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" (遞歸實現(xiàn))# 把后面的字符往前挪動 方法一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.斐波那契數(shù)列用尾遞歸實現(xiàn)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
