python--递归、遍历文件夹、二分查找（python递归二分法查找）

python--递归、遍历文件夹、二分查找（python递归二分法查找）

递归

在函数中调用函数本身. 就是递归在python中递归的深度最大到997

递归的应用:我们可以使用递归来遍历各种树形结构, 比如我们的文件夹系统. 可以使用递归来遍历该文件夹中的所有文件

def func(count): print("我是谁,我在哪里" + str(count)) func(count + 1)func(1)

结果：

我是谁,我在哪里1我是谁,我在哪里2......我是谁,我在哪里996我是谁,我在哪里997

遍历文件夹

import osfilePath = "f:\\CJMDXTtest\\"def read(filePath, n): it = os.listdir(filePath) # 打开文件夹 for el in it: # 拿到路径 fp = os.path.join(filePath, el) # 获取到绝对路径 if os.path.isdir(fp): # 判断是否是文件夹 print("\t" * n, el) read(fp, n + 1) # 又是文件夹. 继续读取内部的内容 递归入口 else: print("\t" * n, el) # 递归出口read(filePath, 0)

在函数内部，可以调用其他函数，如果一个函数在内部调用自身，这个函数就是递归函数

def calc(n): print(n) if int(n / 2) == 0: return n return calc(int(n / 2))calc(10)

结果:

10521

递归特性:

必须有一个明确的结束条件每次进入更深一层递归时，问题规模相比上次递归都应有所减少递归效率不高，递归层次过多会导致栈溢出（在计算机中，函数调用是通过栈（stack）这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以，递归调用的次数过多，会导致栈溢出）

def calc(*numbers): sum = 0 for n in numbers: sum = sum + n * n return sumprint(calc(2, 4))

结果：

20

可以传多个参数，计算平方相加，接收的是一个元组

def fact(n): if n == 1: return 1 return n * fact(n - 1)print(fact(5))

结果：

120

递归函数，计算他的阶乘，过程如下===> fact(5)===> 5 * fact(4)===> 5 * (4 * fact(3))===> 5 * (4 * (3 * fact(2)))===> 5 * (4 * (3 * (2 * fact(1))))===> 5 * (4 * (3 * (2 * 1)))===> 5 * (4 * (3 * 2))===> 5 * (4 * 6)===> 5 * 24===> 120

尾递归是指，在函数返回的时候，调用自身本身，并且，return语句不能包含表达式。这样，编译器或者解释器就可以把尾递归做优化，使递归本身无论调用多少次，都只占用一个栈帧，不会出现栈溢出的情况。

def fact_iter(num, product): if num == 1: return product return

可以看到，return fact_iter(num - 1, num * product)仅返回递归函数本身，num - 1和num * product在函数调用前就会被计算，不影响函数调用。fact(5)对应的fact_iter(5, 1)的调用如下：===> fact_iter(5, 1)===> fact_iter(4, 5)===> fact_iter(3, 20)===> fact_iter(2, 60)===> fact_iter(1, 120)===> 120

def move(n, a, b, c): if n > 1: move(n - 1, a, c, b) print(a, '-->', c) if n > 1: move(n - 1, b, a, c)move(3, 'A', 'B', 'C')

结果：

A --> CA --> BC --> BA --> CB --> AB --> CA --> C

二分查找

lst = [11, 22, 33, 44, 55, 66, 77]n = 66left = 0right = len(lst) - 1count = 1while left <= right: middle = (left + right) // 2 if n > lst[middle]: left = middle + 1 elif n < lst[middle]: right = middle - 1 else: print("存在") print(middle) break count = count + 1else: print("不存在")

结果：

存在5

lst = [11, 22, 33, 44, 55, 66, 77, 88, 99]def binary_search(left, right, n): middle = (left + right) // 2 if left > right: return -1 if n > lst[middle]: left = middle + 1 elif n < lst[middle]: right = middle - 1 else: return middle return binary_search(left, right, n)print(binary_search(0, len(lst) - 1, 66))

结果：

5

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。