一. 递归
在函数中调用函数本身, 就是递归
prthon中递归的最大深度是998
def func(n):
print(n)
n += 1
func(n)
func(1)
递归的应用:我们可以使用递归来遍历各种树形结构, 比如我们的文件夹系统, 可以使用递归来遍历该文件夹中的所有文件
import os
def func(lujing, n):
lst = os.listdir(lujing) # os.listdir() 打开文件夹, 把该文件夹内所有的文件名装到列表lst
for el in lst: # 遍历列表, 拿到每一个文件名
path = os.path.join(lujing, el) # 还原 文件名 的 路径
# path = lujing + "\" + el
# print(path)
if os.path.isdir(path): # 判断该路径下的文件是否是 文件夹
print(" " * n, el) # 打印文件名
func(path, n+1) # 如果是文件夹, 再次 执行func函数, 打开该文件夹
else:
print(" " * n, el) # 如果不是文件夹, 直接打印文件名
func("d:红蜘蛛", 0)
二. 二分查找
每次查找能删除一般的数据, 查找效率很高, 但是局限性比较大, 必须是有序序列才可以使用二分查找
1. 普通二分法查找
lst = [3, 15, 26, 37, 48, 59, 61, 76, 89, 92]
def binarysearch(n, lst):
min = 0
max = len(lst) - 1
while min <= max:
mid = (min + max) // 2
if n > lst[mid]:
min = mid + 1
elif n < lst[mid]:
max = mid - 1
else:
return mid
else:
return -1
num = int(input("请输入一个数:"))
f = binarysearch(num, lst)
print(f)
2. 另类递归的二分法, 很难计算出索引, 列表在变,用切片来切列表
lst = [3, 15, 26, 37, 48, 59, 61, 76, 89, 92]
def binarysearch(n, lst):
min = 0
max = len(lst) - 1
mid = (min + max) // 2
while lst != []:
if n > lst[mid]:
lst = lst[mid + 1 :]
return binarysearch(n, lst)
elif n < lst[mid]:
lst = lst[: mid] # 左闭右开
return binarysearch(n, lst)
else:
print("存在")
break
else:
print("不存在")
num = int(input("请输入要查找的数字:"))
binarysearch(num, lst)
3. 普通递归二分法, 计算思想和二分法一致
lst = [3, 15, 26, 37, 48, 59, 61, 76, 89, 92]
def binarysearch(n, lst, min, max):
mid = (min + max) // 2
if min <= max:
if n > lst[mid]:
min = mid + 1
return binarysearch(n, lst, min, max)
elif n < lst[mid]:
max = mid - 1
return binarysearch(n, lst, min, max)
else:
return mid
else:
return -1
num = int(input("请输入要查找的数:"))
f = binarysearch(num, lst, 0, len(lst) - 1)
print(f)
4. 一种特殊的查找方法
已知列表中的最大数值, 查找某个数是否存在
lst = [3, 15, 26, 37, 48, 59, 61, 76, 89, 92]
def func():
while 1:
n = int(input("请输入要查找的数字:"))
if n <= 92 and n >= -93:
new_list = []
for i in range(93):
new_list.append(0)
for i in range(len(lst)):
new_list[lst[i]] = 1
if new_list[n] == 1:
print("存在")
else:
print("不存在")
else:
print("输入有误")
continue
func()