十四. Python基础(14)--递归

1 ● 递归(recursion)

概念: recursive functions—functions that call themselves either directly or indirectly in order to loop.

最大递归层数: the default maximum recursion depth in Python is 997.

限制条件: 一定有一个分支不调用自身

修改最大递归层数:

import sys

sys.setrecursionlimit(1500)

COUNT = 0

def func():

global COUNT # 虽然函数内可以引用COUNT, 但是因为下面修改了COUNT, 所以要用global声明COUNT

COUNT += 1

print(COUNT)

func()

2 ● 递归的典型案例:

alex的年龄

阶乘

斐波那契数列

二分查找

三级菜单

3 ● alex的年龄

def age(n):

if n == 4:

return 40

return age(n+1) + 2

print(age(4)) # 40

4 ● 阶乘

def fact(n):

if n == 1:

return 1

return n * fact(n-1)

print(fact(4)) # 24

5 ● 斐波那契数列

def fib(n):

if n ==1 or n == 2:

return 1

return fib(n-1) + fib(n-2)

print(fib(6)) # 8

6 ● 二分查找

def search(num, l, start = None, end =None):

start = start if start else 0

end = end if end else len(l)-1

mid = (end-start)//2 + start

if start > end:

return None

elif l[mid] > num:

return search(num, l, start, mid - 1)

elif l[mid] < num:

return search(num, l, mid + 1, end)

elif l[mid] == num:

return mid

l = [2,3,5,10,15,16,18,22,26,30,32,35,41,42,43,55,56,66,67,69,72,76,82,83,88]

print(search(66,l)) # 17

7 ● 三级菜单

menu = {

'北京': {

'海淀': {

'五道口': {

'soho': {},

'网易': {},

'google': {}

'中关村': {

'爱奇艺': {},

'汽车之家': {},

'youku': {},

'上地': {

'百度': {},

'昌平': {

'沙河': {

'老男孩': {},

'北航': {},

'天通苑': {},

'回龙观': {},

'朝阳': {},

'东城': {},

'上海': {

'闵行': {

"人民广场": {

'炸鸡店': {}

}

'闸北': {

'火车战': {

'携程': {}

}

'浦东': {},

'山东': {},

}

def Three_Level_Menu(menu):

while True:

for k in menu:print(k)

key = input('>>>')

if key == 'q':return 'q'

elif key == 'b': # 退出本轮循环(递归函数造就了一个循环体)break

elif key in menu:

ret = Three_Level_Menu(menu[key])

if ret == 'q':

return 'q' # ① 回归到最后一层时, 没有key == 'q'为True的情况, 所以会return一个'q'(没有设置接受的变量), 然后结束整个函数; ② 如果ret !='q', 并且key不在当前字典的键里面, 那么重新开始本轮循环(递归函数造就了一个循环体)

Three_Level_Menu(menu)

另一方法:

pres_dic = menu # 当前词典

prev_dic = [] # 用来存储之前已经查询的词典

print("下面是可供查询的地点:")

while True:

for key in pres_dic.keys():

print(key)

inp = input("请输入您要查询的地点, 输入b/B退回上一层, 输入q/Q退出查询:").strip()

if inp not in pres_dic.keys() and inp.lower() != 'b' and inp.lower() != 'q':

print("您输入的地点不存在, 请重新输入!")

continue

if inp in pres_dic.keys():

prev_dic.append(pres_dic)

pres_dic = pres_dic[inp] # 然后开始新一轮的循环

if inp.lower() == 'b':

if prev_dic != []: # 等价于if prev_dic:

pres_dic = prev_dic[-1] # 当前词典编程之前已经查询的词典列表的最后一个

del prev_dic[-1] # # 用来存储之前已经查询的词典列表去掉最后一个元素

else:

print("没有更大级别的地点了!")

if inp.lower() == 'q':

break

8 ● 面试真题

# 提取各个fields对应的数据

data={"time":"2016-08-05T13:13:05",

"some_id":"ID1234",

"grp1":{ "fld1":1,"fld2":2},

"xxx2":{ "fld3":0,"fld5":0.4},

"fld6":11,

"fld7":{"fld100": 0, "fld500": 0.4},

"fld46":8}

#fields:由"|"连接的以"fld"开头的字符串,如:fld2|fld3|fld7|fld19

# 解法1:

def select(data,fields):

result = {}

field_lst = fields.split('|')

for key in data:

if key in field_lst:

result[key] = data[key]

if type(data[key]) == dict: # 不要写成elif, 否则, "fld100"对应的数据无法提取出来

res = select(data[key],fields)

result.update(res)

return result

# 解法2:

def select(data,fields,result = {}):

field_lst = fields.split('|')

for key in data:

if key in field_lst:

result[key] = data[key]

if type(data[key]) == dict: # 不要写成elif, 否则, "fld100"对应的数据无法提取出来

select(data[key], fields)

return result

fields = 'fld2|fld3|fld7|fld19|fld100'

ret = select(data,fields)

print(ret) # {'fld2': 2, 'fld3': 0, 'fld7': {'fld100': 0, 'fld500': 0.4}, 'fld100': 0}

●