递归

递归调用

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

# 递归调用示例(直接调用，无限递归)
def func():
    print('山里有庙，庙里有个老和尚................')
    func()


func()

# 递归调用示例(间接调用，无限递归)

def foo():
    print('from foo')
    bar()

def bar():
    print('from bar')
    foo()

f00()

递归要有一个明确的的结束条件，结束递归的方式是return

#猜年龄的例子：
def age(n):
    if n ==5:
        return 18
    else:
        ret = age(n+1)return ret +2

     以下是灵魂画师egon老师的示例图，

递归的应用

1.递归实现3级菜单

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

def select(menu):
    name1 = input('请输入要查询的地区:')
    if name1 in menu:
        for j in menu[name1]:
            print(j)
        select(menu[name1])

select(menu)

2.实现2分查找

l = [2,3,4,5,6,12,23,34,35,37,42,45,50,51,52,53,54,56,58,60,61,63,64,65,66,67,69,70]

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,66)
print(index)