递归

一.递归：可以理解为一个函数不断的调用自己

def recursion(n):
    print(n)　　　　　#每调用一次后打印n的值
    recursion(n+1)　 #n的值加一后再次调用

recursion(1)

结果：

1
2
3
...
996
Traceback (most recent call last):
  File "D:/python/new/charter3/test.py", line 4, in <module>
    recursion(1)
  File "D:/python/new/charter3/test.py", line 3, in recursion
    recursion(n+1)
  File "D:/python/new/charter3/test.py", line 3, in recursion
    recursion(n+1)
  File "D:/python/new/charter3/test.py", line 3, in recursion
    recursion(n+1)
  [Previous line repeated 993 more times]
  File "D:/python/new/charter3/test.py", line 2, in recursion
    print(n)
RecursionError: maximum recursion depth exceeded while calling a Python object

发现会报错，这是因为递归是有默认次数的，循环1000次就会达到最大次数从而报错，这是因为每次递归的值都存储在内存里，设置最大次数可以防止内存被撑爆。当然也可以通过一些方法提高递归次数

import sys
sys.setrecursionlimit(1500)　　#设置递归的次数为1500次

 二.递归的特性：

例：

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

结果：

5
2
1
0
1
2
5

开始n的值为10，执行一次进入了第一层n=5，再执行一次进入第二层，以此类推，一直进到第四层。当遇到符合的条件return时，此时递归会一层层的从第四层向外退出。

三.递归的作用

如：斐波那契数列、汉诺塔、二分查找等等。

例1.阶乘

def f(n):
    if n == 1:
        return 1
    return n * f(n-1)
print(f(20))

 例2.二分法查找数组元素

def func1(lis, num):
    if len(lis) >= 1:
        a = int(len(lis)/2)
        if lis[-1] < num:
            print("查无此数")
            exit()
        elif lis[0] > num:
            print("查无此数")
            exit()
        if lis[a] > num:
            L = lis[:a]
            func1(L, num)
        elif lis[a] < num:
            L = lis[a:]
            func1(L, num)
        else:
            print("已寻找到此数")
    else:
        print("无输入元素")
L1 = [21,56,56,2656,16,56523,3265,232,323232,3]
L1.sort()
func1(L1, int(input(">>>")))