13. 函数-递归函数

一、定义

​ 在函数中调用函数本身，应用在树形结构中，比如遍历文件；在python中最大的递归次数是1000，但不能达到1000，根据代码、操作系统特性 997-998之间。

1. 遍历文件

// 文件遍历

import os

# 定义一个层数，打印是按照树形打印
def func(file_path, ceng):  
    # 调用os模块打开所给路径下的文件夹
    lst = os.listdir(file_path)
    
    # 遍历得到的文件夹列表
    for file in lst:  
        # 调用os模块将列表中的每一个元素域所给路径拼接全路径
        file_path_full = os.path.join(file_path, file)  
        # 判断全路径得到的是否为文件夹
        if os.path.isdir(file_path_full):  
            # 先将遍历的元素打印,第一层ceng为0不需制表
            print('	'*ceng, file)  
            # 第二层文件夹内容需制表，层加一# 第二层文件夹内容需制表，层加一
            func(file_path_full, ceng+1)  
        else:
            # 第一层ceng为0不需制表
            print('	'*ceng, file)  
    else:
        return
    
# 第一层是根，0不需制表
func('F:老男孩python', 0)  

import os

def read(filepath, n):
    # 获取到当前文件夹中的所有文件
	files = os.listdir(filepath) 
    # 遍历文件夹中的文件, 这里获取的只是本层文件名
 	for fi in files: 
        # 加入文件夹 获取到文件夹+文件
 		fi_d = os.path.join(filepath,fi) 
        # 如果该路径下的文件是文件夹
 		if os.path.isdir(fi_d): 
 			print("	"*n, fi)
            # 继续进行相同的操作
 			read(fi_d, n+1) 
 		else:
            # 递归出口，最终在这里隐含着return
 			print("	"*n, fi) 

#递归遍历目录下所有文件
read('../oldboy/', 0)

2. 二分查找

​ 二分查找. 每次能够排除掉⼀半的数据. 查找的效率非常⾼. 但是局限性比较⼤. 必须是有 序序列才可以使用二分查找 要求: 查找的序列必须是有序序列.

li = [1,2,3,53,4,5,6,7,8,9,43,45,768,1,54,65,778,56,2,3,455,75,98]
lis = sorted(li)
print(lis)  # 二分查找必须是有序序列
def func(lst, n):
    left = 0  # 定义左指针，指向第一个位置
    right = len(lst) - 1  # 定义右指针，指向最后一个位置

    while left <= right:  # 当左指针大于右指针（异位了->没找到跳出）当左侧等于右侧也是没找到
        mid = (left + right) // 2
        if n > lst[mid]:  # 要拿传入的数和中间值比较，如果比中间值大则次数在mid右侧，否则相反
            left = mid + 1  # n在右侧,把left移动到mid右边一个
        elif n < lst[mid]:
            right = mid -1  # n在右侧,把right移动到mid左边一个
        else:
            # print('找到了哦%s' % mid)
            return mid
    else:
        print('没有此元素')
print(func(lis, 90))