1. 递归
自己调用自己
递归的入口(参数) 和 出口(return)
树形结构的遍历
import os
def func(lujing, n):
lst = os.listdir(lujing) # 打开文件夹,列出所有文件
for el in lst: # el 每一个文件
path = os.path.join(lujing, el) # 还原路径
if os.path.isdir(path): # 判断是否是文件夹
print('\t'*n ,el)
func(path, n + 1)
else:
print('\t' * n, el)
func(r'E:\python_workspace_s18', 0)
2. 二分法
掐头结尾取中间
查找效率非常的高
# 二分法
lst = [1, 3, 5, 7, 13, 15, 17, 19, 21, 23, 27, 29, 31, 33, 39, 41, 43, 47, 49]
left = 0
right = len(lst) - 1
count = 1
n = int(input("请输入一个数:"))
while left <=right:
middle = (left + right) // 2
if n > lst[middle]:
left = middle + 1
elif n < lst[middle]:
right = middle - 1
else:
print('找到了')
print('循环次数为:%s' % count)
break
count += 1
else:
print('不存在')
# 递归实现:
lst = [1, 3, 5, 7, 13, 15, 17, 19, 21, 23, 27, 29, 31, 33, 39, 41, 43, 47, 49]
def func(s, lst):
left = 0
right = len(lst) - 1
if lst != []:
middle = (left + right) //2
if n > lst[middle]:
left = middle + 1
lst = lst[left:]
func(s, lst)
elif n < lst[middle]:
right = middle -1
lst = lst[:right]
func(s, lst)
else:
print('找到了')
return
else:
print('没有找到')
return
n = int(input('请输入一个数:'))
func(n, lst)
# 递归二
lst = [1, 3, 5, 7, 13, 15, 17, 19, 21, 23, 27, 29, 31, 33, 39, 41, 43, 47, 49]
def func(n, lst, left, right):
if left <= right:
middle = (left + right) // 2
if n > lst[middle]:
left = middle + 1
return func(n, lst, left, right)
elif n < lst[middle]:
right = middle - 1
return func(n, lst, left, right) # 递归如果有返回值. 所有调用递归的地方必须写return
else:
print("找到了")
return middle
else:
print('没有找到')
return -1
n = int(input('请输入一个数:'))
func(n,lst,0,len(lst)-1)
