递归函数和二分法查找

一.递归函数

　　递归函数：在一个函数里在调用这个函数本身。

　　递归函数如果不受到外力的阻止会一直执行下去。但是我们之前已经说过关于函数调用的问题，每一次函数调用都会产生一个属于它自己的

名称空间，如果一直调用下去，就会造成名称空间占用太多内存的问题，于是python为了杜绝此类现象，强制的将递归层数控制在了997.

1 def foo(n):
2     print(n)
3     n += 1
4     foo(n)
5 foo(1)

　　未报错之前能看到的最大数字就是998.当然了，997是python为了我们程序的内存优化所设定的一个默认值，我们当然还可以通过一些手段去

修改它：

1 import sys
2 print(sys.setrecursionlimit(设定递归的最大深度))

二.二分法查找

　　二分查找算法也称折半查找，基本思想就是折半，和平时猜数字游戏一样，比如猜的数字时67，猜测范围是0-100，则会先猜测中间值50，

结果小了，所以就会从50-100猜测，中间值为75，结果大了，又从50-75猜测中间值，一直到猜中为止。因此，二分查找有一个限制就是原先数

组需要是一个有序数组.

　在列表l中查找数字66:　

l = [2,3,5,10,15,16,18,22,26,30,32,35,41,42,43,55,56,66,67,69,72,76,82,83,88]
具体思考流程如下:

 1 def func(l,aim):
 2     mid = (len(l)-1)//2
 3     if l:
 4         if aim > l[mid]:
 5             func(l[mid+1:],aim)
 6         elif aim < l[mid]:
 7             func(l[:mid],aim)
 8         elif aim == l[mid]:
 9             print("bingo",mid)
10     else:
11         print('找不到')
12 func(l,66)
13 
14 运行结果:bingo 0

View Code

　　为什么没有找到66的索引呢?因为在比较得到比目标数大或者小的切片后,实际上是改变了目标的索引,切到最后只会出现0和1两种情况,说明上

述代码实现不了查找,需要优化.

 1 l1 = [1, 2, 4, 5, 7, 9]
 2 def two_search(l,aim,start=0,end=None):
 3     end = len(l)-1 if end is None else end
 4     mid_index = (end - start) // 2 + start
 5     if end >= start:
 6         if aim > l[mid_index]:
 7             return two_search(l,aim,start=mid_index+1,end=end)
 8 
 9         elif aim < l[mid_index]:
10             return two_search(l,aim,start=start,end=mid_index-1)
11 
12         elif aim == l[mid_index]:
13             return mid_index
14         else:
15             return '没有此值'
16     else:
17         return '没有此值'
18 print(two_search(l1,9))

View Code