数据结构与算法的重温之旅(八)——递归

415 阅读9分钟

接下来讲的是算法是递归。在讲递归前我们先举个递归的例子。在军训中教官可能会喊道让队员叫号,对18号出列,如果队员彼此都不知道别人甚至自己的号码,处于完全随机的排队状态的话,那么这个时候叫号其实相当于一个递归,即当前一个叫号的时候,我知道前一个人和自己的号码。

那什么是递归呢?即函数自己调用自己就是一个递归。但是如果函数一直调用自己的话则有可能会出现堆栈溢出导致程序崩溃,所以严格来说,递归除了自己能够调用自己本身以外,还要满足三个必要的条件。

首先第一个是一个问题的解可以分解为几个子问题的解。像上面讲的例子第十八号出列,可以分解成前一个人的号码是多少的问题。

第二就是这个问题与分解之后的子问题除了数据规模不同以外,求解思路都是一样的。就好像上面的例子,你只有当前一个人喊到几,你才知道自己是第几号,而子问题求解的也是求解前一个人喊到几,所以思路是一样的。

第三点就是递归一定要有一个终止条件。还是用教官叫号的例子,教官所培训的人肯定是有限,所以当教官喊的号太大,叫到最后一个人的时候教官就知道自己喊的号太大了。而如果教官喊的号刚好在范围时,他就知道哪个人是十八号。这个就是递归终止条件。

说了这么多,那我们如何编写一个递归呢?其实写一个递归的关键是写出这个递归的递归公式和终止条件,然后通过程序来实现该递归公式。

假如这里有 n 个台阶,每次你可以跨 1 个台阶或者 2 个台阶,请问走这 n 个台阶有多少种走法?如果有 7 个台阶,你可以 2,2,2,1 这样子上去,也可以 1,2,1,1,2 这样子上去,总之走法有很多,那如何用编程求得总共有多少种走法呢?我们仔细想下,实际上,可以根据第一步的走法把所有走法分为两类,第一类是第一步走了 1 个台阶,另一类是第一步走了 2 个台阶。所以 n 个台阶的走法就等于先走 1 阶后,n-1 个台阶的走法 加上先走 2 阶后,n-2 个台阶的走法。用公式表示就是:

f(n)=f(n-1)+f(n-2)

有了这个递归公式之后我们再来分析一下终止条件。n=2 时,f(2)=f(1)+f(0)。如果递归终止条件只有一个 f(1)=1,那 f(2) 就无法求解了。所以除了 f(1)=1 这一个递归终止条件外,还要有 f(0)=1,表示走 0 个台阶有一种走法,不过这样子看起来就不符合正常的逻辑思维了。所以,我们可以把 f(2)=2 作为一种终止条件,表示走 2 个台阶,有两种走法,一步走完或者分两步来走。

所以,递归终止条件就是 f(1)=1,f(2)=2。这个时候,你可以再拿 n=3,n=4 来验证一下,这个终止条件是否足够并且正确。我们把递归终止条件和刚刚得到的递推公式放到一起就是这样的:

f(1) = 1; f(2)=2; f(n) = f(n-1)+f(n-2)

有了公式以后我们编写代码就容易多了:

function func(val){
    if (val === 1) return 1
    if (val === 2) return 2
    return func(val - 1) + func(val - 2)
}

总结一下,写递归代码的关键就是找到如何将大问题分解为小问题的规律,并且基于此写出递推公式,然后再推敲终止条件,最后将递推公式和终止条件,最后将递推公式和终止条件翻译成代码。

其实每个人觉得递归难主要是钻进了一个思维惯性中,比如上面的定义所说递归是要将大的问题分解成更细的子问题,如果是像上面叫号那样只是不断的分解出一个子问题的话就比较容易理解,如果像走石阶那样分解成两个子问题则开始比较难理解了。其实人脑几乎没办法把整个“递”和“归”的过程一步一步都想清楚。计算机擅长做重复的事情,所以递归正和它的胃口。而我们人脑更喜欢平铺直叙的思维方式。当我们看到递归时,我们总想把递归平铺展开,脑子里就会循环,一层一层往下调,然后再一层一层返回,试图想搞清楚计算机每一步都是怎么执行的,这样就很容易被绕进去。

对于递归代码,这种试图想清楚整个递和归过程的做法,实际上是进入了一个思维误区。很多时候,我们理解起来比较吃力,主要原因就是自己给自己制造了这种理解障碍。那正确的思维方式应该是怎样的呢?如果一个问题 A 可以分解为若干子问题 B、C、D,你可以假设子问题 B、C、D 已经解决,在此基础上思考如何解决问题 A。而且,你只需要思考问题 A 与子问题 B、C、D 两层之间的关系即可,不需要一层一层往下思考子问题与子子问题,子子问题与子子子问题之间的关系。屏蔽掉递归细节,这样子理解起来就简单多了。

因此,编写递归代码的关键是,只要遇到递归,我们就把它抽象成一个递推公式,不用想一层层的调用关系,不要试图用人脑去分解递归的每个步骤。

除此之外像上面说的,我们编写递归代码的时候要避免堆栈溢出。我在“栈”那一节讲过,函数调用会使用栈来保存临时变量。每调用一个函数,都会将临时变量封装为栈帧压入内存栈,等函数执行完成返回时,才出栈。系统栈或者虚拟机栈空间一般都不大。如果递归求解的数据规模很大,调用层次很深,一直压入栈,就会有堆栈溢出的风险。

我们可以通过在代码中限制递归调用的最大深度的方式来解决这个问题。递归调用超过一定深度(比如 1000)之后,我们就不继续往下再递归了,直接返回报错。还是电影院那个例子,我们可以改造成下面这样子,就可以避免堆栈溢出了。

let deep = 0
function func(val){
    ++n
    if (n > 1000) return throw Error('error')
    if (val === 1) return 1
    if (val === 2) return 2
    return func(val - 1) + func(val - 2)
}

但这种做法并不能完全解决问题,因为最大允许的递归深度跟当前线程剩余的栈空间大小有关,事先无法计算。如果实时计算,代码过于复杂,就会影响代码的可读性。所以,如果最大深度比较小,比如 10、50,就可以用这种方法,否则这种方法并不是很实用。

还有一点就是避免递归的重复运算。就拿上面走阶梯的为例,如果计算一个f(5),首先第一步你要算出f(4)和f(3),然后第二步通过f(4)算出f(3)和f(2),第三步这里的f(3)还要继续算出f(2)和f(1)。但是这里的第一步的f(3)却还没有算,需要重复第三步的步骤再算一遍。f(5)还好只是重复了一个,如果n越大,则重复的概率则越大。这个时候我们可以通过一个散列表或者是其他能够表示唯一的数据结构来储存n为几的时候的值。在JavaScript中则可以通过Set来储存。代码如下:

var tempIndex = new Set()
var tempValue = []

function f(n) {
    if (n == 1) return 1;
    if (n == 2) return 2;

    if (tempIndex.has(n)) {
        return tempValue[n];
    }

    var ret = f(n-1) + f(n-2);
    tempIndex.add(n)
    tempValue[n] = ret
    return ret;
}

在时间效率上,递归代码里多了很多函数调用,当这些函数调用的数量较大时,就会积聚成一个可观的时间成本。在空间复杂度上,因为递归调用一次就会在内存栈中保存一次现场数据,所以在分析递归代码空间复杂度时,需要额外考虑这部分的开销,比如我们前面讲到的教官叫号,空间复杂度并不是 O(1),而是 O(n)。

那递归的时间复杂度那么高,并且还会存在堆栈溢出和重复计算的风险,那我们如何去将递归改写成非递归代码呢?那刚刚所说到的例子,f(1) = 1; f(2)=2; f(n) = f(n-1)+f(n-2)这条式子其实只是表示当前函数等于当前函数的上一个值家当前函数的上上一个值,那么我们可以用循环来从一开始迭代上去:

function f(n) {
  if (n == 1) return 1;
  if (n == 2) return 2;
  
  var ret = 0;
  var pre = 2;
  var prepre = 1;
  for (var i = 3; i <= n; ++i) {
    ret = pre + prepre;
    prepre = pre;
    pre = ret;
  }
  return ret;
}

再比如f(n)=f(n-1)+1这条式子,表示的是当前函数值等于当前函数的上一个值加1,这个实现起来就更简单了:

function f(n) {
  var ret = 1;
  for (var i = 2; i <= n; ++i) {
    ret = ret + 1;
  }
  return ret;
}

那是不是所有的递归代码都可以改为这种迭代循环的非递归写法呢?笼统地讲,是的。因为递归本身就是借助栈来实现的,只不过我们使用的栈是系统或者虚拟机本身提供的,我们没有感知罢了。如果我们自己在内存堆上实现栈,手动模拟入栈、出栈过程,这样任何递归代码都可以改写成看上去不是递归代码的样子。但是这种思路实际上是将递归改为了“手动”递归,本质并没有变,而且也并没有解决前面讲到的某些问题,徒增了实现的复杂度。


上一篇文章:数据结构与算法的重温之旅(七)——队列​​​​​​​

下一篇文章:数据结构与算法的重温之旅(九)——三个简单的排序算法​​​​​​​ 

延伸阅读:数据结构与算法的重温之旅(番外篇1)——谈谈斐波那契数列​​​​​​​