Python递归

在python中，如阶乘运算，函数的自身循环调用等叫做递归。
递归主要有递推和回溯两个阶段。
递归的效率低，需要在进入下一次递归时，保留当前的状态，解决方法是尾递归，即在函数的最后一步（而非最后一行）调用自己。但是python没有尾递归，且对递归层级做了限制
1.必须有一个明确的结束条件
2.每次进入更深一层递归时，问题规模相比山此递归应有所减少
3.递归效率不高，递归层次过多会导致栈溢出（在计算机中，函数调用是通过栈（stack）这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以递归调用的次数过多，会导致栈溢出）

在默认情况下，系统会对递归做层级的限制,默认是1000：

>>> import sys
>>> sys.getrecursionlimit()
1000

当然，我们也可以修改这个值：

>>> sys.setrecursionlimit(500)
>>> sys.getrecursionlimit()
500

当然不推荐修改。

递归的使用

循环和递归具有相似的功能，但是在有些场景下，我们无法指定循环的条件时，使用递归就能很好的是实现.
如，打印出列表中的所有数字：

a=[1,[2,[3,[4,[5,[6,[7,[8,[9,10,11],12]]]]]]]]

def list_num(list_n):
    for i in list_n:
        if type(i) is list:
            list_num(i)
        else:
            print(i)
list_num(a)

二分法

在使用递归对有序数列进行查找时，使用二分法可以极大的提高算法效率。二分法的的原理是每次都截取一半，在这一半中查找需要的值。这里使用递归：

a=[0, 1, 2, 3, 6, 7, 8, 9, 33, 44, 54, 66, 67, 878]

def findnum(num,l):
    print(l)
    if len(l)==1:
        if l[0] == num:
            print('find this num')
        else:
            print('not exist')
        return

    half_index=len(l)//2
    if num == l[half_index]:
        print('find this num')
        return
    elif num > l[half_index]:
        l=l[half_index:]
    elif num < l[half_index]:
        l=l[:half_index]
    findnum(num, l)   # 使用递归调用自身

findnum(34,a)