迎接ECMAScript 6, 使用尾递归

尾调用，是指函数内部的最后一个动作是函数调用。该调用的返回值，直接返回给函数。

Example:

function sum(x) {
    return sum(x + 1);
}

这里的sum()内部的sum就是属于尾调用，ta所返回的值直接返回给调用ta的上层sum()函数。

function sum(x) {
    return 1 + sum(x + 1);
}

这里的sum()内部的sum就不属于尾调用，ta所返回的值在返回给调用ta的上层sum()函数之前，需要先跟1计算和，然后再返回。

尾调用和非尾调用有什么差异？

编写一个求和函数，有大致3种方式:

• 循环

  function sum(x) {
      var result = x;
      while (x >= 1) {
          result += --x;
      }
      return result;
  }
  

  循环自然是速度和性能最好的，但是在编写复杂的代码时，循环往往模块化很差，可读性很差，而且无法体现数学上的描述。

• 普通递归

  function sum(x) {
      if (x === 1) {
          return 1;
      }
      return x + sum(--x);
  }
  

  普通递归时，内存需要记录调用的堆栈所出的深度和位置信息。在最底层计算返回值，再根据记录的信息，跳回上一层级计算，然后再跳回更高一层，依次运行，直到最外层的调用函数。在cpu计算和内存会消耗很多，而且当深度过大时，会出现堆栈溢出。

  比如，计算sum(5)的时候，其计算过程是这样的:

  sum(5)
  (5 + sum(4))
  (5 + (4 + sum(3)))
  (5 + (4 + (3 + sum(2))))
  (5 + (4 + (3 + (2 + sum(1)))))
  (5 + (4 + (3 + (2 + 1))))
  (5 + (4 + (3 + 3)))
  (5 + (4 + 6))
  (5 + 10)
  15

  在计算的过程中，堆栈一直不停的记录每一层次的详细信息，以确保该层次的操作完成，能返回到上一层次。

  通过尾递归，可以取消过多的堆栈记录，而只记录最外层和当前层的信息，完成计算后，立刻返回到最上层。从而减少cpu计算和内存消耗。

• 尾递归

  function sum(x, total) {
      if (x === 1) {
          return x + total;
      }
      return sum(x - 1, x + total);
  }
  

  这个函数更具有数学描述性:

  • 如果输入值是1 => 当前计算数1 + 上一次计算的和total
  • 如果输入值是x => 当前计算数x + 上一次计算的和total

  计算sum(5, 0)的时候，其过程是这样的:

  sum(5, 0)
  sum(4, 5)
  sum(3, 9)
  sum(2, 12)
  sum(1, 14)
  15

  整个计算过程是线性的，调用一次sum(x, total)后，会进入下一个栈，相关的数据信息和跟随进入，不再放在堆栈上保存。当计算完最后的值之后，直接返回到最上层的sum(5,0)。

  这能有效的防止堆栈溢出。

  而且最happy的是，在ECMAScript 6，我们将迎来尾递归优化，享受只有LISP HASKELL这些古典函数式语言才拥有的能力。通过尾递归优化，javascript代码在解释成机器码的时候，将会向while看起，也就是说，同时拥有数学表达能力和while的效能。

使用尾递归

这里有一个使用尾递归提取绝对文件名的例子，可以来展示下尾递归的魅力。这个函数需要输入一个(或几个)目录名和当前所在的文件位置，然后会递归提取目录下的所有文件名，放入一个栈中。

var FS = require('fs');
var PATH = require('path');

function readSync(paths, i) {
    if (i >= 0 && i < paths.length) {
        var stats = FS.statSync(paths[i]);
        if (stats.isFile()) {
            return readSync(paths, ++i);
        } else if (stats.isDirectory()) {
            var newPaths = FS.readdirSync(paths[i]).map(function (path) {
                return PATH.join(paths[i],path);
            });
            return readSync(paths.slice(0, i).concat(newPaths, 
                                                     paths.slice(i + 1)), 
                            i);
        } else {
            return readSync(paths.slice(0, i).concat(paths.slice(i + 1)), 
                            i);
        }
    } else {
        return paths;
    }
}

测试一下，这个函数可以在服务器启动时，提取某一个(或者几个)目录内的所有文件，然后用于编译或者是其他的操作。

readSync([PATH.join(__dirname, './tpls')], 0).forEach(function (path) {
    console.log(path);
});
readSync([PATH.join(__dirname, './tpls'), PATH.join(__dirname, './pages')], 0).forEach(function (path) {
    console.log(path);
});