Python——函数之递归、栈的使用
今天主要和大家分享函数的递归，同时引入一个新的概念——栈
1.递归
1.定义
函数的递归指的就是函数自己调用自己，什么是函数自己调用自己呢？我们来看一个栗子：
这里给大家一个数学中的一个数列：斐波那契数列 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368，它指的是前两项的和等于第三项，那么我们对于这样的需求如何用Python代码实现呢？这个时候就用到了函数的递归
def func(arg1,arg2):
if arg1 == 0:
print(arg1,arg2)
# 拿到第三个值
arg3 = arg1 + arg2
print arg3
#将第二个值和第三个值作为参数继续传入函数中
func(arg2,arg3)
# 将斐波那契数列的前两项0,1传入函数
func(0,1)
通过上面的这个例子，是不是对于递归有了一定的理解呢，但是递归本身是属于自己本身调用自己，这种方式是一种效率低，且消耗内存的一种方式
2.用递归实现三级菜单
三级菜单我们平时都是很常见的，像是在淘宝里买东西的时候，需要我们填写地址，这些操作我们仔细想想都是三级菜单，而且我们也可以通过递归来操作
menu = {
'北京': {
'海淀': {
'五道口': {
'soho': {},
'网易': {},
'google': {}
},
'中关村': {
'爱奇艺': {},
'汽车之家': {},
'youku': {},
},
'上地': {
'百度': {},
},
},
'昌平': {
'沙河': {
'老男孩': {},
'北航': {},
},
'天通苑': {},
'回龙观': {},
},
'朝阳': {},
'东城': {},
},
'上海': {
'闵行': {
"人民广场": {
'炸鸡店': {}
}
},
'闸北': {
'火车战': {
'携程': {}
}
},
'浦东': {},
},
'山东': {},
}
def menu_func(menu):
while True:
# 循环打印menu，得到对应的键：北京、上海、广州
for key in menu:
print(key)
inp = input('请输入要查询的地址（q退出，b返回上一级）：').strip()
if inp.upper() == 'Q': return 'q'
if inp.upper() == 'B': return 'b'
# 判断能否拿到对应正确的值
elif menu.get(inp):
# 使用递归将用户输入的值再次进行循环打印显示
flag = menu_func(menu[inp])
# 一层一层的return进行退出
if flag == 'q': return 'q'
menu_func(menu)
2.栈lifo
这里在给大家介绍一个新的概念（数据结构）——栈 lifo（last in first out即后进先出）。
栈的特点就是后进先出，顾名思义，就是最后进来的数据要最先出去。那么上面的我们用递归实现的三级菜单，使用栈应该怎么实现呢？
# 三级菜单
# 栈
menu = {
'北京': {
'海淀': {
'五道口': {
'soho': {},
'网易': {},
'google': {}
},
'中关村': {
'爱奇艺': {},
'汽车之家': {},
'youku': {},
},
'上地': {
'百度': {},
},
},
'昌平': {
'沙河': {
'老男孩': {},
'北航': {},
},
'天通苑': {},
'回龙观': {},
},
'朝阳': {},
'东城': {},
},
'上海': {
'闵行': {
"人民广场": {
'炸鸡店': {}
}
},
'闸北': {
'火车战': {
'携程': {}
}
},
'浦东': {},
},
'山东': {},
}
# 先将整个大的字典放在一个列表中
lst = [menu]
#当列表不为空的时候，我们开始循环
while lst:
#取列表的最后一项，即当前的大字典
for key in lst[-1]:
# 北京
print(key)
inp = input('>>>')
# 输入q直接退出循环
if inp.upper() == 'Q':break
#返回上一级的时候，对列表进行pop，这样会默认删除掉列表最后的那个元素，对于再次循环列表时，拿到的最后一个元素就是上一层的菜单
elif inp.upper() == 'B':lst.pop()
# 从字典中取出你输入的地址，又对应拿到下一层的菜单
elif lst[-1].get(inp):
# 将对应的下一级菜单添加到列表中的最后一个位置上，反复循环。
lst.append(lst[-1][inp])
以上就是函数的递归以及栈的相关分享。