递归

摘要：冴羽的博客学习递归

递归

程序调用自身的编程技巧称为递归(recursion)。例如：
阶乘

function factorial(n) {
  if (n == 1) return n;
  return n * factorial(n - 1);
}

可以看出：构成递归需具备边界条件、递归前进段和递归返回段，当边界条件不满足时，递归前进，当边界条件满足时，递归返回
递归的特点：
1.大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解
2.不能无限制调用自身，必须有出口——明确的边界条件

尾调用

尾调用就是指某个函数的最后一步是调用另一个函数
例如：

// 尾调用
function f(x){
  return g(x);
}

分析下执行上下文栈变化：

// 伪代码
ECStack.push(<f> functionContext);
ECStack.pop();
ECStack.push(<g> functionContext);
ECStack.pop();

结论：使用尾调用只存在一个调用记录，所以永远不会发生“栈溢出”错误

// 非尾调用，如上面的阶乘
function f(x){
  return x * g(x - 1);
}

分析下执行上下文栈变化：

// 伪代码
ECStack.push(<f> functionContext);
ECStack.push(<g> functionContext);
ECStack.pop();
ECStack.pop();

结论：函数调用自身，称为递归。如果尾调用自身，就称为尾递归。普通递归非常耗费内存，递归层次过多会导致“栈溢出”，而利用尾递归则可以避免
优化阶乘函数：

function factorial(n, res) {
    if (n == 1) return res;
    return factorial(n - 1, n * res)
}
console.log(factorial(4, 1)) // 24

利用占位偏函数：

var newFactorial = partial(factorial, _, 1)
newFactorial(4) // 24