递归函数[通俗易懂]

大家好，又见面了，我是你们的朋友全栈君。

如果一个函数在内部调用自身，这个函数就叫做递归函数

递归函数的简单定义如下：

def recursion():
    return recursion()

这只是一个简单的定义，什么也做不了。

当然，你可以尝试会发生什么结果，理论上会永远运行下去，但实际操作时发现不一会儿程序就报错了，因为每次调用函数都会用掉一点内存，在足够多的函数调用发生后，空间几乎被占满，程序就会报错。

RecursionError: maximum recursion depth exceeded
#超过最大递归深度

这类递归被称为无穷递归(infinite recursion),理论上永远都不会结束，当然，我们需要能实际做事情的函数，有用的递归函数应该满足如下条件：

（1）当函数直接返回值时有基本实例（最小可能性问题）

（2）递归实例，包括一个或多个问题最小部分的递归调用

使用递归的关键在于将问题分解为小部分，递归不能永远进行下去，因为它总是以最小可能性问题结束，而这些问题又存储在基本实例中。

函数调用自身怎么实现呢？？

其实函数每次被调用时都会创建一个新的命名空间，也就是当函数调用‘自己’时，实际上运行的是两个不同的函数（也可以说一个函数具有两个函数的命名空间）。

我们来看一个递归示例，计算阶乘n！=1*2*3*4*5*……*n，用函数fact(n)表示，可以看出：

fact(n)=1*2*3*……*(n-1)*n=(n-1)!*n=fact(n-1)*n

所以，fact(n)可以表示为n*fact(n-1)，只有n=1时需要特殊处理

于是，fact(n)用递归方式定义函数如下：

def fact(n):
    if n==1:
        return 1
    return n*fact(n-1)

执行该函数：

>>> fact(1)
1
>>> fact(5)
120
>>> fact(100)
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000L

如果我们计算fact(5)，可以根据函数定义看到计算过程如下：

===> 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

由函数定义可知，递归函数的有点是定义简单，逻辑清晰。

理论上，所有递归函数都可以写成循环的方式，不过循环的逻辑不如递归清晰。

使用递归函数需要注意仿制栈溢出，在计算机中，函数调用通过栈（stack）这种数据结构实现的。每当进入一个函数调用，栈就会增加一层栈帧，每当函数返回，栈就会减一层栈帧，忧郁栈的大小不是无线的，因此递归调用的次数过多会导致栈溢出。可以试试fact(1000),执行结果如下：

RecursionError: maximum recursion depth exceeded in comparison

由执行结果看到，执行出现异常，异常提示超过最大递归深度。

那么怎么解决这个问题呢？

首先我们可以通过修改最大递归深度来增加递归深度。通过sys模块的setrecursionlimit()方法来修改。

import sys
sys.setrecursionlimit(2000)#这样就可以增加最大递归深度

但是这样也治标不治本，如果递归次数太多，那就说明这个问题就不适合用递归来解决。

还有一种方法，就是通过尾递归优化，事实上尾递归和循环的效果一样，把循环看成一种特殊尾递归函数也是可以的。

尾递归是指在函数返回时只能调用函数本身，return语句不能包含表达式，这样，编译器或解释器就可以对尾递归进行优化，使递归本身无论调用多少次都只占用一个栈帧，从而避免栈溢出的情况。

由于上面的fact(n)函数return n*(n-1)引入了乘法表达式，因此不是尾递归，要改成尾递归方式需要多一点代码，主要是把每一步乘积传入递归函数（通过把乘积结果传入函数参数的方式），看如下函数定义方式：

def fact(n,ret=1):
    if n==0:
        return ret
    return fact(n-1,ret=ret*n)
print(fact(5))#输出120

可以看到return fact(n-1,ret=ret*n)仅返回函数本身，n-1和ret=ret*n在函数调用前就会被计算，不影响函数的调用。

尾递归调用时，如果做了优化，栈不会增长，因此，无论多少次调用也不会导致栈溢出。

遗憾的是，大多数编程语言没有针对尾递归做优化，Python解释器也没有做优化，所以，即使把上面的fact(n)函数改成尾递归方式，也会导致栈溢出。

def fact(n,ret=1):
    if n==0:
        return ret
    return fact(n-1,ret=ret*n)
print(fact(1000))
#输出
RecursionError: maximum recursion depth exceeded in comparison

但是可以通过装饰器方法手动进行尾递归优化，这里暂不叙述，详细方法百度

递归与三级菜单：

menu = {
    '北京': {
        '海淀': {
            '五道口': {
                'soho': {},
                '网易': {},
                'google': {}
            },
            '中关村': {
                '爱奇艺': {},
                '汽车之家': {},
                'youku': {},
            },
            '上地': {
                '百度': {},
            },
        },
        '昌平': {
            '沙河': {
                '老男孩': {},
                '北航': {},
            },
            '天通苑': {},
            '回龙观': {},
        },
        '朝阳': {},
        '东城': {},
    },
    '上海': {
        '闵行': {
            "人民广场": {
                '炸鸡店': {}
            }
        },
        '闸北': {
            '火车战': {
                '携程': {}
            }
        },
        '浦东': {},
    },
    '山东': {},
}

def threeLM(dic):
     while True:
         for k in dic:print(k)
         key = input('input>>').strip()
         if key == 'b' or key == 'q':return key
         elif key in dic.keys() and dic[key]:
             ret = threeLM(dic[key])
             if ret == 'q': return 'q'
 
threeLM(menu)

#会迷惑的一个地方就是当输入b和q时，返回key(此时key=b或q)是返回给上一次return的地方，

递归函数实现三级菜单

l = [menu]
while l:
    for key in l[-1]:print(key)
    k = input('input>>').strip()   # 北京
    if k in l[-1].keys() and l[-1][k]:l.append(l[-1][k])
    elif k == 'b':l.pop()
    elif k == 'q':break

用堆栈实现的三级菜单

二分查找法

lis=[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]


def find(aim,li,start=0,end=None):
    end=len(li) if end is None else end
    middle=(end-start)//2+start
    if start<=end:
        if li[middle]>aim:
            return find(aim,li,start=start,end=middle-1)
        elif li[middle]<aim:
            return find(aim,li,start=middle+1,end=end)
        else:
            return middle
    else:
        return 'not find'
print(find(16,lis))