递归
- 在函数中调用函数本身. 就是递归
- 在python中递归的深度最大到997
递归的应用:
我们可以使用递归来遍历各种树形结构, 比如我们的文件夹系统. 可以使用递归来遍历该文件夹中的所有文件
def func(count): print("我是谁,我在哪里" + str(count)) func(count + 1) func(1)
结果：
我是谁,我在哪里1 我是谁,我在哪里2 ...... 我是谁,我在哪里996 我是谁,我在哪里997
遍历文件夹
import os filePath = "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)
结果:
10 5 2 1
递归特性:
- 必须有一个明确的结束条件
- 每次进入更深一层递归时，问题规模相比上次递归都应有所减少
- 递归效率不高，递归层次过多会导致栈溢出（在计算机中，函数调用是通过栈（stack）这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以，递归调用的次数过多，会导致栈溢出）
def calc(*numbers): sum = 0 for n in numbers: sum = sum + n * n return sum print(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 fact_iter(num - 1, num * product)
可以看到，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 --> C A --> B C --> B A --> C B --> A B --> C A --> C
二分查找
lst = [11, 22, 33, 44, 55, 66, 77] n = 66 left = 0 right = len(lst) - 1 count = 1 while 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 + 1 else: 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
