一、递归函数

江湖上流传这这样一句话叫做：人理解循环，神理解递归。所以你可别小看了递归函数，很多人被拦在大神的门槛外这么多年，就是因为没能领悟递归的真谛。

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

递归的默认最大深度：998

举例，先来一个死循环

  1. def func1():
  2.     print(666)
  3. while True:
  4.     func1()

执行输出：

666

…

递归函数

  1. def func1():
  2.     print(666)
  3.     func1()
  4. func1()

执行输出：

666

…

RecursionError: maximum recursion depth exceeded while calling a Python object

那么它是执行到多少次时，报错呢？

加一个计数器

  1. count = 0
  2. def func1():
  3.     global count
  4.     count += 1
  5.     print(count)
  6.     func1()
  7. func1()

执行输出：

1

…

998

…

RecursionError: maximum recursion depth exceeded while calling a Python object

说明默认递归深度为 998

这个递归深度是可以改的

  1. import sys
  2. #更改默认递归深度
  3. sys.setrecursionlimit(100000)
  4. count = 0
  5. def func1():
  6.     global count
  7.     count += 1
  8.     print(count)
  9.     func1()
  10. func1()

执行输出：

…

3807

我的 wind10 系统，深度只能到这么多

至于实际可以达到的深度就取决于计算机的性能了

linux 系统，深度能够达到更深。比如说 1000 万，我开虚拟机测试的。

不过我们还是不推荐修改这个默认的递归深度，因为如果用 997 层递归都没有解决的问题要么是不适合使用递归来解决要么是你代码写的太烂了

举个例子来说明递归能做的事情

现在你们问我，alex 老师多大了？我说我不告诉你，但 alex 比 egon 大两岁。

你想知道 alex 多大，你是不是还得去问 egon？egon 说，我也不告诉你，但我比武 sir 大两岁。

你又问武 sir，武 sir 也不告诉你，他说他比太白大两岁。

那你问太白，太白告诉你，他 18 了。

这个时候你是不是就知道了？alex 多大？

1 金鑫 18

2 武 sir 20

3 egon 22

4 alex 24

你为什么能知道的？

首先，你是不是问 alex 的年龄，结果又找到 egon、武 sir、太白，你挨个儿问过去，一直到拿到一个确切的答案，然后顺着这条线再找回来，才得到最终 alex 的年龄。这个过程已经非常接近递归的思想。我们就来具体的我分析一下，这几个人之间的规律。

  1. age(4) = age(3) + 2
  2. age(3) = age(2) + 2
  3. age(2) = age(1) + 2
  4. age(1) = 18

那这样的情况，我们的函数怎么写呢？

  1. def age(n):
  2.     if n == 1:
  3.         return 18
  4.     else:
  5.         return age(n-1)+2
  6. print(age(4))

执行输出：24

二、二分查找法

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列

算法有很多种，比如：二分查找，树运算，堆，栈….

使用二分查找的前提

数据是有序且唯一的数字数列

举例：

有一个列表，需要查找出索引为 66 的值

  1. 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]

第一种方法: 直接使用 index 查询

  1. print(l.index(66))

执行输出：17

第二种方法: 使用 for 循环

  1. count = 0
  2. for i in l:
  3.     if i == 66:
  4.         print(count)
  5.         break
  6.     count += 1

执行输出，效果同上

假如我们这个列表特别长，里面好好几十万个数,效率太低了

需要使用二分查找算法

  1. 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.     ![](https://cdn.nlark.com/yuque/0/2020/png/1484428/1597633114279-73218e00-28f3-4ace-ad00-147b4b262683.png)

这就是二分查找算法！

那么落实到代码上我们应该怎么实现呢？

简单版二分法

  1. 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]
  3. def func(l,aim):
  4.     mid = (len(l)-1)//2
  5.     if l:
  6.         if aim > l[mid]:
  7.             func(l[mid+1:],aim)
  8.         elif aim < l[mid]:
  9.             func(l[:mid],aim)
  10.         elif aim == l[mid]:
  11.             print("bingo",mid)
  12.     else:
  13.         print('找不到')
  14. func(l,66)
  15. func(l,6)

执行输出：

bingo 0

找不到

升级版二分法

把列表改短一点

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

执行输出：

4

加日志执行:

  1. li = [2, 3, 5, 10, 15, 33, 55]
  2. count = 0
  3. def two_search(li, aim, start=0, end=None):
  4.     global count
  5.     count += 1
  6.     end = len(li)-1 if end is None else end #结束索引值,len(li)要减 1,否则如果传 100，函数无法结束。
  7.     mid_index = (end - start) // 2 + start  #中间索引
  9.     #加日志
  10.     print('第{}执行,start 的值为{},end 的值为{},mid_index 的值为{},li[mid_index]的值为{}'.format(count, start,end,mid_index,li[mid_index]))
  12.     if start <= end:
  13.         if li[mid_index] < aim:
  14.             return two_search(li, aim, start=mid_index+1, end=end)
  15.         elif li[mid_index] > aim:
  16.             return two_search(li, aim, start=start, end=mid_index-1)  #（[2,3,5],3）
  17.         elif li[mid_index] == aim:
  18.             return mid_index
  19.         else:
  20.             return '没有此值'
  21.     else:
  22.         return '没有此值'
  23. print(two_search(li,15))

执行输出：

第 1 执行,start 的值为 0,end 的值为 6,mid_index 的值为 3,li[mid_index]的值为 10

第 2 执行,start 的值为 4,end 的值为 6,mid_index 的值为 5,li[mid_index]的值为 33

第 3 执行,start 的值为 4,end 的值为 4,mid_index 的值为 4,li[mid_index]的值为 15

4

解释：

先来解释一下中间索引 // 表示取整除 - 返回商的整数部分 ，比如 9//2 输出结果 4

列表有 7 个元素，第一次，执行时，start 为 0，(end - start) // 2 + start 等于(6-0)//2 + 0 mid_index 的值为 3，li[mid_index]的值为 10

那么为什么 mid_index 的等式，后面要加 start 呢？

  1.     ![](https://cdn.nlark.com/yuque/0/2020/png/1484428/1597633114233-0c502a76-e918-4271-aa09-544c954a864e.png)

第一次执行时,中间索引值，取 3

第二次执行时,中间索引值，取 5

如果不加 start，那么第二只还是取的是 3

第一次执行时，li[mid_index]的值为 10，aim 的值为 15，

进入 if 判断，走第一个 if 条件，因为找到的中间值比目标值要小，所以 start 要在 mid_index 的基础上加 1。通俗的来讲，劈一半，左边找的值太小，就找右边，所以要加 1

第二次执行时，li[mid_index]的值为 33，aim 的值为 15，

进入 if 判断，走第二个 if 条件，因为找到的中间值比目标值要大，start 依然不变,end 要在 mid_index 的基础上减 1。通俗的来讲，再劈一半，左边找的值太大，就继续找左边的，所以要减 1

第三次执行时，li[mid_index]的值为 15，aim 的值为 15，

进入 if 判断，走第三个 if 条件，已经找到目标值了，直接 return mid_index 结束整个函数