初识递归

• 递归的定义：在一个函数内部调用这个函数本身
• 为了防止递归无限进行，一般会指定一个退出条件
• 递归的最大深度：997 ```python def foo(n): print(n) n += 1 foo(n)

foo(1)

最大深度997是python为了程序内存优化设置的一个默认值，我们可以通过一些手段去修改它：
```python
import sys
print(sys.setrecursionlimit(10000))
def foo(n):
    print(n)
    n += 1
    foo(n)
foo(1)

将python允许的递归深度设置为了1w，至于实际可以达到的深度就取决于计算机的性能了。
不推荐修改这个默认的递归深度，因为如果用997层递归都没有解决的问题是不适合使用递归来解决。

汉诺塔问题

从左到右 A B C 柱 大盘子在下, 小盘子在上, 借助B柱将所有盘子从A柱移动到C柱, 期间只有一个原则:
大盘子只能在小盘子的下面.

我们只需要考虑如果有64层，先将A柱上的63层移动到B柱上，然后将A柱的第64个移动到C柱上，然后
将B柱上的63层移动到C柱上即可。

那怎么把63层都移到B柱上，这个问题可以用上面相同的方法解决。

def move(n,a,b,c):
    if n == 1:
        print(a,'->',c)
    else:
        # 将n-1个盘子从a --> b
        move(n-1,a,c,b)
        # 将剩余的最后一个盘子从a --> c
        print(a,'->',c)
        # 将剩余的n-1个盘子从 b --> c
        move(n-1,b,a,c)
n = int(input('请输入汉诺塔的层数：'))
move(n,'A','B','C')

二分查找

# 递归：二分法
list1 = [2,3,5,10,15,16,18,22,26,30,32,35,41,42,43,55,56,66,67,69,72,76,82,83,88]
# mid_find(要找的数，查找范围，起始下标，终止下标)
def mid_find(num, l, start, end):
    length = start + end
    # mid是中间值在列表中的下标
    mid = length // 2
    if num == l[mid]:
        print("找到了")
        return
    elif start + 1 == end:
        print("没找到")
    elif num < l[mid]:
        end = mid - 1
        mid_find(num, l, start, end)
    elif num > l[mid]:
        start = mid + 1
        mid_find(num, l, start, end)
mid_find(65, list1, 0, len(list1) - 1)
mid_find(65, list1, 0, len(list1) - 1)
# 运行结果
没找到
找到了