递归

发表于 | 分类于

递归并不属于什么语言的特性，只是一种编程技巧。

对于递归的使用，很多初学者都停留在了解，但不深入，并且很难达到熟练使用的程度。

怎样才能更好的理解递归，并熟练使用呢，这是本篇深入学习的目的。

递归是什么？

递归，是一种程序设计思想，从使用形式上看，是函数的自调用，即在函数的内部调用自身。

案例：计算 n 的阶乘

1
2
3
4
5
6
7
8
function recursion(n) {
  if (n === 1) {
    return 1
  }
  return n * recursion( n - 1 );
}
recursion(4) 
// 4 * 3 * 2 * 1 = 24

从上面我们看到，recursion 函数的内部调用了 recursion()，自调用的形式就是递归的经典使用形式。

注：递归函数内部必须包含终止条件，即递归的出口。否则会造死循环。

递归在底层是如何执行的呢？

先来看一下程序中的函数在内存中什么样的，如下图所示：

如上图所示，程序中的函数，会存储在 代码段 中，代码段只会保存一份相同的代码。

对于递归来说，每个函数其实都是相同的，因此递归函数会被放到栈中，每次递归的函数（不一定只针对递归函数）被存储到栈帧中，依次排列就形成了一个 调用栈。

那么函数为什么要存储在栈中而不是堆中呢？

我们知道，函数的执行顺序其实是及外的，即内层函数全部执行完毕（释放内存），外层函数才能得到释放，这就适用于栈的先进后出的逻辑。

看一下每个栈帧长什么样：

可以看到，忽略其他的内容，输入参数和返回值，代表的就是一个函数调用。

通过上面对函数在内存的简单了解，我们可以把递归函数的调用栈代换成下面这样：

注：因为压栈是从栈底开始，栈底在最上面，那么图中的函数栈，自然也是从上往下的生长。

理解了函数调用的逻辑，我们可以梳理一下递归函数的执行逻辑：

递归函数开时，从 recursion(4) 开始调用（栈帧1），其返回值是 4 * recursion(3); 但是这时我们还不知道函数 recursion(3) 的返回值是多少，所以需要新的栈帧来计算 recursion(3)，那么新的栈帧计算的返回值是 3 * recursion(2)，这时 recursion(2)的返回值又不知道了，所以又需要新的栈帧来计算 recursion(2)，整个过程就是如此循环下去，直到达到终止条件 recursion(1) = 1 ，有了明确的返回值，然后每个栈帧开始依次出栈，最终就能计算出 recursion(4) 的真实返回值了 。

整个入栈过程就是这样的：

1
2
3
4
recursion(4) = 4 * recursion(3)
recursion(3) = 3 * recursion(2)
recursion(2) = 2 * recursion(1)
recursion(1) = 1

出栈过程是这样的：

1
2
3
4
recursion(1) = 1
recursion(2) = 2 * recursion(1) = 2 * 1
recursion(3) = 3 * recursion(2) = 3 * 2 * 1
recursion(4) = 4 * recursion(3) = 4 * 3 * 2 * 1

使用尾递归防止爆栈

每个栈的容量是有限的，且每个栈帧都会占据一些空间，如果递归的太深（维护的栈帧数量过多）的话，则很可能会导致挤爆一个栈。

再来回顾一下我们的递归算法

1
recursion(n) = n * recursion(n - 1)

从上面的栈帧图我们可以看到，每个栈不仅需要记录当前的 n 值，好需要记录下一个函数栈的返回值，然后才能计算出当前栈帧的结果，所以对于上面的算法，使用多个栈是无法避免的。

为了防止爆栈情况的发生，我们使用尾递归的方式，改下一下我们的算法：

1
2
3
4
5
6
function recursion(n, result) {
  if (n === 1) {
    return result
  }
  return recursion(n - 1, n * result);
}

可以看到，之前的 n * recursion(n - 1) 替换成了 recursion(n - 1, n * result)，而且函数新增了一个参数 result 。

先看一下计算过程：

1
2
3
4
5
6
recursion(4, 1)
= recursion(3, 4 * 1)
= recursion(2, 3 * 4 * 1)
= recursion(1, 2 * 3 * 4 * 1)
= recursion(1, 24)
= 24

通过上面的计算过程，会发现，每个函数的执行，都不在依赖任何变量和返回值，所有的值，只是通过传参的方式计算得出。跟之前的算法过程进行对比，能够看出，当计算到 recursion(1, 24) ，整个计算过程已经技术，不需要再退回到 recursion(2) = 2 * recursion(1) = 2 * 1 这个函数了不是吗？

这就是 尾递归 的妙处，那么它是怎么做到不会发生爆栈的呢？

当我们使用 尾递归 进行计算时，计算机是能够发现这种情况的，并针对 尾递归 的情况，只需要对递归函数分配一个栈帧就可以搞定这些计算，而且不需要关心 n 的值的大小，以及递归的深度，因为我们不在需要多个栈帧进行协作计算了。

那么具体什么样的递归，才属于尾递归呢？

当递归调用时函数体中最后执行的语句，且该语句不参与任何计算（如，return n * recursion(n - 1)就不是尾递归，因为递归函数在调用时，跟变量 n 形成了计算表达式。），并且返回值不属于表达式的一部分时，这个递归才是 尾递归