JS递归函数精讲

递归就是调用自身的一种编程技巧，在程序设计中应用广泛。递归函数就是函数对自身的调用，是循环运算的一种算法模式。

JS递归运算

递归必须由以下两部分组成。

• 递归调用的过程。
• 递归终止的条件。

在没有限制的情况下，递归运算会无终止地自身调用。因此，在递归运算中要结合 if 语句进行控制，只有在某个条件成立时才允许执行递归，否则不允许调用自身。

递归运算的应用场景如下。

1) 求解递归问题

主要解决一些数学运算，如阶乘函数、幂函数和斐波那契数列。

下面示例使用递归运算来设计阶乘函数。

var f = function (x) {
    if (x < 2) return 1;  //递归终止条件
    else return x * f(x - 1);  //递归调用过程
}
console.log(f(5));  //返回5的阶乘值为120

在这个过程中，利用分支结构把递归结束条件和递归运算分开。

2) 解析递归型数据结构

很多数据结构都具有递归特性，如 DOM 文档树、多级目录结构、多级导航菜单、家族谱系结构等。对于这类数据结构，使用递归算法进行遍历比较合适。

下面使用递归运算计算指定节点内所包含的全部节点数。

function f (n) {  //统计指定节点及其所有子节点的元素个数
    var l = 0;  //初始化计数变量
    if (n.nodeType == 1) l ++;  //如果是元素节点，则计数
    var child = n.childNodes;  //获取子节点集合
    for (var i = 0; i < child.length; i ++) {  //遍历所有子节点
        l += f (child[i]);  //递归运算，统计当前节点下所有子节点数
    }
    return l;  //返回节点数
}
window.onload = function () {
    console.log(f(document.body));  //返回2，即body和script两个节点
}

3) 适合使用递归法解决问题

有些问题最适合采用递归的方法求解，如汉诺塔问题。

下面使用递归运算设计汉诺塔演示函数。参数说明：n 表示金片数；a、b、c 表示柱子，注意排列顺序。返回说明：当指定金片数，以及柱子名称，将输出整个移动的过程。

function f (n,a,b,c) {
    if (n == 1) {  //当为一片时，直接移动
        document.write("移动 【盘子" + n + "】从【" + a + "柱】到【" + c + "柱】<br>");
    } else {
        f (n - 1, a, c, b);  //调整参数顺序。让参数a移给b
        document.write("移动 【盘子" + n + "】从【" + a + "柱】到【" + c + "柱】<br>");
        f(n - 1, b, a, c);  //调整顺序，让参数b移给c
    }
}
f (3, "A", "B", "C");  //调用汉诺塔函数

运行结果如下：

移动【盘子1】从【A柱】到【C柱】
移动【盘子2】从【A柱】到【B柱】
移动【盘子1】从【C柱】到【B柱】
移动【盘子3】从【A柱】到【C柱】
移动【盘子1】从【B柱】到【A柱】
移动【盘子2】从【B柱】到【C柱】
移动【盘子1】从【A柱】到【C柱】

JS尾递归

尾递归是递归的一种优化算法，递归函数执行时会形成一个调用函数，当子一层的函数代码执行完成之后，父一层的函数才会销毁调用记录，这样就形成了调用栈，栈的叠加可能会产生内存溢出。而尾递归函数的每子一层函数不再需要使用父一层的函数执行完毕就会销毁栈记录，避免了内存溢出，节省了内存空间。

示例

下面是阶乘的一种普通线性递归运算。

function f (n) {
    return (n == 1) ? 1 : n * f (n - 1);
}
console.log(f(5));  //120

使用尾递归算法后，则可以使用以下方法。

function f (n, a) {
    return (n == 1) ? a : f (n - 1, a * n);
}
console.log(f(5, 1));  //120

当 n=5 时，线性递归的递归过程如下。

f (5) = {5 * f(4)}
      = {5 * {4 * f(3) }}
      = {5 * {4 * {3 * f(2)}}}
      = {5 * {4 * {3 * {2 * f(1)}}}}
      = {5 * {4 * {3 * {2 *1}}}}
      = {5 * {4 * {3 *2}}}
      = {5 * {4 * 6}
      = {5 * 24}
      = 120

而尾递归的递归过程如下。

f (5) = f (5, 1)
      = f (4, 5)
      = f (3, 20)
      = f (2, 60)
      = f (1, 120)
      = 120

很容易看出，普通递归比尾递归更加消耗资源，每次重复的过程调用都使得调用链条不断加长，系统不得不使用栈进行数据保存和恢复，而尾递归就不存在这样的问题，因为它的状态完全由变量 n 和 a 保存。

从理论上分析，尾递归也是递归的一种类型，不过其算法具有迭代算法的特征。上面的阶乘尾递归可以改写为下面的迭代循环。

var n = 5;
var w = 1;
for (var i = 1; i <= 5; i ++) {
    w = w * i;
}
console.log(w);

尾递归由于直接返回值，不需要保存临时变量，所以性能不会产生线性增加，同时 JavaScript 引擎会将尾递归形式优化成非递归形式。

JS递归与迭代的区别

递归与迭代都是循环的一种，简单比较如下：

• 在程序结构上，递归是重复调用函数自身实现循环，迭代是通过循环结构实现。
• 在结束方式上，递归当满足终止条件时会逐层返回再结束，迭代直接使用计数器结束循环。
• 在执行效率上，迭代的效率明显高于递归。因为递归需要占用大量系统资源，如果递归深度很大，系统资源可能会不够用。
• 在编程实现上，递归可以很方便的把数学公式转换为程序，易理解，易编程。迭代虽然效率高，不需要系统开销，但不容易理解，编写复杂问题时比较麻烦。

在实际应用中，能不用递归就不用递归，递归都可以用迭代来代替。

示例

下面以斐波那契数列为例说明。

斐波那契数列就是一组数字，从第 3 项开始，每一项都等于前两项之和。例如：
1、1、2、3、5、8、13、21、34、55、89、144、233、377、610、987、1597、2584、4181。

使用递归函数计算斐波那契数列，其中最前面的两个数字是 0 和 1。

var fibonacci = function (n) {
    return n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2);
};
console.log(fibonacci(19));  //4181

尝试传入更大的数字，会发现递归运算的次数加倍递增，速度加倍递减，返回值加倍放大。如果尝试计算 100 的斐波那契数列，则浏览器基本瘫痪。

下面使用迭代算法来设计斐波那契数列，代码如下（测试瞬间完成，基本没有任何延迟）：

var fibonacci = function (n) {
    var a = [0, 1];  //记录数列的数组，第1、2个元素值确定
    for (var i = 2; i <= n; i ++) {  //从第 3 个数字开始循环
        a.push(a[i - 2] + a[i - 1]);  //计算新数字，并推入数组
    }
    return a[n];  //返回指定位数的数列结果
};
console.log(fibonacci(19));  //4181

下面使用 JavaScript 高阶函数进行设计，把斐波那契数列函数封装在一个闭包体内，然后返回斐波那契数列函数。在闭包内使用 memo 数组持久记录每级斐波那契数列函数的求值结果。在下一次求值之前，先在数组中检索是否存在同级（数列的个数，数组的下标位置）计算结果，如果存在，则直接返回，避免重复行计算；如果没有找到结果，则调用斐波那契数列函数进行求和。实现代码如下：

var finbonacci = (function () {
    var memo = [0, 1];
    var fib = function (n) {
        var result = memo[n];
        if (typeof result !== 'number') {
            result = fib(n - 1) + fib(n - 2);
            memo[n] = result;
        }
        return result;
    };
    return fib;
}());
console.log(finbonacci(100));  //354224848179262000000

在浏览器中测试，可以看到，求 100 的斐波那契数列基本上不会延迟。