递归

递归就是将一个问题分解成一个或者几个相似的子问题解决的方法

递归需要满足的条件

1. 问题本身可以被分解为一个或者几个类似的子问题
2. 子问题除了数据规模，解决思路要和问题本身相似
3. 有终止条件

如何写递归代码

1. 找到递推公式( 就是将问题分解成几个子问题 )
2. 找到终止条件

比如斐波那契数列，递推公式就是 f(n) = f(n-1) + f(n-2)，终止条件就是 n = 1, f(1) = 1; n = 2, f(2) = 1，所以就可写出如下递归代码：

function fibonacci(n) {
  if(n <= 2) {
    return 1;
  }
  return fibonacci(n-1) + fibonacci(n-2);
}

注意点

1. 小心堆栈溢出( 因为递归的本质就是栈的入栈出栈 )
2. 小心重复的计算( 比如上面的代码，计算 f(5) 时，就要去重复的去计算 f(3) )
3. 空间成本

上述问题都可以通过一些手段解决：
比如对于第一点，可以限制递归的层数，超过限定层数就报错，或者手动模拟递归的入栈出栈过程，通过循环解决

var f = function () {
  if(f.depth > 1000) {
    f.depth = 0;
    throw new Error();
  }
  f.depth++;
  if(n <= 2) {
    return 1;
  }
  return fibonacci(n-1) + fibonacci(n-2);
}
f.depth = 0;

对于第二点，则可以使用一个map将已经计算过的结果缓存起来，然后在计算前先在缓存中查找，或者也可以将递归改成循环的方式

// map缓存计算结果
var map = { 1: 1, 2: 1 };
function fibonacci(n) {
  if(map[n]) {
    return map[n];
  }
  var sum = fibonacci(n-1) + fibonacci(n-2);
  map[n] = sum;
  return sum;
}

// 循环
function f(n) {
  if(n <= 2) {
    return 1;
  }
  var prepre = 1;
  var pre = 1;
  var result = 0; 
  for(var i=3; i<=n; i++) {
    result = prepre + pre;
    prepre = pre;
    pre = result;
  }
  return result;
}