递归函数

递归函数就是在函数中调用自身函数

##最大递归深度默认为997/998 ————是python从内存角度做得限制

1 def story():
2     print('从前有座山')
3     story()
4 
5 
6 #RecursionError: maximum recursion depth exceeded while calling a Python object
7 # 递归的错误，超过了递归的最大深度

如果递归次数太多，就不适合用递归解决问题

递归的缺点点：占内存，优点：会让代码变简单。

递归特点：不要只看到return就认为已经返回了。要看操作是在递到第几层的时候发生的，然后返回给了谁。若不是返回给最外层函数，调用者就接受不到。要在分析，看如何把结果返回回来。

用递归写的斐波那契数列：

1 def fib(n,a=1,b=1):
2     if n==1 : return a
3     return fib(n-1,b,a+b)
4 
5 ##查看第几个斐波那契数列。

查看前多个斐波那契数列（非递归。。。）：

def fib(max):
    n = 0
    a = 0
    b = 1
    while n < max:
        print (b)
        a, b = b,a+b
        # print('*****',a)
        n = n+1
fib(10)

阶乘：

def fac(n):
    if n ==1:
        return 1
    return n * fac(n-1)

用递归的写的二分查找算法：

 1 def find(l,aim,start = 0,end = None):
 2     end = len(l) if end is None else end
 3     mid_index = (end - start)//2 + start
 4     if start <= end:
 5         if l[mid_index] < aim:
 6             return find(l,aim,start =mid_index+1,end=end)
 7         elif l[mid_index] > aim:
 8             return find(l, aim, start=start, end=mid_index-1)
 9         else:
10             return mid_index
11     else:
12         return '找不到这个值'
13 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]
14 ret = find(l,1)
15 print(ret)