python-递归

递归

在调用一个函数的过程中，直接或间接使用了函数本身

递归效率很低，需要在进入下一次递归时保留当前状态，Python不像其他语言，没有尾递归，但是Python有限制条件，不允许用户无限递归

递归的特点：

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

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

3.递归效率不高，递归层数过多会导致栈溢出

如果有这样一个列表，让你从这个列表中找到66的位置，你要怎么做？

l = [2,3,5,10,15,16,18,22,26,30,32,35,41,42,43,55,56,66,67,69,72,76,82,83,88]

你说，so easy！

l.index(66)...

我们之所以用index方法可以找到，是因为python帮我们实现了查找方法。如果，index方法不给你用了。。。你还能找到这个66么？

如果有这样一个列表，让你从这个列表中找到66的位置，你要怎么做？

l = [2,3,5,10,15,16,18,22,26,30,32,35,41,42,43,55,56,66,67,69,72,76,82,83,88]
你说，so easy！

l.index(66)...

我们之所以用index方法可以找到，是因为python帮我们实现了查找方法。如果，index方法不给你用了。。。你还能找到这个66么？

上面这个方法就实现了从一个列表中找到66所在的位置了。

但我们现在是怎么找到这个数的呀？是不是循环这个列表，一个一个的找的呀？假如我们这个列表特别长，里面好好几十万个数，那我们找一个数如果运气不好的话是不是要对比十几万次？这样效率太低了，我们得想一个新办法。

二分查找算法

l = [2,3,5,10,15,16,18,22,26,30,32,35,41,42,43,55,56,66,67,69,72,76,82,83,88]

你观察这个列表，这是不是一个从小到大排序的有序列表呀？

如果这样，假如我要找的数比列表中间的数还大，是不是我直接在列表的后半边找就行了？

l = [2,3,5,10,15,16,18,22,26,30,32,35,41,42,43,55,56,66,67,69,72,76,82,83,88]

def func(l,aim):
    mid = (len(l)-1)//2
    if l:
        if aim > l[mid]:
            func(l[mid+1:],aim)
        elif aim < l[mid]:
            func(l[:mid],aim)
        elif aim == l[mid]:
            print("bingo",mid)
    else:
        print('找不到')
func(l,66)
func(l,6)

二分法基础版

def func(l, aim,start = 0,end = len(l)-1 ):
    mid = (start+end)//2
    if not l[start:end+1]:
        return
    elif aim > l[mid]:
        return func(l,aim,mid+1,end)
    elif aim < l[mid]:
        return func(l,aim,start,mid-1)
    elif aim == l[mid]:
        print("bingo")
        return mid

index = func(l,68)
print(index)

二分法查找升级版

递归函数与三级菜单

menu = {
    '北京': {
        '海淀': {
            '五道口': {
                'soho': {},
                '网易': {},
                'google': {}
            },
            '中关村': {
                '爱奇艺': {},
                '汽车之家': {},
                'youku': {},
            },
            '上地': {
                '百度': {},
            },
        },
        '昌平': {
            '沙河': {
                '老男孩': {},
                '北航': {},
            },
            '天通苑': {},
            '回龙观': {},
        },
        '朝阳': {},
        '东城': {},
    },
    '上海': {
        '闵行': {
            "人民广场": {
                '炸鸡店': {}
            }
        },
        '闸北': {
            '火车战': {
                '携程': {}
            }
        },
        '浦东': {},
    },
    '山东': {},
}

menu

def threeLM(dic):
    while True:
        for k in dic:print(k)
        key = input('input>>').strip()
        if key == 'b' or key == 'q':return key
        elif key in dic.keys() and dic[key]:
            ret = threeLM(dic[key])
            if ret == 'q': return 'q'
        elif (not dic.get(key)) or (not dic[key]) :
            continue

threeLM(menu)

递归函数实现三级菜单