了解 JavaScript 的递归

简介

使用递归可以更自然地解决一些问题。例如，像斐波那契数列：数列中的每个数字都是数列中前两个数字的和。凡是需要您构建或遍历树状数据结构的问题基本都可以通过递归来解决，锻炼自己强大的递归思维，你会发现解决这类问题十分容易。

在本文中，我将列举两个案例，让你们了解递归函数是如何工作的。

纲要

什么是递归
数字的递归
数组的递归
总结

什么是递归

函数的递归就是在函数中调用自身，看一个简单的例子：

function doA(n) {
    ...
    doA(n-1);
}

为了理解递归在理论上是如何工作的，我们先举一个与代码无关的例子。想象一下，你是一家公司的话务员。由于这是一家业务繁忙的公司，你的座机连接多条线路，因此你可以同时处理多个电话。每条线路对应接收器上的一个按钮，当有来电时，该按钮将闪烁。今天当你到达公司开始工作时，发现有四条线路对应的按钮正在闪烁，所以你需要接听所有这些电话。

你接通线路一，并告诉他“请稍等”，然后你接通线路二，并告诉他“请稍等”，接着，你接通线路三，也告知他“请稍等”，最后，你接通线路四，并与其通话。当你结束了与线路四的通话之后，你回过头来接通线路三，当你结束了与线路三的通话之后，你接通线路二，结束之后，你再接通线路一，当与线路一的这位客户结束通话后，你终于可以放下电话了。

这个例子中的每一通电话就像某函数中的一个递归调用。当你接到一个电话且不能立即处理时，这个电话将被搁置；当你有一个不需要立即触发的函数调用时，它将停留在调用栈上。当你可以接听一个电话时，这个线路会被接通；当你的代码能够触发一个函数调用时，它会从调用栈中弹出。在你看到之后的代码案例有些发懵时，请回想一下这个比喻。

数字的递归

每个递归函数都需要一个终止条件，从而使其不会无休止地循环下去。然而，仅仅加一个终止条件，是不足以避免其无限循环的。该函数必须一步一步地接近终止条件。在递归步骤中，问题会逐步简化为更小的问题。

假设有一个函数：从1加到n。例如，当n = 4，它实现的就是“1 + 2 + 3 + 4”。

首先，我们需要寻找终止条件。这一步可以认为是找到那个不通过递归就直接结束该问题的条件。当n等于0时，没法再拆分了，所以我们的递归在到达0时停止。

在每一步中，你将从当前数字减去1。什么是递归条件？就是用减少的数字调用函数sum。

function sum(num){
    if (num === 0) {
        return 0;
    } else {
        return num + sum(--num)
    }
}
 
sum(4);     //10

每一步过程如下：

执行sum(4)。
4等于0么？否，把sum(4)保留并执行sum(3)。
3等于0么？否，把sum(3)保留并执行sum(2)。
2等于0么？否，把sum(2)保留并执行sum(1)。
1等于0么？否，把sum(1)保留并执行sum(0)。
0等于0么？是，计算sum(0)。
提取sum(1)。
提取sum(2)。
提取sum(3)。
提取sum(4)。

这是查看函数如何处理每个调用的另一种方式：

sum(4)
4 + sum(3)
4 + ( 3 + sum(2) )
4 + ( 3 + ( 2 + sum(1) ))
4 + ( 3 + ( 2 + ( 1 + sum(0) )))
4 + ( 3 + ( 2 + ( 1 + 0 ) ))
4 + ( 3 + ( 2 + 1 ) )
4 + ( 3 +  3 ) 
4 + 6 
10

我们可以发现，递归条件中的参数不断改变，并逐渐接近并最终符合终止条件。在上面的案例中，我们在递归条件中的每一步都将参数减1，最后在终止条件中测试参数是否等于0。

任务

使用常规循环方法而不是递归来写一个数字求和的sum函数。
写一个递归函数来实现两数相乘。例如：multiply(2,4) 将返回8，写出multiply(2,4)的每一步发生的情况。

数组的递归

数组的递归和数字的递归相似，类似于数字的递减，我们在每一步递减数组中的元素个数，直到获得一个空数组。

考虑使用数组作为求和函数的参数，并返回数组中所有元素的总和。求和函数如下：

function sum(arr) {
    var len = arr.length;
    if (len == 0) {
        return 0;
    } else {
        return arr[0] + sum(arr.slice(1));
    }
}

如果数组长度等于0，则返回0，arr[0]表示数组的第一位，arr.slice(1)表示从第一位开始截取arr数组，并返回截取之后的数组。例如var arr = [1,2,3,4];，arr[0]为1，arr.slice(1)为[2,3,4]。当我们执行sum([1,2,3,4])时，都发生了一些什么？

sum([1,2,3,4])
1 + sum([2,3,4])
1 + ( 2 + sum([3,4]) )
1 + ( 2 + ( 3 + sum([4]) ))
1 + ( 2 + ( 3 + ( 4 + sum([]) )))
1 + ( 2 + ( 3 + ( 4 + 0 ) ))
1 + ( 2 + ( 3 + 4 ) )
1 + ( 2 + 7 ) 
1 + 9
10

每一次执行都检查数组是否为空，否则，对元素数量逐渐递减的该数组执行递归。

任务

使用常规循环方法而不是递归来写一个数组求和的sum函数。
定义一个length()函数，数组作为参数，返回数组长度（不可以使用Javascript Array对象内置的length属性）。例如：length(['a', 'b', 'c', 'd'])，并写出每一步发生的事情。

总结

一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。

本文只列举两个小案例，只为说明递归是怎么回事，上述两个案例的公式都是变量+函数的形式，当然也有很多函数+函数的形式的案例，例如文章开头提到的著名的斐波那契数列，代码如下：

function func( n ) { 
    if (n == 0 || n == 1) {
        return 1;
    }
        return func(n-1) + func(n-2);
}

下面来说一下使用递归的步骤及优缺点。

步骤

找规律，将这个规律转换成一个公式return出来。
找出口，出口即终止条件，它一定是一个已知的条件。

优点

代码异常简洁。
符合人类思维。

缺点

由于递归是调用函数自身，而函数调用需要消耗时间和空间：每次调用，都要在内存栈中分配空间以存储参数、临时变量、返回地址等，往栈中压入和弹出数据都需要消耗时间。这势必导致执行效率大打折扣。
递归中的计算大都是重复的，其本质是把一个问题拆解成多个小问题，小问题之间存在互相重叠的部分，这样的重复计算也会导致效率的低下。
调用栈可能会溢出。栈是有容量限制的，当调用层次过多，就会超出栈的容量限制，从而导致栈溢出！

可见递归的缺点还是很明显的，在实际开发中，在可控的情况下，合理使用。

感谢您的阅读！