函數遞歸與生成式
- 2021 年 8 月 12 日
- 筆記
一、函數遞歸：
1.定義：函數不僅可以嵌套定義，還可以嵌套調用，即在調用一個函數的過程中，函數內部又調用另一個函數，而函數的遞歸調用指的是在調用一個函數的過程中又直接或間接地調用該函數本身
在調用f1的過程中，又調用f1，這就是直接調用函數f1本身
def f1(): print('from f1') f1() f1()
在調用f1的過程中，又調用f2，而在調用f2的過程中又調用f1，這就是間接調用函數f1本身
def f1():
print('from f1')
f2()
def f2():
print('from f2')
f1()
f1()從上圖可以看出，兩種情況下的遞歸調用都是一個無限循環的過程，但在python對函數的遞歸調用的深度做了限制，因而並不會像大家所想的那樣進入無限循環，會拋出異常，要避免出現這種情況，就必須讓遞歸調用在滿足某個特定條件下終止。
#1. 可以使用sys.getrecursionlimit()去查看遞歸深度，默認值為1000，雖然可以使用 sys.setrecursionlimit()去設定該值，但仍受限於主機操作系統棧大小的限制 #2. python不是一門函數式編程語言，無法對遞歸進行尾遞歸優化。
二、回溯與遞推
某公司四個員工坐在一起，問第四個人薪水，他說比第三個人多1000，問第三個人薪水，第他說比第二個人多1000，問第二個人薪水，他說比第一個人多1000，最後第一人說自己每月5000，請問第四個人的薪水是多少？
思路解析：
要知道第四個人的月薪，就必須知道第三個人的，第三個人的又取決於第二個人的，第二個人的又取決於第一個人的，而且每一個員工都比前一個多一千，數學表達式即：
salary(4)=salary(3)+1000 salary(3)=salary(2)+1000 salary(2)=salary(1)+1000 salary(1)=5000 總結為： salary(n)=salary(n-1)+1000 (n>1) salary(1)=5000 (n=1)
很明顯這是一個遞歸的過程，可以將該過程分為兩個階段：回溯和遞推。
在回溯階段，要求第n個員工的薪水，需要回溯得到(n-1)個員工的薪水，以此類推，直到得到第一個員工的薪水，此時，salary(1)已知，因而不必再向前回溯了。然後進入遞推階段：從第一個員工的薪水可以推算出第二個員工的薪水(6000)，從第二個員工的薪水可以推算出第三個員工的薪水(7000)，以此類推，一直推算出第第四個員工的薪水(8000)為止，遞歸結束。需要注意的一點是，遞歸一定要有一個結束條件，這裡n=1就是結束條件。
def salary(n): if n==1: return 5000 return salary(n-1)+1000 s=salary(4) print(s)
在未滿足n\=\=1的條件時，一直進行遞歸調用，即一直回溯，見圖4.3的左半部分。而在滿足n\=\=1的條件時，終止遞歸調用，即結束回溯，從而進入遞推階段，依次推導直到得到最終的結果。
遞歸本質就是在做重複的事情，所以理論上遞歸可以解決的問題循環也都可以解決，只不過在某些情況下，使用遞歸會更容易實現，比如有一個嵌套多層的列表，要求打印出所有的元素，代碼實現如下
# l = [1,[2,[3,[4,[5,[6,[7,[8,[9]]]]]]]]] # # def foo(l): # for item in l: # if type(item) is not list: # print(item) # else: # foo(item) # # # foo(l)
使用遞歸，我們只需要分析出要重複執行的代碼邏輯，然後提取進入下一次遞歸調用的條件或者說遞歸結束的條件即可，代碼實現起來簡潔清晰
三、生成式
# 一 列表生成式 # l = [] # for i in range(1, 6): # if i > 3: # l.append(i) # print(l) # l = [i for i in range(1,6)] # l = [i**2 for i in range(1,6)] # l = [i for i in range(1,6) if i > 3] # print(l) # names = ['liusir_dsb', 'housir_dsb', 'egon', 'wusir_dsb'] # res = [name for name in names if name.endswith('dsb')] # print(res) # 二 字典生成式 # res = {k:v for k,v in [('name', 'egon'), ('age', 18)]} # res = {i:i for i in range(5)} # print(res) # 三 集合生成式 # res = {i for i in range(5)} # print(res,type(res)) # 四 生成器表達式 # l = [i for i in range(1,6)] # g = (i for i in range(1,6)) # print(g) # # print(next(g)) # print(next(g)) # print(next(g)) # print(next(g)) # print(next(g)) # print(next(g)) with open('a.txt',mode='rt',encoding='utf-8') as f: # res = f.read() # print(len(res)) # res = 0 # for line in f: # res += len(line) # res = sum([len(line) for line in f]) # res = sum((len(line) for line in f)) res = sum(len(line) for line in f) print(res)
四、匿名函數
1.匿名函數只能用一次
def foo(x, y):
return x + y
2.調用匿名函數的方式：
# 調用匿名函數方式一 # f=lambda x,y:x+y # print(f(1,2)) # 調用匿名函數方式二 # res = (lambda x,y:x+y)(1,2) # print(res)
3.匿名函數真正的用途是與其他函數配合使用
salaries = { 'axx': 30000, 'bxx': 3000, 'cxx': 2000, 'egon': 1000, 'zxx': 500 } # print(max([33,44,11,99])) # def func(k): # return salaries[k] # print(max(salaries,key=func)) # print(max(salaries,key=lambda k:salaries[k])) # print(min(salaries,key=lambda k:salaries[k])) print(sorted(salaries,key=lambda k:salaries[k])) print(sorted(salaries,key=lambda k:salaries[k],reverse=True))
