python 遞歸

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

使用遞歸進(jìn)行二進(jìn)制搜索

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

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

2
none