Python 递归函数

一、初始递归

递归函数：在一个函数里在调用这个函数本身。

递归的最大深度：998

正如你们刚刚看到的，递归函数如果不受到外力的阻止会一直执行下去。但是我们之前已经说过关于函数调用的问题，每一次函数调用都会产生一个属于它自己的名称空间，如果一直调用下去，就会造成名称空间占用太多内存的问题，于是python为了杜绝此类现象，强制的将递归层数控制在了997。

拿什么来证明这个“998理论”呢？这里我们可以做一个实验：

def foo(n):
    print(n)
    n += 1
    foo(n)
foo(1)

结果：

/usr/local/bin/python3 /home/yuchuantester/YuchuanData/PythonData/PythonProject/YuchuanDemo008.py
1
2
3
.
.
.
.
.
.
994
995
996
Traceback (most recent call last):
  File "/home/yuchuantester/YuchuanData/PythonData/PythonProject/YuchuanDemo008.py", line 58, in <module>
    foo(1)
    print(n)
RecursireplaceString: maximum recursion depth exceeded while calling a Python object

Process finished with exit code 1

由此我们可以看出，未报错之前能看到的最大数字就是996.当然了，997是python为了我们程序的内存优化所设定的一个默认值，我们当然还可以通过一些手段去修改它：

import sys

print(sys.setrecursionlimit(2000))
def fool(n):
    print(n)
    n += 1
    fool(n)
fool(1)

结果：

/usr/local/bin/python3 /home/yuchuantester/YuchuanData/PythonData/PythonProject/YuchuanDemo008.py
None
1
2
3
.
.
.
1994
1995
1996
Traceback (most recent call last):
  File "/home/yuchuantester/YuchuanData/PythonData/PythonProject/YuchuanDemo008.py", line 93, in fool
    fool(n)
  [Previous line repeated 995 more times]
  File "/home/yuchuantester/YuchuanData/PythonData/PythonProject/YuchuanDemo008.py", line 91, in fool
    print(n)
RecursireplaceString: maximum recursion depth exceeded while calling a Python object

Process finished with exit code 1

我们可以通过这种方式来修改递归的最大深度，刚刚我们将python允许的递归深度设置为了10w，至于实际可以达到的深度就取决于计算机的性能了。不过我们还是不推荐修改这个默认的递归深度，因为如果用997层递归都没有解决的问题要么是不适合使用递归来解决要么是你代码写的太烂了～～～

看到这里，你可能会觉得递归也并不是多么好的东西，不如while True好用呢！然而，江湖上流传这这样一句话叫做：人理解循环，神理解递归。所以你可别小看了递归函数，很多人被拦在大神的门槛外这么多年，就是因为没能领悟递归的真谛。而且之后我们学习的很多算法都会和递归有关系。来吧，只有学会了才有资本嫌弃！

二、递归示例讲解

例一：

现在你们问我，LBJ老师多大了？我说我不告诉你，但LBJ比 ATN大两岁。

你想知道ATN多大，你是不是还得去问ATN？ATN说，我也不告诉你，但我比DHW大两岁。

你又问DHW，DHW也不告诉你，他说他比ADTKB大两岁。

那你问ADTKB，ADTKB告诉你，他18了。

这个时候你是不是就知道了？LBJ多大？

你为什么能知道的？

首先，你是不是问alex的年龄，结果又找到egon、武sir、太白，你挨个儿问过去，一直到拿到一个确切的答案，然后顺着这条线再找回来，才得到最终alex的年龄。这个过程已经非常接近递归的思想。我们就来具体的我分析一下，这几个人之间的规律。

age_LBJ = age_ATN+2
age_ATN = age_DHW+2
age_DHW = age_ADTKB+2
age_ADTKB = 18

age_LBJ = age_ADTKB+2+2+2
age_LBJ = 18+2+2+2
age_LBJ = 24

那这样的情况，我们的函数怎么写呢？

def find_age(n, init_age):
    if n == 1:
        return init_age
    else:
        return find_age((n - 1), init_age) + 2
print(find_age(4, 18))
print(find_age(6, 18))
print(find_age(8, 18))

结果：

/usr/local/bin/python3 /home/yuchuantester/YuchuanData/PythonData/PythonProject/YuchuanDemo008.py
24
28
32

Process finished with exit code 0

递归函数与三级菜单

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

递归函数实现三级菜单

def threeLM(dict):
    while 1:
        for item in dict:
            print(item)
        key = input("input>>").strip()
        if key == 'b' or key == 'q':
            return key
        elif key in dict.keys() and dict[key]:
            ret = threeLM(dict[key])
            if ret == 'q':
                return 'q'
threeLM(menu)

结果：

/usr/local/bin/python3 /home/yuchuantester/YuchuanData/PythonData/PythonProject/YuchuanDemo008.py
北京
上海
山东
input>>b

Process finished with exit code 0

还记得之前写过的三级菜单作业么？现在咱们用递归来写一下～

l = [menu]

while l:
    for key in l[-1]: print(key)
    k = input('input>>').strip()  # 北京
    if k in l[-1].keys() and l[-1][k]:
        l.append(l[-1][k])
    elif k == 'b':
        l.pop()
    elif k == 'q':
        break

结果：

/usr/local/bin/python3 /home/yuchuantester/YuchuanData/PythonData/PythonProject/YuchuanDemo008.py
北京
上海
山东
input>>北京
海淀
昌平
朝阳
东城
input>>昌平
沙河
天通苑
回龙观
input>>b
海淀
昌平
朝阳
东城
input>>q

Process finished with exit code 0