首页 > > 网络编程 > 其它 >

递归与二分法

2018-12-14 08:38:31来源：博客园阅读 ()

递归

自己调用自己

递归的入口(参数)和出口(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)