函数递归介绍

函数的递归调用，是函数嵌套调用的一种特殊形式。在调用一个函数的过程中，直接或者间接的调用到函数本身。

递归的本质就是循环，但不应让递归死循环，必须在满足某种条件时，结束递归调用。

递归的回溯，即一层一层的调用下去。

递归的递推，即在某一层满足结束条件，结束递归调用后，就会开始递推，也就是一层一层的返回结果的过程。

def f1(n):
    if n == 10:
        return
    print(n)
    n+=1
    f1(n)
f1(0)

二分法

作用

假如需要从一个按大小排序的列表中找到一个值，如果通过遍历的方式去查找，则在列表很长、同时要查找的值在最后面的情况下，需要把列表元素全部遍历一遍，造成了效率低下的问题。

而如果使用二分法，即便列表再长，也不会查找的太多次，因为二分法的每一次查找，都能直接排除掉一半，所以这是一种较为高效的查找方式。

实现

需要借用到函数递归实现自身调用自身，同时列表需要有序。

函数中先的出中间索引，然后通过该索引对应的值，判断与要查找的值的大小关系。

如果索引的值大于要找的值，则将列表前半部分进行切片，然后将其作为参数调用自身查找这一半。

反之小于则是找后半部分，同时判断如果索引对应的值等于要找的值，那就是找到了。

循环反复最终就将值找出来，但如果没有找到可能会抛出异常或死循环，所以应该在函数开头判断如果列表为空，则输出提示然后直接返回，不再继续执行。

# 二位列表存储数据
lst = [(i, f"iamdata-{i}") for i in range(0, 10000)]

# 二分法查找数据函数
def findata(lst, key):
    # 如果为递归到lst一个值都不剩，说明列表中没有要找的值。
    if len(lst) == 0:
        print('Found failed')
        return

    # 取中间索引
    mid_index = len(lst) // 2
    # 取中间值
    mid_value = lst[mid_index][0]
    # 如果有序列表的中间值大于key，说明要找的数据在前半段。
    if mid_value > key:
        # 查找前半段数据，，由于索引切片不包含结束索引的值，所以直接使用中间索引即可。
        return findata(lst[:mid_index], key)
    # 如果有序列表的中间值小于key，说明要找的数据在后半段。
    elif mid_value < key:
        # 查找后半段数据，由于索引切片会包含起始索引的值，所以要+1以排除这个已经判断过的中间值。
        return findata(lst[mid_index + 1:], key)
    # 如果等于则说明找到了，返回查找的数据。
    else:
        print(f"Index: {lst[mid_index][0]}, Find Data: {lst[mid_index][1]}")
        return

# 调用查找函数
findata(lst, 123)