递归与二分法
- 2020 年 1 月 20 日
- 筆記
递归
自己调用自己
递归的入口(参数)和出口(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)
