【一】递归的定义#

【1】什么是递归#

在一个函数里在调用这个函数本身

【2】最大递归层数#

最大递归层数有限制：997
但是也可以自己限制

1
def foo(n):
2
    print(n)
3
    n+=1
4
    foo(n)
5
foo(1)

【3】最大层数限制#

Python默认的，可以做修改，但是不建议你修改。
（因为如果用997层递归都没有解决的问题要么是不适合使用递归来解决问题，要么就是你的代码太烂了）

1
import sys
2

3
#修改递归层数
4
sys.setrecursionlimit(10000000)
5

6
n=0
7
def f():
8
    global n
9
    n+=1
10
    print(n)
11
    f()
12
f()

我们可以通过以上代码，导入sys模块的方式来修改递归的最大深度。
sys模块：所有和python相关的设置和方法

【4】结束递归的标志#

return

【5】递归解决的问题#

就是通过参数，来控制每一次调用缩小计算的规模

【6】使用场景#

数据的规模在减少，但是解决问题的思路没有改变
很多排序算法会用到递归

【二】递归小应用#

【1】猜小明的年龄#

下面我们来猜一下小明的年龄
- 小明是新来的同学，丽丽问他多少岁了。
- 他说：我不告诉你，但是我比滔滔大两岁。
- 滔滔说：我也不告诉你，我比晓晓大两岁
- 晓晓说：我也不告诉你，我比小星大两岁
- 小星也没有告诉他说：我比小华大两岁
- 最后小华说，我告诉你，我今年18岁了
这个怎么办呢？
当然，有人会说，这个很简单啊，知道小华的，就会知道小星的，知道小星的就会知道晓晓的，以此类推，就会知道小明的年龄啦。
这个过程已经非常接近递归的思想了。

姓名	年龄
小华	18+2
小星	20+2
晓晓	22+2
滔滔	24+2
小明	26+2

上面的图我们可以用个序号来表示吧

1
age(5) = age(4)+2
2
age(4) = age(3) + 2
3
age(3) = age(2) + 2
4
age(2) = age(1) + 2
5
age(1) = 18

那么代码该怎么写呢？

1
def age(n):
2
    if n ** 1:
3
        return 18
4
    else:
5
        return age(n - 1) + 2
6

7
ret=age(6)
8
print(ret)

【2】一个数，除2直到不能整除2#

1
def cal(num):
2
    if num % 2 ** 0:  ## 先判断能不能整除
3
        num = num // 2
4
        return cal(num)
5
    else:
6
        return num
7

8

9
print(cal(8))

【3】**如果一个数可以整除2，就整除，不能整除就*3+1**#

1
def func(num):
2
    print(num)
3
    if num**1:
4
        return
5
    if num%2**0:
6
        num=num//2
7
    else:
8
        num=num*3+1
9
    func(num)
10
func(5)

【三】三级菜单#

1
menu = {
2
    '北京': {
3
        '海淀': {
4
            '五道口': {
5
                'soho': {},
6
                '网易': {},
7
                'google': {}
8
            },
9
            '中关村': {
10
                '爱奇艺': {},
11
                '汽车之家': {},
12
                'youku': {},
13
            },
14
            '上地': {
15
                '百度': {},
16
            },
17
        },
18
        '昌平': {
19
            '沙河': {
20
                '老男孩': {},
21
                '北航': {},
22
            },
23
            '天通苑': {},
24
            '回龙观': {},
25
        },
26
        '朝阳': {},
27
        '东城': {},
28
    },
29
    '上海': {
30
        '闵行': {
31
            "人民广场": {
32
                '炸鸡店': {}
33
            }
34
        },
35
        '闸北': {
36
            '火车战': {
37
                '携程': {}
38
            }
39
        },
40
        '浦东': {},
41
    },
42
    '山东': {},
43
}

1
def threeLM(menu):
2
    while True:
3
        for key in menu:#循环字典的key，打印出北京，上海，山东
4
            print(key)
5
        name=input('>>>:').strip()
6
        if name**'back' or name**'quit':#如果输入back，就返回上一层。如果输入quit就退出
7
            return name #返回的name的给了ret
8
        if name in menu:
9
            ret=threeLM(menu[name])
10
            if ret**'quit':return 'quit'#如果返回的是quit，就直接return quit 了，就退出了
11
threeLM()
12
## print(threeLM(menu))#print打印了就返回出quit了，threeLM()没有打印就直接退出了