递归
自己调用自己
递归的入口(参数)和出口(return)
树状结构的遍历
import os
def func(lujing, n): # "d:/a/"
lst = os.listdir(lujing) # 打开文件夹. 列出该文件夹内的所有文件名
for el in lst: # el是文件的名字. b, c
path = os.path.join(lujing, el) # 还原文件路径"d:/a/b"
if os.path.isdir(path): # 判断路径是否是文件夹
print("..." * n,el) # 显示文件夹的名字
func(path, n + 1) # 在来一次
else:
print("\t" * n,el) # 显示文件
func("d:/a", 0)二分法
掐头结尾取中间
查找效率非常的高
不使用递归进行二分法
lst = [1,3,5,7,12,36,68,79,132,345,567]
n = int(input("请输入一个数"))
left = 0
right = len(lst) - 1
while left <= right:
mid = (left + right)//2
if n > lst[mid]:
left = mid + 1
elif n < lst[mid]:
right = mid - 1
else:
print("存在")
break
else:
print("不存在")用递归进行二分法的两种方法
1)第一种
def func(n, lst):
left = 0
right = len(lst) - 1
if lst != []:
mid = (left + right)//2
if n > lst[mid]:
func(n, lst[mid+1:]) # 改变列表
elif n < lst[mid]:
func(n, lst[:mid])
else:
print("找到了")
return
else:
print("没找到")
return
n = int(input("请输入你要查找的数:"))
func(n, [1,3,5,7,12,36,54,68,79,85,92,106]) 2)第二种
def func(n, lst, left, right):
if left <= right:
mid = (left + right) // 2
if n > lst[mid]:
left = mid + 1
return func(n, lst, left, right)
elif n < lst[mid]:
right = mid - 1
return func(n, lst, left, right) # 递归如果有返回值. 所有调用递归的地方必须写return
else:
print("找到了")
return mid # 返回上一个调用函数的值
else:
print("找不到")
return False
n = int(input("请输入你要查找的数:"))
lst = lst = [1,3,5,7,12,36,68,79,125,343,485,875,1948]
ret = func(n, lst, 0, len(lst)-1)
print(ret)
