微信公眾號搜索【程序媛小莊】福荸，關(guān)注半路出家的程序媛如何靠python開發(fā)養(yǎng)家糊口~
引入
函數(shù)既可以嵌套定義也可以嵌套調(diào)用表箭。嵌套定義指的是在定義一個函數(shù)時在該函數(shù)內(nèi)部定義另一個函數(shù)；嵌套調(diào)用指的是在調(diào)用一個函數(shù)的過程中函數(shù)內(nèi)部有調(diào)用另一個函數(shù)。而函數(shù)的遞歸調(diào)用指的是在調(diào)用一個函數(shù)的過程中又直接或者間接的調(diào)用該函數(shù)本身比肄。
函數(shù)遞歸介紹
函數(shù)遞歸就是函數(shù)的遞歸調(diào)用，是函數(shù)嵌套調(diào)用的一種特殊形式囊陡，具體就是指在調(diào)用一個函數(shù)的過程中直接或者間接的調(diào)用到本身芳绩，遞歸的本質(zhì)就是循環(huán)做重復(fù)的事情。
在調(diào)用func的過程中又調(diào)用func撞反，這就是直接調(diào)用函數(shù)本身妥色；
在調(diào)用func的過程中調(diào)用foo，而在調(diào)用foo的過程中又調(diào)用func遏片，這就是間接調(diào)用func本身嘹害。
通過上面的分析，兩種情況下的函數(shù)遞歸調(diào)用都是一個無限循環(huán)的過程吮便，Python為了防止函數(shù)遞歸進入無限循環(huán)對函數(shù)遞歸調(diào)用的深度做了限制笔呀，一旦超出限制就會拋出異常。
def foo():
print('foo')
func()
def func():
print('func')
foo()
func()
'''
程序運行結(jié)果：
RecursionError: maximum recursion depth exceeded while calling a Python object(超過最大遞歸深度)
'''
因此為了避免函數(shù)遞歸調(diào)用報錯线衫，就必須在滿足某中條件的情況下結(jié)束對函數(shù)的遞歸調(diào)用凿可。
def foo(n):
if n == 1:
print('遞歸結(jié)束')
return
else:
foo(n-1)
foo(2)
函數(shù)遞歸原理及使用
通過一個簡單的小學(xué)數(shù)學(xué)題說明遞歸的原理及使用。
小一比小二多一個蘋果，小二比小三多一個蘋果枯跑，小三比小四多一個蘋果惨驶，小四有兩個蘋果，問小一有幾個蘋果敛助？
這個題目非常簡單粗卜，解答思路如下：
要想知道小一的蘋果數(shù)量就需要知道小二的蘋果數(shù)量，而小二的蘋果數(shù)量又取決于小三纳击，小三的蘋果數(shù)量又是基于小四的蘋果數(shù)量：
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
因此可以總結(jié)出下面的結(jié)論：
app_num(4) = 2
app_num(x) = app_num(x+1) + 1
很明顯是一個重復(fù)調(diào)用同一種方法的過程续扔，只是參數(shù)不同，也就是一個遞歸的過程焕数，通過上面的分析可以將遞歸過程分為兩個階段 - 回溯和遞推纱昧。
回溯階段：想要計算小一(x=1)的蘋果數(shù)量就需要回溯得到小二(x+1)的蘋果，以此類推堡赔，直到得到小四的蘋果個數(shù)识脆，此時app_num(4)已知，就無需再向前回溯善已。
遞推階段：從小四的蘋果數(shù)量可以推算出小三的蘋果數(shù)量灼捂，從小三的蘋果數(shù)量可以推算出小二的，以此類推换团，一直推算出小一的蘋果數(shù)量為止悉稠，遞歸結(jié)束。需要注意的是艘包，遞歸一定要有結(jié)束條件的猛，這里當(dāng)x=1就是結(jié)束條件。
遞歸的本質(zhì)就是在做重復(fù)的事情辑甜，理論上說遞歸可以解決的問題循環(huán)也都可以解決衰絮，只不過是在某種情況下使用遞歸更容易實現(xiàn)。
def apple_num(x):
if x == 4: # 結(jié)束遞歸的條件
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)
有一個按照從小到大順序排列的數(shù)字列表，需要從該數(shù)字列表中找到我們想要的數(shù)字胡诗，如何更高效邓线？
# 使用二分法：先取出列表的中間位置的值，與需要的數(shù)字進行比較煌恢，如果中間位置的值大于需要的值骇陈，那么就在中間值的左側(cè)2 進行比較，如果小于瑰抵，那么就在中間值的右側(cè)進行比較你雌，如果剛好等于，就輸出值。然后對上述步驟進行循環(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)
