山地人

Python 递归

山地人
山地人
2021-07-19

这篇教程,我们关注点在递归上。递归是一种很重要的解决重复问题的方法。

什么是递归

函数直接或间接调用自己的过程称为递归,这样的函数被称为递归函数

递归其实是两个过程,我们把这两个字拆开:是将一个问题逐步拆解成更小的子问题的过程,当问题被拆解到无需再拆解的时候子问题也就被求解出来了。此时再从子问题一点点往上合并,也就是的过程。最后回归到要最开始的问题。整个过程被称为递归

递归的例子

我们拿求解斐波那契数列来举例: 斐波那契数列:1、1、2、3、5、8、13、… 除了第一项和第二项是固定的1之后每一项都是前两项的和。根据这样的规则,我们可以得出这样两个算式:

f(n) = 1 (当n<=2时)
f(n) = f(n-1) + f(n-2) (当n>2时)

根据上面两个算式,我们用Python递归函数来表达:

def fib(n):
if n<=2:
return 1
else:
return fib(n-1)+fib(n-2)

运行沙盒,测试下fib(n)的递归版本。

如何写递归函数

对于编写递归函数,我们先得找出问题的规律,找到规律后,也就意味着我们可以定义出递归表达式了。然后我们还得导出什么时候可以结束,也就是递归的终止条件。

拿前面斐波那契数列来说,规律就是每次都是前两个数的和,这就是规律部分。我们把要求的数用函数表示就是f(n)。那这个f(n)是前两个数的和,所以f(n) = f(n-1) + f(n-2) 这样递归表达式就有了。接下来我们再来看这样的表达式中f(n)会去寻找f(n-1)和f(n-2),f(n-1)又会寻找f(n-2)和f(n-3)。这样下去n-x会越来越小,知道n-x值为2或者n-x值为1时,不用再去寻找,因为我们知道f(1) = 1 ,f(2) = 1 这个两个最开始的n的对应值。这就是递归终止条件。

def f(n):
if n<=2:
return 1
else:
return f(n-1)+f(n-2)

最后我们把所得到的的终止条件和递归表达式都整合到递归函数中,就有了上面这样的定义,当n小于等于2时,直接返回结果1。这就保证了,当求f(3) = f(2) + f(1) 是能得到结果,因为f(2)和f(1)都是不用再递归计算的。往后f(4),f(5),…,f(n)的计算都可以进行了。

通过这样的思考和分析,我们学会了编写递归函数: 1.寻找递归表达式(找出规律) 2.定义递归终止条件(找递归的出口) 3.整合成递归函数

递归的优劣

优点:

  • 递归表达逻辑更加清晰。
  • 对编写和维护代码更为友好。 缺点:
  • 需要使用更多内存维护堆栈,递归深度过程会有栈溢出的风险。
  • 更多的调用栈操作,执行速度会比迭代慢一些。
  • 递归中有较多的重复计算,(可以优化)

对递归的优化

针对递归中出现的问题,我们再来看看如何优化这些问题。

重复计算,用缓存

对于上面的fib(n)的递归版本,会有很多重复计算,当n越大,重复计算的情况就越严重。为此,我们可以在其中加入缓存,将已有的计算结果缓存起来,下次再次遇到同样的计算时,先查看如果有缓存就直接使用,否则再去计算。

def fib(n):
cache = {}
def innerFib(n):
nonlocal cache
if n<1:
return 0
if n<=2:
return 1
else:
if(n in cache):
return cache[n]
else:
cache[n] = innerFib(n-1)+innerFib(n-2)
return cache[n]

innerFib中定义了一行nonlocal cache,用于声明在innerFib中绑定fib中的cache。

运行沙盒,测试下fib(n)的递归版本。

小实验

为了对比效果,这里将两个版本的fib()函数进行一次对比,观察下运行结果。

  • fib()是没有加缓存的版本
  • fibCache()是带缓存版本的 我们看看两个版本同时计算到 fib(40) 所需要的时间:

运行下面的沙盒,观察两个版本的递归的计算性能。

堆栈溢出

带缓存的fib性能比不带缓存的版本高了很多。现在来解决另一个问题,当我们加大fib(n)n的值,比如设置为100。这时即便是带缓存版本的fib(100)也出现了爆栈问题。

下面,我们基于这个带缓存的版本的思路继续优化,看能否消除递归爆栈问题。既然递归层级过深会导致爆栈,那能否减少递归。我们利用迭代去替代原来内部的递归函数,递归的想法是要求出f(n)就要知道f(n-1)和f(n-1)。如果反过来思考,我们已经知道了f(1)和f(2),就可以知道f(3)。知道f(2)和f(3)也就知道了f(4)。如果要求f(n),那我们就从f(1),f(2)…f(n)当计算到f(n)时,结果也就完成了。基于这个思路,我们重新实现了一版fib

def fib(n):
if(n<=2):
return 1
a = 1
b = 1
for i in range(3,n+1):
result = a + b
a = b
b = result
return b

通过思路的调整,我们把递归版本的fib改造成了迭代版本的fib,这个版本巧妙利用,a和b两个变量,替代了之前缓存版本需要大量的缓存Map的问题。同时也不会有过深的调用堆栈,因此也不会带来递归爆栈问题。可谓一句多得。

运行下面的沙盒,将递归改成迭代版本。

至此,本篇教程也到了该和你说再见的时候了,我们下期再见。

学完本篇互动教程,如果你觉得体验不错,可以把网页链接发送给你的小伙伴,让他/她也来感受一下。当然,你也可以继续看看网站上其他的的互动教程,希望`idev365`能够给你带来收获。

学习教程的过程中碰到了问题,或者对idev365有什么改进意见和想法,欢迎加入idev365微信内测群,和山地人交流你的想法。