递归、回溯、剪枝

递归

一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。

回溯 & 剪枝

回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。

剪枝与回溯不同的是，在遍历树中，若某一节点不符合要求，则直接去除，终止函数，不“回溯”返回任何值。

深度优先遍历

深度优先，简洁的理解是宏观上是从左到右遍历枝，每次迭代中直到分支的叶子。

js 代码的执行符合深度优先的逻辑，通过该逻辑来设计回溯中回退引用数据方案。

联系与应用

回溯与剪枝常用于递归操作中，作为优化性能的手段，减少运算量。

常见的，当递归中传递了了引用类型数据，且未在每次递归函数中深拷贝该数据，该种情形，一般要使用 回溯 ，在回溯到上一节点时，对引用数据做回退。

比如每层传递数组arr，都是arr.push(1)，则回溯后，应进行arr.pop()的操作

若递归过程中未有引用数据的介入，则可以直接 剪枝，不去回退任何数据。

尾递归

递归是函数在结束 return 语句中，递归了其本身，但不是简单的调用，往往还附带一些变量运算，这就导致在递归返回之前，当前作用域上下文不能弹栈，需要保持，这也是所有递归都有的问题，会比较大地消耗内存。

例如下列的例子的阶乘运算，就是一种递归，堆栈中需要较长时间的保持参数 n 极调用记录。

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

尾递归是指递归函数的调用发生在函数最后，且在 return 语句中，仅具有递归函数本身，例如将上述阶乘运算做如下修改。

function factorial(n, total) { 
    if (n === 1) return total; 
    return factorial(n - 1, n * total); 
} 
factorial(5, 1) // 120

这就是一种尾递归，由于当前作用域语句执行结束，作用域内没有后续操作，换句话说没有后续作用域变量参与操作，所以可以直接弹栈，节省内存。