python的递归与二分法

Posted on | In

递归

递归:在调用一个函数的过程中，直接或间接地调用了函数本身这个就叫递归

1.必须有个明确的结束条件

2.每次进入更深一层递归时，问题规模相比上次递归应有所减少

3.递归效率不高，递归层次过多会导致栈溢出（在计算机中，函数调用是通过栈(stack)这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，就栈就会减少一层栈帧。由于栈的大小不是无限的，递归调用的次数过多，则会导致栈溢出）

实例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def age(n):
    if n == 1:
        return 18
    else:
        return age(n-1)+2
 
print(age(5))
# age(5)=age(4)+2 第一次进入
# age(4)=age(3)+2 第二次进入
# age(3)=age(2)+2 第三次进入
# age(2)=age(1)+2 第四次进入
# age(1)=18 第五次进入，最后判断终止条件

# age(n)=age(n-1)+2 #n>1  递归终止条件
# age(1)=18 #n=1          等于终止条件

二分法

每次拿中间的值与想要的值比较

例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
name = {12, 32, 23, 45, 123, 4654, 1231, 1, 2, 212, 56, 9, 34, 99, 30}
name_sor = sorted(name)     #把列表内容按升序排列
 
 
def second_find(x, li):
    mid_index = int(len(li) / 2)
    if len(li) > 1:
        if x > li[mid_index]:
            l1 = li[mid_index:]
            second_find(x,l1)
        elif x <li[mid_index]:
            l2 = li[:mid_index]
            second_find(x,l2)
        else:
            print('恭喜你找到了')
    elif len(li) == 1:
        if li[0] == x:
            print("恭喜你找到了")
        else:
            print("gun!")
 
 
second_find(32, name_sor)