递归调用与二分法

1、递归调用

递归调用：在调用一个函数的过程中，直接或间接地调用了函数本身.

示例：def age(n):    if n == 1:        return 18   # 结束条件    return age(n-1)+2   # 调用函数本身print(age(5))打印结果26

递归的执行分为两个阶段：

1 递推

2 回溯

示例图 

 

 

递归特性:

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

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

3、递归效率不高，因为每次调用自身时，都会在内存中创建一个新的内存空间，当不断循环调用非常多次时，是非常耗内存的。

2、二分法

主要应用于有序序列中，原理是每次查找都将原序列折半，逐渐缩小查找范围的一种算法。

例如查找一个数字，查找了打印 ‘find it’ 没有查到打印 'not exists'

l = [1,2,5,7,10,31,44,47,56,99,102,130,240]def binary_search(l,num):    print(l)    if len(l) == 1:        if l[0] == num:            print('find it')        else:            print('not exists')        return    mid_index=len(l)//2    mid_value=l[mid_index]    if num == mid_value:        print('find it')        return    if num > mid_value:        l=l[mid_index:]    if num < mid_value:        l=l[:mid_index]    binary_search(l,num)binary_search(l,31)