python 遞歸

遞歸允許函數(shù)自行調(diào)用。修復代碼的步驟會一次又一次地執(zhí)行新值。我們還必須設置判斷遞歸調(diào)用何時結(jié)束的標準。在下面的例子中，我們看到了二進制搜索的遞歸方法。我們采用一個排序列表，并將其索引范圍作為遞歸函數(shù)的輸入。

使用遞歸進行二進制搜索

我們使用python實現(xiàn)二進制搜索算法，如下所示。我們使用有序的項目列表，并設計一個遞歸函數(shù)，將起始索引和結(jié)束索引作為輸入列表。然后二進制搜索函數(shù)自行調(diào)用，直到找到搜索到的項目或在列表中結(jié)束它的缺席。

def bsearch(list, idx0, idxn, val):

    if (idxn < idx0):
        return none
    else:
        midval = idx0 + ((idxn - idx0) // 2)
# compare the search item with middle most value

        if list[midval] > val:
            return bsearch(list, idx0, midval-1,val)
        elif list[midval] < val:
            return bsearch(list, midval+1, idxn, val)
        else:
            return midval

list = [8,11,24,56,88,131]
print(bsearch(list, 0, 5, 24))
print(bsearch(list, 0, 5, 51))

當上面的代碼被執(zhí)行時，它會產(chǎn)生以下結(jié)果 -

2
none