Python递归思想与代码实现

1， 递归思想

递归算法:递归(Recursion)，在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。

这是官方的解释，翻译成人话就是：

• 函数内部自己调用自己
• 函数必须有出口 

函数自己调用自己很好理解，但什么是出口呢？我们知道，递归实际上是简化嵌套for循环的一种精简算法，所以在函数内部自己调用自己的过程就是在不短的循环，并改变函数传入的参数。如果没有不再执行自己调用自己的出口，那么递归就会陷入无限循环的无底洞。

出口通常是用return或if else语句避免再调用自己。

def recursion(n):
    print(n, "<===1====>")
    if n > 0:
        recursion(n - 1)
    # 那么这就是一个出口，如果n <= 0了就会不再递归
    else:
        print(n, '<===2====>')


recursion(5) # 外部调用

结果就是：

5 <===1====>
4 <===1====>
3 <===1====>
2 <===1====>
1 <===1====>
0 <===1====>
0 <===2====>  # 这个是出口，在这个时候n = 0

Process finished with exit code 0

递归还有两个重要的思想，第一个我们要找到等价的运算式，也就是将大问题拆分成很多个可递归的小问题。

第二个：

1. 递推：像上边递归实现所拆解，递归每一次都是基于上一次进行下一次的执行，这叫递推。
2. 回溯：则是在遇到终止条件，则从最后往回返一级一级的把值返回来，这叫回溯。

听到这是不是有点懵，我们来通过下面阶乘的实例与代码实现来进一步理解这个思想。

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 factor

print(factorial(5))

输出：

2
6
24
120
120

Process finished with exit code 0

不难发现，第一个输出的2就是流程图中的a式的值，6是b式的值，24是c式的值，120就是d式也就是最外层返回的5的阶乘了。

通过此输出，也证明了回溯过程的实现。这样我们就可以利用此思想求斐波那契数列等等等。那么递归其实也是可以用for来实现的。

# 求5的阶乘
num = 1
for i in range(1,6):
    num *= i
print(num)

3，栈溢出

递归效率不高，递归层次过多会导致栈溢出（在计算机中，函数调用是通过栈（stack）这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以，递归调用的次数过多，会导致栈溢出），此时程序会抛出错误：超出最大递归深度。

那么一般最大的深度是1000左右，我们可以通过sys的两个方法来设置最大深度和得到最大深度。

import sys


# 得到最大的深度值
print(sys.getrecursionlimit())
# 设置最大深度为2000
sys.setrecursionlimit(2000)

4，运行速度

import sys
import time
print(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循环。

所以我们总结一下递归的缺点：

1. 递归由于是函数调用自身，而函数调用是有时间和空间的消耗的--效率
2. 递归中很多计算都是重复的，由于其本质是把一个问题分解成两个或者多个小问题，多个小问题存在相互重叠的部分，则存在重复计算--效率
3. 调用栈可能会溢出，其实每一次函数调用会在内存栈中分配空间，而每个进程的栈的容量是有限的，当调用的层次太多时，就会超出栈的容量，从而导致栈溢出，强制设置最大深度会导致内存占用大--性能

优点：

1. 简洁
2. 在特殊情况下比for循环更加简洁，逻辑清晰。

4，建议

在使用for循环运算量并不太大时使用递归，在for循环逻辑太过于繁琐时使用递归。