Python递归思想与代码实现
1， 递归思想
递归算法:递归(Recursion)，在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。
这是官方的解释，翻译成人话就是：
- 函数内部自己调用自己
- 函数必须有出口
函数自己调用自己很好理解，但什么是出口呢？我们知道，递归实际上是简化嵌套for循环的一种精简算法，所以在函数内部自己调用自己的过程就是在不短的循环，并改变函数传入的参数。如果没有不再执行自己调用自己的出口，那么递归就会陷入无限循环的无底洞。
出口通常是用return或if else语句避免再调用自己。
def recursion(n): print(n, "") if n > 0: recursion(n - 1) # 那么这就是一个出口，如果n <= 0了就会不再递归 else: print(n, '')recursion(5) # 外部调用结果就是：
5 4 3 2 1 0 0 # 这个是出口，在这个时候n = 0Process finished with exit code 0递归还有两个重要的思想，第一个我们要找到等价的运算式，也就是将大问题拆分成很多个可递归的小问题。
第二个：
- 递推：像上边递归实现所拆解，递归每一次都是基于上一次进行下一次的执行，这叫递推。
- 回溯：则是在遇到终止条件，则从最后往回返一级一级的把值返回来，这叫回溯。
听到这是不是有点懵，我们来通过下面阶乘的实例与代码实现来进一步理解这个思想。
2，递归求阶乘，代码实现与思想解析
首先先上代码：
def factorial(n): # 出口 if n == 1: return 1 else: return n * factorial(n-1)print(factorial(5))这段代码求出了5的阶乘，大家先试着理解。
其中出口就是在n - 1 = 1的时候，递归就开始了回溯。
我们看一下流程图：
n * factorial(n-1)是等价表达式。红色箭头是递推的过程，从1-2-3-4；绿色箭头是回溯的过程，从a-b-c-d；紫色箭头是参数的变化。我把每一个式子都分解了一下，我们可以发现最后真正输出的是最外层的return，回溯顺序是从最底层往上返回。
如果我们改一下代码，在每一次回溯的时候输出等价表达式的值：
def factorial(n): # 出口 if n == 1: return 1 # 递归内层 else: factor = n * factorial(n-1) print(factor) return factorprint(factorial(5))输出：
2624120120Process finished with exit code 0不难发现，第一个输出的2就是流程图中的a式的值，6是b式的值，24是c式的值，120就是d式也就是最外层返回的5的阶乘了。
通过此输出，也证明了回溯过程的实现。这样我们就可以利用此思想求斐波那契数列等等等。那么递归其实也是可以用for来实现的。
# 求5的阶乘num = 1for i in range(1,6): num *= iprint(num)3，栈溢出
递归效率不高，递归层次过多会导致栈溢出（在计算机中，函数调用是通过栈（stack）这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以，递归调用的次数过多，会导致栈溢出），此时程序会抛出错误：超出最大递归深度。
那么一般最大的深度是1000左右，我们可以通过sys的两个方法来设置最大深度和得到最大深度。
import sys# 得到最大的深度值print(sys.getrecursionlimit())# 设置最大深度为2000sys.setrecursionlimit(2000)4，运行速度
import sysimport timeprint(sys.getrecursionlimit())sys.setrecursionlimit(2000)start = time.time()def factorial(n): # 出口 if n == 1: return 1 # 递归内层 else: return n * factorial(n-1)print(factorial(1000))print(time.time() - start)我们通过time方法来获取运行的时间，发现大概在0.008s左右
而for循环实测在0.004秒左右，所以我们看到递归的缺点是资源占用和运行速度劣与for循环。
所以我们总结一下递归的缺点：
- 递归由于是函数调用自身，而函数调用是有时间和空间的消耗的--效率
- 递归中很多计算都是重复的，由于其本质是把一个问题分解成两个或者多个小问题，多个小问题存在相互重叠的部分，则存在重复计算--效率
- 调用栈可能会溢出，其实每一次函数调用会在内存栈中分配空间，而每个进程的栈的容量是有限的，当调用的层次太多时，就会超出栈的容量，从而导致栈溢出，强制设置最大深度会导致内存占用大--性能
优点：
- 简洁
- 在特殊情况下比for循环更加简洁，逻辑清晰。
4，建议
在使用for循环运算量并不太大时使用递归，在for循环逻辑太过于繁琐时使用递归。