day 17 - 1 递归函数

#可以执行下，看下与递归函数执行的结果有什么不同
while True:
    print('从前有座山')

#一个简单的递归函数
def story():
    print('从前有座山')
    story()
    print(111)  #执行不到这句话

story()


#RecursionError: maximum recursion depth exceeded while calling a Python object
# 递归的错误，超过了递归的最大深度

#测试以下 python 中的递归深度  默认 997

#修改递归限制
import sys
sys.setrecursionlimit(100000)  #不要改

n=0
def rec():
    global n
    print('从前有座山')
    n +=1
    print(n)
    rec()
rec()

# 如果递归次数太多，那么就不适合使用递归来解决问题
# 递归的缺点 ： 占内存
# 递归的优点：  会让代码变简单

张三 多大       n = 1   age(1) = age(2)+2 = age(n+1) + 2
张三 比 李四 大两岁
李四 多大？      n = 2   age(2) = age(3) + 2 = age(n+1) +2
李四 比 王五 大两岁
王五 多大       n = 3   age(3) = age(4) + 2 = age(n+1) +2
王五 比 赵六 大两岁
赵六 多大？
赵六 40 了      n = 4   age(4) = 40

def age(n):
    if n == 4:
        return 40
    elif n >0 and n < 4:
        return age(n+1) + 2
print(age(1))  #输出结果 46

def age(1):
    if 1 == 4:
        return 40
    elif 1 > 0 and 1 < 4:
        return 46  #于是最终得到 46 的结果

def age(2):
    if 2 == 4:
        return 40
    elif 2 >0 and 2 < 4:
        return age(3) + 2    # age(3) 的返回结果加 2 得到 44，返回给 age(1)

def age(3):
    if 3 == 4:
        return 40
    elif 3 >0 and 3 < 4:
        return  age(n+1) + 2   #4、age(4) + 2 得到 42 返回给age(2)

def age(4):
    if 4 == 4:        #2、发现下面判断不在满足条件
        return 40    #3、于是返回 return 40，注意：这里返回给了调用着 age(3)
    elif n >0 and n < 4:
        return  age(n+1) + 2        #1、这里 age(3+1) 得到 age(4) ，再次调用

k = [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]
def find(lis,aim):
    #获取中间值
    mid = len(lis)//2
    #如果中间值大于 aim
    if lis[mid] > aim:
        new_lis = lis[:mid]
        find(new_lis,aim)
    elif lis[mid] < aim:
        new_lis = lis[mid + 1:]
        find(new_lis,aim)
    else:
        print('找到了：'+ str(aim) + ' 所在位置为：'+ str(mid))

find(k,66)

k = [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]
def find(lis,aim,start = 0,end = len(k)):
    #获取中间值
    mid = (end - start)//2 + start
    #如果中间值大于 aim
    if lis[mid] > aim:
        find(lis,aim,start = start,end = mid-1)
    elif lis[mid] < aim:
        find(lis,aim,start = mid + 1,end = end)
    else:
        print('找到了：'+ str(aim) + ' 所在位置为：',mid)

find(k,18)
find(k,43)

k = [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]
def find(lis,aim,start = 0,end = None):
    end = len(lis) if end is None else end
    #获取中间值
    mid = (end - start) // 2 + start
    #中间值大于 aim
    if lis[mid] > aim:
        find(lis,aim,start = 0,end = mid - 1)
    elif lis[mid]< aim:
        find(lis,aim,start= mid + 1,end = end)
    else:
        print('找到了：'+str(aim)+"位于"+str(mid))
find(k,69)

k = [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]
def find(lis,aim,start = 0,end = None):
    end = len(lis) if end is None else end
    #获取中间值
    mid = (end - start) // 2 + start
    if start <= end:
        #中间值大于 aim
        if lis[mid] > aim:
            find(lis,aim,start = 0,end = mid - 1)
        elif lis[mid]< aim:
            find(lis,aim,start= mid+1,end = end)
        else:
            print('找到了：'+str(aim)+"位于"+str(mid))
    else:
        print('找不到这个值')
find(k,68)

k = [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]
def find(lis,aim,start = 0,end = None):
    end = len(lis) if end is None else end
    #获取中间值
    mid = (end - start) // 2 + start
    if start <= end:
        #中间值大于 aim
        if lis[mid] > aim:
           return find(lis,aim,start = 0,end = mid - 1)
        elif lis[mid]< aim:
           return find(lis,aim,start= mid+1,end = end)
        else:
           # print('找到了：'+str(aim)+"位于"+str(mid))
           return mid
    else:
        return'找不到这个值'

print(find(k,5))

# 67  发生两次调用
# 66  发生好几次
# 44  找不到