1.递归效率低，需要在进入下一次递归时保留当前的状态，见51cto博客
解决方法是尾递归，即在函数的最后一步（而非最后一行）调用自动
但是python又没有尾递归，且对递归层级做了限制
必须有一个明确的结束条件
2.每次进入更深一层递归时，问题规模相比上次递归都应有所减少
3.递归效率不高，递归层次过多会导致栈溢出（在计算机中，函数调用是通过栈（stack）这种）
尾递归优化：http://egon09.blog.51cto.com/9161406/1842475
什么叫递归：
递归函数，在一个函数内调用自己
最大递归层数做了一个限制：997
最大层数限制是python默认的，可以做修改
但是不建议修改因为会占用电脑的内存
#猜alex的年龄
#alex比egon大两岁 alex = egon + 2
#egon比wuSir大两岁 egon = wusir + 2
#wusir比nezha大两岁 wusir = nezha + 2
#nezha比金鑫大两岁 金鑫 + 2
#金鑫40了
# 1.金鑫 age(1) = 40
# 2.哪吒 age(1) + 2
# 3.wusir age(2) + 2
# 4.egon age(3) + 2
# 5.alex age(4) + 2
def age(n):
if n == 1:
return 40
else:
ret = age(n-1) #先递推后递归
return ret + 2
ret=age(5)
print(ret) 48
#结束递归的标志：return
递归实现三级菜单
menu = {
'北京': {
'海淀': {
'五道口': {
'soho': {},
'网易': {},
'google': {}
},
'中关村': {
'爱奇艺': {},
'汽车之家': {},
'youku': {},
},
'上地': {
'百度': {},
},
},
'昌平': {
'沙河': {
'老男孩': {},
'北航': {},
},
'天通苑': {},
'回龙观': {},
},
'朝阳': {},
'东城': {},
},
'上海': {
'闵行': {
"人民广场": {
'炸鸡店': {}
}
},
'闸北': {
'火车战': {
'携程': {}
}
},
'浦东': {},
},
'山东': {},
}
def threeLM(menu):
for i in menu:
print(i)
key = input("please input name:")
if key in menu:
threeLM(menu[key])
threeLM(menu)
递归二分算法
如果一个数 可以整除2 就整除
不能整除就*3+1
def func(num):
print(num)
if num == 1:
return
if num %2 == 0:
num = num //2
else:
num = num * 3 + 1
func(num) func(5) 输出结果：
l = [2,3,5,10,15,16,18,22,26]
def find(l,aim): #l:列表 aim：要找的
mid = len(l)//2 #计算中点
if l[mid] > aim: #判断中间位置的值和目标值的大小关系
new_l = l[:mid] #[16,18] = [16,18,22,26][:mid]
return find(new_l,aim)
elif l[mid] < aim:#判断中间位置的值和目标值的大小关系
new_l = l[mid+1:]
return find(new_l,aim)
else:
return l[mid]
print(find(l,16)) 16