递归函数和二分法

递归函数与二分法

函数的递归调用：

在调用一个函数的过程中又直接或者间接地调用该函数本身，称之为递归调用
- 递归必须满足两个条件：
  1. 每进入下一次递归调用，问题的规模都应该有所减少
  2. 递归必须有一个明确的结束条件
- 递归两个明确的阶段：
  1. 回溯：函数调用循环规模减少的过程
  2. 递推：循环结束一层层返回结果的过程
```
# 实现5的阶乘5！

def factorial(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n - 1)


print(factorial(5))
 
```

二分法

在有序的区间内查找时，使用二分法使对比范围缩小一半，大大提升了查找效率（普通查找需要一个个进行遍历，效率太低）

# 在列表内查找值
l1 = [1,2,3,4,6,7,8,9,13,23,24,25,26,29,30,40,48,55,60]
def find_n(list1, num):
    if len(list1) == 0:
        print('not in')
        return
    x = list1[len(list1) // 2]
    if num > x:
        list1 = list1[len(list1) // 2 + 1:]
        return find_n(list1, num)
    elif num < x:
        list1 = list1[:len(list1) // 2]
        return find_n(list1, num)
    else:
        print('find it')


find_n(l1, 23)