第十天：递归

[sofish]

通常来说，提起递归，就会想到阶乘；想起阶乘就会想到自己既不喜欢数学也不喜欢历史；所以也就是说无论从客观层面（数学）上来说，还是从非客观（历史，通常更像故事而不是真实）都不喜欢，那就是任性；任性的结果是这些科目成绩不好，成绩不好就只能考法学院；考法学院还不好好学习，就只能写代码，写代码又要搞递归；递归又要回到阶乘。所以，还是贴个图片并从维基百科拿来一句定义吧：一个正整数的阶乘/层（英语：factorial）是所有小于及等于该数的正整数的积，并且有0的阶乘为1。

又要来逼死文科生了：递归，在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。那我们用递归实现一个阶乘吧：

function factorial(n) {
  return n ? (n * factorial(n - 1)) : 1;
}

好了，完美，不过《 JS 高级程序设计》里提及过一个问题，函数作为一个引用类型，在递归里，如果我们使用函数名来调用自身，可能会存在一个指向的问题（引用类型在有引用时，指向的对象是不会被回收（GC）的，对吧？！），看下面的代码：

var f = factorial;
factorial = null;
f(4); // TypeError: factorial is not a function

我们可以简单地使用一个 hack 来解决 —— 使用 arguments.callee，它永远指向函数本身：

function factorial(n) {
  return n ? (n * arguments.callee(n - 1)) : 1;
}

var f = factorial;
factorial = null;
f(4);

然后... 又要一脸懵逼了，因为有了 strict 模式，如下：

'use strict'

~function func() {
  arguments.callee;
  // TypeError: 'caller', 'callee', and 'arguments' properties may not be accessed on strict mode functions or the arguments objects for calls to them
}();

所以有什么办法比较好呢？

让我们回到递归本身来。在面试的时候，我们经常问起一个问题 —— 如何拍平一个数组。如：

var arr = [1, [2, [3, [4], 5], 6], 7];
(function flatten(arr) {
  var newArray = [];
  // your code here

  return newArray;
})(arr);

那么，如果使用递归的话，可以如何实现呢？

[sofish]

一些实现：

1. 普通青年

var arr = [1, [2, [3, [4], 5], 6], 7];

function flatten(arr, ret) {
  if(!ret) ret = [];
  for(var i = 0, j = arr.length; i < j; i++) {
    Array.isArray(arr[i]) ? flatten(arr[i], ret) : ret.push(arr[i]);
  }
  return ret;
};

console.log(flatten(arr));

2. 文艺青年

var arr = [1, [2, [3, [4], 5], 6], 7];

function flatten(arr) {
  return arr.reduce(function(ret, cur) {
    return ret.concat(Array.isArray(cur) ? flatten(cur) : cur);  
  }, []);
};

console.log(flatten(arr));

3. 二逼少年

var arr = [1, [2, [3, [4], 5], 6], 7];

function flatten(arr) {
  return arr.join(',').split(',').map(Number);
};

console.log(flatten(arr));

当然，如果数组小于三层，可以用一个新的模式 —— 抖机灵少年模式：

var arr = [1, 2, [3, 4, 5], 6, 7];

function flatten(arr) {
  return [].concat.apply([], arr);
};

console.log(flatten(arr));