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

  输出

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

  
  2
  None