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])
以上就是函数的递归以及栈的相关分享.
来源: https://www.cnblogs.com/guoruijie/p/11172191.html