递归

一.定义

　　在一个函数内部再调用函数本身。

二.递归深度

　　每一次的调用，都会产生一个属于自己的空间，为了防止名称空间占用太多内存，于是python将递归层数控制在997（默认值），当然也可以修改，跟计算机的性能有关。

三.递归实例

　　1.求一个整数n的阶乘

1 def factorial(n) :
2   if n == 1 :
3     return 1         #递归结束
4   return n * factorial(n - 1)  #问题规模减1，递归调用

　　n = 5

　　执行完后面return后面的再返回

四.注意：

　　递归解决的问题：
　　就是通过参数，来控制每一次缩小计算的规模

　　适合的场景：
　　数据的规模在减小，但是解决问题的思路没有变

　　结束递归的的标志：return

五.二分查找算法　

 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]
 2 def func(l,aim):
 3     mid = (len(l)-1)//2
 4     if l:
 5         if aim > l[mid]:
 6             func(l[mid+1:],aim)
 7         elif aim < l[mid]:
 8             func(l[:mid],aim)
 9         elif aim == l[mid]:
10             print("bingo",mid)
11     else:
12         print('找不到')
13 func(l,66)
14 func(l,6)
15 
16 #升级版
17 def func(l, aim,start = 0,end = len(l)-1 ):
18     mid = (start+end)//2
19     if not l[start:end+1]:
20         return
21     elif aim > l[mid]:
22         return func(l,aim,mid+1,end)
23     elif aim < l[mid]:
24         return func(l,aim,start,mid-1)
25     elif aim == l[mid]:
26         print("bingo")
27         return mid
28 
29 index = func(l,68)
30 print(index)