递归解释（附示例）

“要理解递归，首先必须理解递归” - 未知

递归是一种解决问题的方法，通过逐步解决问题的各个小部分，直至最终解决最初的大问题。如果一个方法或函数可以调用自身，则称其为递归。

function understandRecursion(doIUnderstandRecursion) {
    const recursionAnswer = confirm('Do you understand recursion?');
    if(recursionAnswer === true) { // base case
        return true;
    }
    understandRecursion(recursionAnswer); // recursive call
}

对于上面的例子，请注意基准条件和递归调用，它们使得该算法成为递归算法。递归函数必须有一个基准条件，或者说一个不进行递归调用的条件。我认为理解递归的最好方法是看例子，所以让我们来看一下两个常见的递归问题。

例 1：计算数字的阶乘

计算一个数的阶乘是一个常见问题，可以用递归方法解决。提醒一下，一个数 n 的阶乘定义为 n!，是将 1 到 n 相乘的结果。因此，5!等于5*4*3*2*1，结果为120。

我们先来看一个迭代解决方案：

function factorial(num) {
    let total = 1;
    for(let n = num; n > 1; n--) {
        total *= n;
    }
    return total;
}

上面的迭代解法很好，但让我们尝试用递归重写它。当我们考虑用递归解决这个问题时，我们需要弄清楚我们的子问题是什么。让我们分解一下：

1. 我们知道factorial(5) = 5 * factorial(4)又名5! = 5 * 4!。
2. 继续，factorial(5) = 5 * (4 * factorial(3))等于5 * (4 * (3 * factorial(2))等等……
3. ...直到你得到5 * 4 * 3 * 2 * 1并且唯一剩下的子问题是1!。
4. factorial(1)并且factorial(0)始终等于 1，因此这将是我们的基本情况。

使用这种思路，我们可以为阶乘问题写出一个递归解决方案：

function factorial(n) {
    if(n === 1 || n === 0) { // base case
        return 1;
    }
    return n * factorial(n - 1); // recursive call
}

例2：斐波那契数列

另一个可以用递归解决的有趣问题是斐波那契数列问题。提醒一下，斐波那契数列是一系列数字：0、1、1、2、3、5、8、13、21、34，等等。其规律是将前两个数字相加，因此 0 + 1 = 1，1 + 1 = 2，1 + 2 = 3，2 + 3 = 5，等等。换句话说，位置n(对于n > 2) 处的斐波那契数等于 的斐波那契数(n - 1)加上 的斐波那契数(n - 2)。

再次，我认为首先看到一个迭代解决方案是有帮助的：

function fibonacci(n) {
    if(n === 0) return 0;
    if(n === 1) return 1;

    let fibNMinus2 = 0;
    let finNMinus1 = 1;
    let fibN = n;

    for(let i = 2; i <= n; i++) { // n >= 2
        fibN = fibNMinus1 + fibNMinus2; // f(n-1) + f(n-2)
        fibNMinus2 = fibNMinus1;
        fibNMinus1 = fibN;
    }
    return fibN;
}

正如您所见，递归解决方案看起来简单得多：

function fibonacci(n) {
    if(n === 0) return 0; // base case 1
    if(n === 1) return 1; // base case 2

    return fibonacci(n - 1) + fibonacci(n - 2); // recursive call
}

如果要调用 fibonacci(5)，则以下表示将进行的调用：

带有记忆功能的斐波那契数列

我想借此机会提一下解决这个问题的另一种方法，叫做记忆化（memoization）。记忆化是一种优化技术，它存储先前结果的值，类似于缓存，从而加快了我们的递归求解速度。如果你回顾上图中对计算的调用fibonacci(5)，你会发现它fibonacci(3)被计算了两次，所以我们可以存储它的结果，这样当我们再次计算时，就已经有了它。

看看fibonacci当我们添加记忆功能时我们的解决方案如何变化：

function fibonacci(n) {

    const memo = [0, 1]; // cache all computed results here

    const fib = (n) => {

        if(memo[n] != null) return memo[n]; // base case

        return memo[n] = fib(n - 1, memo) + fib(n - 2, memo); // recursive call

    };

        return fib(n);

}

为什么要使用递归？

坦白说，递归解法几乎总是比迭代解法慢。话虽如此，如果你回顾一下我们的斐波那契数列解法，你会发现递归解法更容易阅读，而且记忆化机制可以帮助弥补速度上的差距。递归通常更容易理解，而且通常需要的代码更少。

结论

现在我们已经讲解了一些示例，希望你能更容易地理解递归，并明白我们为什么要使用它。在以后的文章中，我计划讲解树形数据结构，它在很多方法中都使用了递归，敬请期待！本文只是对递归潜力的粗略介绍，如果你想继续学习，这里有一些资源可能会对你有所帮助。

• 通过 HackerRank练习递归问题
• 普林斯顿大学的著名递归问题