python递归二

上一节我们简单得接触了递归得概念，这次我们再次探讨一下递归。

递归在实现的过程中，会被限制最多层次，本质原因是什么呢。

原因就是python专门设置的一种机制用来防止无限递归造成Python溢出崩溃，默认的递归深度大约是900多，但是我们可以通过手工设置递归深度来解决这个问题。

import sys   
sys.setrecursionlimit(10000) #例如这里设置为一万

话说回来就是，每次调用一次函数，栈就会增加一层栈帧，每当函数返回，栈就会减小一层栈帧，由于栈的大小不是无限的，所以递归调用的次数过多，就会导致栈溢出。

下面我们用研究一下递归的实现原理。

举个例子：

def calc(n):
    v = int(n/2)
    if v == 0:
        return
    print(v)
    calc(v)

我们看一下运行结果

>>>calc(10)
5
2
1

很容易理解这个结果是怎么出来的，下面我们在探讨一个问题

def calc(n):
    v = int(n/2)
    if v == 0:
        return
    print(v)
    calc(v)
    print(v)

那么这次调用的结果是什么呢？

>>>calc(10)
5
2
1
1
2
5

为什么是这样的输出结果呢， 5 2 1的输出我们是很容易理解的，为什么在calc(v)之后再次print(v)会反着输出一遍呢，我们思考一下。

我们之前说过，递归的调用每一层结束以后不会退出，而是堆到栈里面去，所以，在这个函数中，第一次调用：v1=5；第二次调用：v2=2；第三次调用：v3=1；第四次调用：v4=0 递归调用停止，第四层结束，此时程序回到了第三层调用第四层的地方，所以会print(v3),然后第三层结束，以此类推...

由此我们可以总结出递归的特点：

1. 正确的递归必须有一个结束条件
2. 每一次递归的调用必须离结束条件越来越近
3. 递归效率不高，递归层次过多会导致栈溢出