引入

函數(shù)既可以嵌套定義也可以嵌套調(diào)用。嵌套定義指的是在定義一個(gè)函數(shù)時(shí)在該函數(shù)內(nèi)部定義另一個(gè)函數(shù)；嵌套調(diào)用指的是在調(diào)用一個(gè)函數(shù)的過(guò)程中函數(shù)內(nèi)部有調(diào)用另一個(gè)函數(shù)。而函數(shù)的遞歸調(diào)用指的是在調(diào)用一個(gè)函數(shù)的過(guò)程中又直接或者間接的調(diào)用該函數(shù)本身。

函數(shù)遞歸介紹

函數(shù)遞歸就是函數(shù)的遞歸調(diào)用，是函數(shù)嵌套調(diào)用的一種特殊形式，具體就是指在調(diào)用一個(gè)函數(shù)的過(guò)程中直接或者間接的調(diào)用到本身，遞歸的本質(zhì)就是循環(huán)做重復(fù)的事情。

在調(diào)用func的過(guò)程中又調(diào)用func，這就是直接調(diào)用函數(shù)本身；

在調(diào)用func的過(guò)程中調(diào)用foo，而在調(diào)用foo的過(guò)程中又調(diào)用func，這就是間接調(diào)用func本身。

通過(guò)上面的分析，兩種情況下的函數(shù)遞歸調(diào)用都是一個(gè)無(wú)限循環(huán)的過(guò)程，Python為了防止函數(shù)遞歸進(jìn)入無(wú)限循環(huán)對(duì)函數(shù)遞歸調(diào)用的深度做了限制，一旦超出限制就會(huì)拋出異常。

def foo():
    print('foo')
    func()
def func():
    print('func')
    foo()
func()
'''
程序運(yùn)行結(jié)果：
RecursionError: maximum recursion depth exceeded while calling a Python object(超過(guò)最大遞歸深度)
'''

因此為了避免函數(shù)遞歸調(diào)用報(bào)錯(cuò)，就必須在滿足某中條件的情況下結(jié)束對(duì)函數(shù)的遞歸調(diào)用。

def foo(n):
    if n == 1:
        print('遞歸結(jié)束')
        return
    else:
        foo(n-1)
foo(2)

函數(shù)遞歸原理及使用

通過(guò)一個(gè)簡(jiǎn)單的小學(xué)數(shù)學(xué)題說(shuō)明遞歸的原理及使用。

小一比小二多一個(gè)蘋果，小二比小三多一個(gè)蘋果，小三比小四多一個(gè)蘋果，小四有兩個(gè)蘋果，問小一有幾個(gè)蘋果？

這個(gè)題目非常簡(jiǎn)單，解答思路如下：

要想知道小一的蘋果數(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

很明顯是一個(gè)重復(fù)調(diào)用同一種方法的過(guò)程，只是參數(shù)不同，也就是一個(gè)遞歸的過(guò)程，通過(guò)上面的分析可以將遞歸過(guò)程分為兩個(gè)階段 - 回溯和遞推。

回溯階段：想要計(jì)算小一(x=1)的蘋果數(shù)量就需要回溯得到小二(x+1)的蘋果，以此類推，直到得到小四的蘋果個(gè)數(shù)，此時(shí)app_num(4)已知，就無(wú)需再向前回溯。

遞推階段：從小四的蘋果數(shù)量可以推算出小三的蘋果數(shù)量，從小三的蘋果數(shù)量可以推算出小二的，以此類推，一直推算出小一的蘋果數(shù)量為止，遞歸結(jié)束。需要注意的是，遞歸一定要有結(jié)束條件，這里當(dāng)x=1就是結(jié)束條件。

遞歸的本質(zhì)就是在做重復(fù)的事情，理論上說(shuō)遞歸可以解決的問題循環(huán)也都可以解決，只不過(guò)是在某種情況下使用遞歸更容易實(shí)現(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

一個(gè)嵌套多層的列表要求打印出所有的元素。

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)

有一個(gè)按照從小到大順序排列的數(shù)字列表，需要從該數(shù)字列表中找到我們想要的數(shù)字，如何更高效？

# 使用二分法：先取出列表的中間位置的值，與需要的數(shù)字進(jìn)行比較，如果中間位置的值大于需要的值，那么就在中間值的左側(cè)2 進(jìn)行比較，如果小于，那么就在中間值的右側(cè)進(jìn)行比較，如果剛好等于，就輸出值。然后對(duì)上述步驟進(jìn)行循環(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'找到了{(lán)list1[mid_index]},索引為{mid_index}')
    elif len(list1)  == 0:
        print('不存在這個(gè)值')
        return
func(find_num,list1)

到此這篇關(guān)于python函數(shù)遞歸調(diào)用的實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)python函數(shù)遞歸調(diào)用內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論