python基础十五之递归函数

　　递归函数，在函数中调用自身函数，就会形成一个递归函数。例如：

def recursion(n):
    n += 1
    print(n)
    recursion(n)

　　由于递归函数的结构，在函数调用时，它会一直调用自身，而函数调用是会占用内存的，所以为了保护内存，python就限制了递归函数的递归深度，默认的限制深度为998。调用上面的函数函数它只能打印到998然后报错。

def recursion(n):
    n += 1
    print(n)
    recursion(n)

recursion(0)

# RecursionError: maximum recursion depth exceeded while calling a Python object
# 超出了递归的最大深度

 　　而这个限定是可以进行设定的，通过sys.setrecursionlimit()可以修改。

import sys
sys.setrecursionlimit(10000)

　　由此可知，需要递归多次的处理的将不再适合使用递归。

　　递归函数的优缺点：

　　　　优点：在运用合理的情况下可以简化代码

　　　　缺点：多次递归占用内存

　　递归函数的应用：算法

　　算法，人类在处理问题上，会发现和发明一些简单有效的计算方法，将这些思想应用于计算机后就产生了很多高效简单的计算方法。这个就是算法，它能使计算机拥有更高效的计算能力。

　　计算机发展至今，已经出现了很多优秀的算法，通过学习和了解这些算法，我们将能写出更好更实用的新算法。这里就说下二分查找法！

　　通过二分列表的索引，递归比较列表中间值和查找值的大小来快速的找到目标。二分法只能用于有序的对象！

def dichotomy(lis, aim, start=0, end=None):
    end = len(lis) if end is None else end
    index = (end - start) // 2 + start
    if start < end:
        if lis[index] < aim:
            return dichotomy(lis, aim, start=index + 1, end=end)
        elif lis[index] > aim:
            return dichotomy(lis, aim, start=start, end=index - 1)
        else:
            return index
    else:
        return '找不到！'


L = [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]
ret = dichotomy(L, 100)
print(ret)