递归函数 二分查找

递归函数：
自己调用自己

def func1():
    print(666)
    func1()  #自己调用自己
func1()

递归到一定深度,就会主动终止,默认最大递归深度998(python解释器给终止的)

count = 0
def func1(n):
    n += 1
    print(n)
    func1(n)
func1(count)

设置递归深度:

count = 0
def func1(n):
    n += 1
    print(n)
    func1(n)
func1(count)

递归函数例子;

'''
n = 1  太白  age(1)= 23
n = 2  日天   age(2)= age(1) + 2
n = 3  wusir  age(3)= age(2) + 2
n = 4  alex   age(4)= age(3) + 2
'''
def age(n):
    if n == 1:
        return 23
    else:
        return age(n-1) + 2      # age(4) = age(3) + 2
print(age(4))           #23+2+2+2

二分查找：
用代码写的计算方式就是算法。
二分查找是最简单的算法，比较经典的算法。
前提:数字序列，有序，不重复。
查找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]
# print(l.index(66))

count = 0
for i in l:
    if i == 66:


        print(count)
    count += 1

for i in range(len(l)):
    if l[i] == 66:
        print(i)
        break
else:
    print('找不到..')
l1 = [1,3,5,7,8,10,11]

def index(l,aim):
    count = -1
    for i in l:
        count += 1
        if i == aim:
            return count
    else:
        return '没有此值'
print(index(l,66))

二分查找算法:

l1 = [2, 3, 5, 10, 15, 16, 18, 19]
def two_find(l,aim):
    mid_index = len(l) // 2
    if aim > l[mid_index]:
        return two_find(l[mid_index+1:],aim)
    elif aim < l[mid_index]:
        return two_find(l[:mid_index], aim)
    elif aim == l[mid_index]:
        return mid_index
    else:
        return None
print(two_find(l1,18))
print(two_find(l1,3))
print(two_find(l1,10))

l1 = [2, 3, 5, 10, 15, 16, 18]

def two_find(l,aim,start=0,end=None):
    end = len(l) - 1 if end is None else end
    mid_index = (end - start) // 2 + start
    '''
        第一次: aim:15 start: 0  end: 6  min_index: 3  中间值:10  aim > 10
        第二次: aim:15 start: 4  end: 6  min_index: 5  中间值:16  aim < 16
        第三次: aim:15 start: 4  end: 5  min_index: 4  中间值:15  aim = 15
        '''
    if start <= end:
        if aim > l[mid_index]:
            return two_find(l, aim, start=mid_index+1, end=end)
        elif aim < l[mid_index]:
            return two_find(l, aim, start=start, end=mid_index)
        elif aim == l[mid_index]:
            return mid_index
        else:
            return None
    else:
        return None
print(two_find(l1,15))

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]
def func(l,aim):
    mid = (len(l)-1)//2
    if l:
        if aim > l[mid]:
            func(l[mid+1:],aim)
        elif aim < l[mid]:
            func(l[:mid],aim)
        elif aim == l[mid]:
            print("bingo",mid)
    else:
        print('找不到')
func(l,66)
func(l,6)

升级版二分法:
l1 = [1, 2, 4, 5, 7, 9]
def two_search(l,aim,start=0,end=None):
    end = len(l)-1 if end is None else end
    mid_index = (end - start) // 2 + start
    if end >= start:
        if aim > l[mid_index]:
            return two_search(l,aim,start=mid_index+1,end=end)

        elif aim < l[mid_index]:
            return two_search(l,aim,start=start,end=mid_index-1)

        elif aim == l[mid_index]:
            return mid_index
        else:
            return '没有此值'
    else:
        return '没有此值'
print(two_search(l1,9))