二分法查找的递归实现（python）
什么是递归
一尺之棰，日取其半，万世不竭 《庄子·天下》
这是《庄子》一书中的一个故事：一根一尺长的木棍，每次取其一半，那永远也取不完。这其中就有递归的思想。
另一个递归的故事：
从前山里有个庙，庙里有个老和尚,老和尚在讲：从前山里有个庙··· ···
如果不规定结束条件的话，递归将会是无穷无尽的。
递归是一种经典算法，它将一个复杂（庞大）问题分解为一个或若干个更简单（规模更小）的同类问题，直到问题被细分的足够简单，我们就给出结果，退出递归。
二分法的递归方案
调整二分法查询 binary_search 的参数：
- theList，要查找的数组，要求已排序。
- left
- right，指定在 theList 中查找的范围
- target，要查找的目标值。
由于我们会递归查找，为了保证最终返回的索引是 theList 的索引，而非其子列表的索引，所以我们将 theList、left、right 都作为函数的参数。
新版本的 binary_search 只做 4 种操作：
- 不存在合理的查找范围，返回 None。
- 计算中点，如果中点等于 target，返回中点索引。
- 如果 target 在中点左侧，调用 binary_search，在中点左侧继续查找。
- 如果 target 在中点右侧，调用 binary_search，在中点右侧继续查找。
其中橙色位置是 binary search 的查找范围。
如果将所有的 binary_search 调用关系都展开，看到的是上图所示情况。橙色越深，即越深层调用 binary_search。
代码
def binary_search(theList, left, right, target):
if(left > right):
return None
midIndex = int((left + right)/2)
midValue = theList[midIndex]
if midValue == target:
return midIndex
if target > midValue:
return binary_search(theList, midIndex + 1, right, target)
return binary_search(theList, left, midIndex - 1, target)阅读递归版本的 binary_search, 只需要记住 binary_search 可以返回指定区域内 target 的查找结果，要么为 None，要么是 target 的索引。
递归的几个重要知识点
1. 终止条件
如果没有设置正确的递归的终止条件，那么递归会无限的执行下去，一直到 Python 的函数调用栈溢出。一些递归算法实现的bug，只要就来源于此。
2. 尾调用
每当函数调用深入一层，调用栈上就会增加一层栈数据，大规模递归调用，会造成 Python 抛出异常。对于其他如 C 语言，则会直接引起操作系统内存耗尽，系统崩溃。这也意味着，递归调用的调用深度有限制，无法处理太大的数据集合。
大多数现代编译器都有尾调用优化，直接使用 return 递归函数 ，编译器会直接用下一层递归调用的调用栈覆盖当前栈，可以将调用栈维持在很小的规模，这样通过递归调用，就可以处理大量数据了。
3. 递归与循环的关系
递归本质上就是循环，现代计算科学已经有很多通用方法，将递归转换为循环实现。
递归更符合人类的思维模式，但是在内存消耗、性能有一定消耗，通常会先设计递归算法，再将递归转化为对应的循环模式实现。
网上很容易搜到递归与循环的转换方法。
文章被以下专栏收录
