Python Data Structure 简明教程
Python - Recursion
递归允许函数调用自身。一段固定代码步骤会不断地针对新值执行。我们还必须设定用于确定递归调用何时结束的标准。在下面的示例中，我们将看到二分搜索的递归方法。我们选取一个有序列表，并将其索引范围作为输入提供给递归函数。
Recursion allows a function to call itself. Fixed steps of code get executed again and again for new values. We also have to set criteria for deciding when the recursive call ends. In the below example we see a recursive approach to the binary search. We take a sorted list and give its index range as input to the recursive function.
Binary Search using Recursion
我们使用 Python 实现了二分搜索算法，如下所示。我们使用一个有序项列表，并设计了一个递归函数，以列表以及起始索引和结束索引作为输入。然后，二分搜索函数将不断调用自己，直到找到被搜索的项目，或推断出它不在列表中。
We implement the algorithm of binary search using python as shown below. We use an ordered list of items and design a recursive function to take in the list along with starting and ending index as input. Then, the binary search function calls itself till find the searched item or concludes about its absence in the list.
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))