递归

• 在函数中调用函数本身. 就是递归
• 在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