Python Data Structure 简明教程

Python - Recursion

递归允许函数调用自身。一段固定代码步骤会不断地针对新值执行。我们还必须设定用于确定递归调用何时结束的标准。在下面的示例中,我们将看到二分搜索的递归方法。我们选取一个有序列表,并将其索引范围作为输入提供给递归函数。

Binary Search using Recursion

我们使用 Python 实现了二分搜索算法,如下所示。我们使用一个有序项列表,并设计了一个递归函数,以列表以及起始索引和结束索引作为输入。然后,二分搜索函数将不断调用自己,直到找到被搜索的项目,或推断出它不在列表中。

Example

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

Output

执行上述代码后,将生成以下结果 −

2
None