当前位置：首页 > news >正文

python全栈开发从入门到放弃之递归函数的调用

news 来源：原创 2024/5/2 21:43:27

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

 1 def age(n):
 2     if n == 1:
 3         return 40     
 4     else:
 5         ret = age(n-1)   #先递推后递归 
 6         return ret + 2
 7 ret=age(5)
 8 print(ret)
 9 
10 48
#结束递归的标志：return

递归实现三级菜单

 1 menu = {
 2     '北京': {
 3         '海淀': {
 4             '五道口': {
 5                 'soho': {},
 6                 '网易': {},
 7                 'google': {}
 8             },
 9             '中关村': {
10                 '爱奇艺': {},
11                 '汽车之家': {},
12                 'youku': {},
13             },
14             '上地': {
15                 '百度': {},
16             },
17         },
18         '昌平': {
19             '沙河': {
20                 '老男孩': {},
21                 '北航': {},
22             },
23             '天通苑': {},
24             '回龙观': {},
25         },
26         '朝阳': {},
27         '东城': {},
28     },
29     '上海': {
30         '闵行': {
31             "人民广场": {
32                 '炸鸡店': {}
33             }
34         },
35         '闸北': {
36             '火车战': {
37                 '携程': {}
38             }
39         },
40         '浦东': {},
41     },
42     '山东': {},
43 }
44 
45 
46 def threeLM(menu):
47     for i in menu:
48         print(i)
49     key = input("please input name:")
50     if key in menu:
51         threeLM(menu[key])
52 
53 
54 
55 threeLM(menu)

递归二分算法

 1 如果一个数 可以整除2 就整除
 2 不能整除就*3+1
 3 def func(num):
 4     print(num)
 5     if num == 1:
 6         return
 7     if num %2 == 0:
 8         num = num //2
 9     else:
10         num = num * 3 + 1
11     func(num)
12 
13 func(5)
14 
15 输出结果：

 1 l = [2,3,5,10,15,16,18,22,26]
 2 def find(l,aim): #l:列表 aim：要找的
 3     mid = len(l)//2  #计算中点
 4     if l[mid] > aim: #判断中间位置的值和目标值的大小关系
 5         new_l = l[:mid] #[16,18] = [16,18,22,26][:mid]
 6         return find(new_l,aim)
 7     elif l[mid] < aim:#判断中间位置的值和目标值的大小关系
 8         new_l = l[mid+1:]
 9         return find(new_l,aim)
10     else:
11         return l[mid]
12 print(find(l,16))
13 
14 
15 16