python递归函数及二分法查找

时间:2022-04-16 03:32:48

函数的递归: 在一个函数的内部调用自己

python递归函数及二分法查找
 1 死循环: 可以无限循环,不会停止
 2 while True:
 3     print('我不是递归')
 4  
 5 递归: 不是死循环,有最大循环深度
 6 def story():
 7     print('我是递归')
 8     story()
 9 story()
10 超过了递归的最大深度报错
11 RecursionError: maximum recursion depth exceeded while calling a Python object
python递归函数及二分法查找

官网上 源码中设置的递归深度: 1000
自己实际测试递归深度: 998

python递归函数及二分法查找
 1 n = 0
 2 def func():
 3     global n
 4     n += 1
 5     print(n)
 6     func()
 7 func()
 8 import sys
 9 print(sys.getrecursionlimit())    #查看递归的最大深度
10 
11 如果你的递归每次都要超过限制 不适合用递归来解决
12 为什么要有限制? 内存消耗的保护机制
13 设置递归的最大深度
14 import sys
15 sys.setrecursionlimit(1000000)
16 
17 n = 0
18 def func():
19     global n
20     n += 1
21     print(n)
22     func()
23 func()
python递归函数及二分法查找

总结
1.递归函数的定义 :一个函数在执行的过程中调用了自己
2.递归在python中的最大深度 : 1000/998
3.递归的最大深度是可以自己修改的,但是不建议你修改

python递归函数及二分法查找
 1 案例(遍历树形结构)
 2 import os
 3 def func(lujing,n):
 4     lst = os.listdir(lujing)    #打开文件夹,列出该文件夹中的所有文件及目录
 5     for i in lst:               #循环文件夹中的所有名字,i相当于文件名
 6         path = os.path.join(lujing,i)   #拼接循环的文件名路径
 7         # print(path)
 8         if os.path.isdir(path): #判断拼接后的路径是否是目录
 9             print('\t'*n,i)       #如果是目录就打印,n等于几就是几个tab键分隔
10             func(path,n+1)          #然后再次调用自己,在重复上面的操作,
11         else:
12             print('\t'*n,i)       #如果不是目录,就打印文件名
13 func('E:/test/',0)  #0为分层间隔
python递归函数及二分法查找

二分法查找主要的作用就是查找元素
数据规则: 掐头结尾取中间,必须是有序序列,数据量越大,效率约明显(百万级数据集)

python递归函数及二分法查找
 1 lst = [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]
 2 print(len(lst))
 3 n = int(input('<<<<:'))
 4 start = 0
 5 end = len(lst) -1
 6 count = 0
 7 while start <= end:
 8     mid = (start + end) // 2
 9     count+= 1
10     if n > lst[mid]:
11         start = mid +1
12     elif n < lst[mid]:
13         end = mid -1
14     else:
15         print('存在')
16         break
17 else:
18     print('不存在')
19 print('查找了%s次'%count)
20 
21 方法2
22 lst = [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]
23 def func(n,lst):
24     start = 0
25     end = len(lst) -1
26     # count = 0
27     if lst != []:
28         mid = (start + end) //2
29         if n > lst[mid]:
30             func(n,lst[mid+1:])
31         elif n < lst[mid]:
32             func(n,lst[:mid])
33         else:
34             print('存在')
35             return
36     else:
37         print('不存在')
38         return
39 n = int(input('<<<:'))
40 func(n,lst)
41 
42 方法3
43 lst = [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]
44 def func(n,lst,start,end):
45     if start <= end:
46         mid = (start + end) //2
47         if n > lst[mid]:
48             start = mid + 1
49             return func(n,lst,start,end)
50         elif n < lst[mid]:
51             end = mid - 1
52             return func(n,lst,start,end)
53         else:
54             print('找到了')
55             return mid
56     else:
57         print('找不到')
58         return -1
59 n = int(input('<<:'))
60 ret = func(n,lst,0,len(lst)-1)
61 print(ret)
62 
63 #最快的查找
64 lst = [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]
65 new_lst = []
66 for i in range(88):
67     new_lst.append(0)
68 for i in lst:
69     new_lst[i] = 1
70 print(new_lst)
71 i = int(input('<<<:'))
72 if new_lst[i] == 0:
73     print('存在')
74 else:
75     print('不存在')
python递归函数及二分法查找

 

 

 

 

 

 

 

 

 

# me : yuan 比我大2岁
# yuan : wusir 比我大2岁
# wusir : 宝元 比wusir大2岁
# 宝元 : alex比宝元大2岁

# me,yuan,wusir,宝元,alex
# alex 18
# 我多大?

# n = 1,age = q(n+1) -2
# n = 2,age = q(n+1) -2
# n = 3,age = q(n+1) -2
# n = 4,age = q(n+1) -2
# n = 5,age = 18

def q(n):
    if n == 1:
        age = q(n + 1) - 2
        return age
    elif n == 2:
        age = q(n + 1) - 2
        return age
    elif n == 3:
        age = q(n + 1) - 2
        return age
    elif n == 4:
        age = q(n + 1) - 2
        return age
    elif n == 5:
        return 18
ret = q(1)
print(ret)

# return 能够帮助你停止递归,并且把最内层的结果一层一层的返回到最外层
# 在最内层函数的返回值,返回的时候永远是离最内层最近的上一层才能接收到返回值
执行过程:
def q(1):   #3 q(1)  #6 q(2)  #9 q(3)  #12 q(4)  #15 q(5)
    if 1 == 1:      #4 n等于1
        age = 12 - 2  #5 此时q(1+1)等于2等于q(n)
        return 10              #21 q(2-1),返回值等于12-2=10

def q(2):
    elif 2 == 2:    #7 符合条件
        age = 14 - 2  #8 q(2+1)等于3等于q(n),返回给q(n)
        return 12              #20 q(3-1),返回值等于14-2=12

def q(3):
    elif n == 3:            #10  符合条件
        age = 16 - 2  #11 q(3+1)等于4等于q(n),返回给q(n)
        return 14              #19 q(4-1),返回值等于16-2=14

def q(4):
    elif n == 4:            #13 符合条件
        age = 16     #14 q(4+1)等于5等于q(n),返回给q(n)
        return age              #18 q(5-1),返回值等于18-2=16

def q(5):
    elif n == 5:            #16 符合条件
        return 18               #17 返回值为18

#def q(n):
#    if n < 5:
#        age = q(n + 1) - 2
#        return age
#    elif n == 5:
#        return 18
ret = q(1)  #2      #因为这个获取的是q(1)的返回值,而q(1)返回值为10=ret获取返回值10
print(ret)  #打印ret返回值