python函數遞歸調用的實現
引入
函數既可以嵌套定義也可以嵌套調用。嵌套定義指的是在定義一個函數時在該函數內部定義另一個函數;嵌套調用指的是在調用一個函數的過程中函數內部有調用另一個函數。而函數的遞歸調用指的是在調用一個函數的過程中又直接或者間接的調用該函數本身。
函數遞歸介紹
函數遞歸就是函數的遞歸調用,是函數嵌套調用的一種特殊形式,具體就是指在調用一個函數的過程中直接或者間接的調用到本身,遞歸的本質就是循環(huán)做重復的事情。
在調用func的過程中又調用func,這就是直接調用函數本身;
在調用func的過程中調用foo,而在調用foo的過程中又調用func,這就是間接調用func本身。
通過上面的分析,兩種情況下的函數遞歸調用都是一個無限循環(huán)的過程,Python為了防止函數遞歸進入無限循環(huán)對函數遞歸調用的深度做了限制,一旦超出限制就會拋出異常。
def foo(): print('foo') func() def func(): print('func') foo() func() ''' 程序運行結果: RecursionError: maximum recursion depth exceeded while calling a Python object(超過最大遞歸深度) '''
因此為了避免函數遞歸調用報錯,就必須在滿足某中條件的情況下結束對函數的遞歸調用。
def foo(n): if n == 1: print('遞歸結束') return else: foo(n-1) foo(2)
函數遞歸原理及使用
通過一個簡單的小學數學題說明遞歸的原理及使用。
小一比小二多一個蘋果,小二比小三多一個蘋果,小三比小四多一個蘋果,小四有兩個蘋果,問小一有幾個蘋果?
這個題目非常簡單,解答思路如下:
要想知道小一的蘋果數量就需要知道小二的蘋果數量,而小二的蘋果數量又取決于小三,小三的蘋果數量又是基于小四的蘋果數量: app_num(1) = app_num(2) + 1 app_num(2) = app_num(3) + 1 app_num(3) = app_num(4) + 1 app_num(4) = 2 因此可以總結出下面的結論: app_num(4) = 2 app_num(x) = app_num(x+1) + 1
很明顯是一個重復調用同一種方法的過程,只是參數不同,也就是一個遞歸的過程,通過上面的分析可以將遞歸過程分為兩個階段 - 回溯和遞推。
回溯階段:想要計算小一(x=1)的蘋果數量就需要回溯得到小二(x+1)的蘋果,以此類推,直到得到小四的蘋果個數,此時app_num(4)已知,就無需再向前回溯。
遞推階段:從小四的蘋果數量可以推算出小三的蘋果數量,從小三的蘋果數量可以推算出小二的,以此類推,一直推算出小一的蘋果數量為止,遞歸結束。需要注意的是,遞歸一定要有結束條件,這里當x=1就是結束條件。
遞歸的本質就是在做重復的事情,理論上說遞歸可以解決的問題循環(huán)也都可以解決,只不過是在某種情況下使用遞歸更容易實現。
def apple_num(x): if x == 4: # 結束遞歸的條件 return 2 return apple_num(x+1) + 1 apple_num1 = apple_num(1) print(apple_num1) # 5
Practice
一個嵌套多層的列表要求打印出所有的元素。
list1 = [[[1, 2], [3, 4], [5, [6, 7], [8, 9, 10], 11, 12], 13]] def func(items): for elements in items: if type(elements) is list: func(elements) else: print(elements) func(list1)
有一個按照從小到大順序排列的數字列表,需要從該數字列表中找到我們想要的數字,如何更高效?
# 使用二分法:先取出列表的中間位置的值,與需要的數字進行比較,如果中間位置的值大于需要的值,那么就在中間值的左側2 進行比較,如果小于,那么就在中間值的右側進行比較,如果剛好等于,就輸出值。然后對上述步驟進行循環(huán) list1 = [0,2,5,7,9,11,34] find_num = 2 def func(find_num,list1): # 輸出每次切分后生成的list1 print(list1) mid_index = len(list1) // 2 if find_num > list1[mid_index]: list1 = list1[mid_index+1:] func(find_num,list1) elif find_num < list1[mid_index]: list1 = list1[:mid_index] func(find_num,list1) elif find_num == list1[mid_index]: print(f'找到了{list1[mid_index]},索引為{mid_index}') elif len(list1) == 0: print('不存在這個值') return func(find_num,list1)
到此這篇關于python函數遞歸調用的實現的文章就介紹到這了,更多相關python函數遞歸調用內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家!
相關文章
關于Python中request發(fā)送post請求傳遞json參數的問題
這篇文章主要介紹了Python中request發(fā)送post請求傳遞json參數的問題,在Python中需要傳遞dict參數,利用json.dumps將dict轉為json格式用post方法發(fā)起請求,感興趣的朋友跟隨小編一起看看吧2022-08-08Python3實現監(jiān)控新型冠狀病毒肺炎疫情的示例代碼
這篇文章主要介紹了Python3實現監(jiān)控新型冠狀病毒肺炎疫情的示例代碼,代碼簡單易懂,非常不錯,具有一定的參考借鑒價值,需要的朋友可以參考下2020-02-02