Python数据结构递归

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

使用递归的二进制搜索

我们使用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)
   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))

输出

当上述代码被执行时，它产生了以下结果 –