Python的递归函数与算法

• 递归函数
• 算法（二分法）

一、递归函数

　　1. 递归函数的概念

　　　　递归函数是函数在运行过程中直接或间接调用了自身的函数

　　　　递归分为两部分：递推和回溯

　　　　　　1) 递推

　　　　　　　　一层层往下推导答案（每次递归之后复杂度相较于上一次一定要有所下降）

　　　　　　2) 回溯

　　　　　　　　依据最后的结论往后推导出最初需要的答案

　　　　　　递归一定要有结束条件！！！

　　　　Python默认的最大递归深度为1000次

import sys
print(sys.getrecursionlimit())
sys.setrecursionlimit(2000)
count = 1
def index():
    global count
    count += 1
    print(count)
    index()
index()

　　　　这样可以更改递归深度

　　2. 递归函数的使用

　　　　1) 使用递归函数进行运算

伪代码:可能无法运行 但是可以表述逻辑
age(5) = age(4) + 2
age(4) = age(3) + 2
age(3) = age(2) + 2
age(2) = age(1) + 2
age(1) = 18

　　　　　　代码实现：

def get_age(n):
    if n == 1:
        return 18
    return get_age(n - 1) + 2
print(get_age(5))

　　　　2) 打印出列表中每一个元素(列表除外)

l = [1,[2,[3,[4,[5,[6,[7,[8,[9,[10,[11,[12,[13,[14,]]]]]]]]]]]]]]
# 1.循环该列表 获取列表内每一个元素
# 2.判断该元素是否是数字 如果是数字 则直接打印
# 3.如果是列表 则循环该列表 获取列表内每一个元素
# 4.判断该元素是否是数字 如果是数字 则直接打印
# 5.如果是列表 则循环该列表 获取列表内每一个元素
# 6.判断该元素是否是数字 如果是数字 则直接打印
# 7.如果是列表 则循环该列表 获取列表内每一个元素

　　　　　　代码实现：

l = [1,[2,[3,[4,[5,[6,[7,[8,[9,[10,[11,[12,[13,[14,]]]]]]]]]]]]]]
def get_num(l):
    for i in l:
        if type(i) is int:
            print(i)
        else:
            # 也是for循环 然后判断
            get_num(i)
get_num(l)

二、算法之二分法

　　1. 算法的概念

　　　　算法是解决问题高效的方法

　　2. 二分法

　　　　二分法能够使用的前提是数据集必须有序

　　　　从下面列表中查找某个值

l = [11, 23, 43, 57, 68, 76, 81, 99, 123, 321, 432, 567, 666, 712, 899, 999, 1111]

　　　　1) 第一种方式，直接for循环从左往右依次查找

　　　　2) 第二种方式，使用二分法

l = [11, 23, 43, 57, 68, 76, 81, 99, 123, 321, 432, 567, 666, 712, 899, 999, 1111]
def my_partner(target_num, l):  # target_num=321  l=l
    if len(l) == 0:
        print('不好意思 我尽力 没找到')
        return
    # 先获取中间位置索引值
    middle_index = len(l) // 2  # 8
    # 判断中间索引对应的值比目标值大还是小
    if target_num > l[middle_index]:
        # 说明要找的元素只可能出现在列表的右侧
        l_right = l[middle_index + 1:]  # l[9:]
        print(l_right)
        my_partner(target_num, l_right)
    elif target_num < l[middle_index]:
        # 说明要找的元素只可能出现在列表的左侧
        l_left = l[:middle_index]
        print(l_left)
        my_partner(target_num, l_left)
    else:
        print('找到了', target_num)
my_partner(567,l)

　　　　　　二分法也有弊端，当我们要查找的元素就在数据集的开头那么该算法可能不是很高效

target_list = [...]
def my_two(target_list,target_num):
    if len(target_list) == 0:
        print('该元素不存在')
        return
    middle_index = len(target_list)//2
    if target_num > target_list[middle_index]:
        target_right = target_list[middle_index+1:]
        my_two(target_right,target_num)
    elif target_num < target_list[middle_index]:
        target_left = target_list[:middle_index]
        my_two(target_left,target_num)
    else:
        print('find it',target_num)