递归

递归允许函数调用自身。 固定的代码步骤一次又一次地执行新值。 我们还必须设置标准来决定递归调用何时结束。 在下面的例子中，我们看到了二进制搜索的递归方法。 我们采用排序列表并将其索引范围作为递归函数的输入。

使用递归进行二进制搜索

我们使用python实现二进制搜索算法，如下所示。 我们使用一个有序的项目列表，并设计一个递归函数，以带有开始和结束索引作为输入的列表。 然后二进制搜索函数调用自己直到找到搜索到的项目或者在列表中得出它的缺席。

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))

执行上述代码时，会产生以下结果 -

2
None