概念

若一个算法直接地或间接地调用自己本身，则称这个算法是递归算法。

递归含义可以从字面意思理解，递：层层递进，归：层层返回。即把一个问题分解更小的相同子问题，层层推进，处理成功后返回数据，一个递归函数调用自身去解决它的子问题。
如下面这个函数即是递归函数：

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

条件

1. 自己调用自己
2. 结束条件
   如上面例子就是递归实现的一种方式，通过调用自身sum()，且结束条件是1，最后达到求和的目的。

写递归代码的关键就是找到如何将原来的问题转化为更小的同一问题，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件合成最终代码。

注意事项

1. 堆栈溢出
   函数调用会在内存形成一个栈来保存临时变量。每调用一个函数，都会将调用位置和内部变量等信息保存到内存中，等函数执行完成返回时才释放。而递归需要同时保存成千上百个调用帧，非常耗费内存，当数据规模较大的时候很容易发生“栈溢出”错误（stack overflow）。
   
   如遇到这种问题可以在代码中添加一个参数，记录递归调用的次数，当大于这个数的时候，手动设置报错信息。比如说上面的例子可以实现如下：

let count=0;
function sum2(n) {
count++;
if(count>10000){
  console.error('超出最大调用次数');
  return;
}
  if (n == 1) return 1
  return sum2(n - 1) + n
}

当然这个数字事先无法估算，只适合一些最大深度比较低的递归调用。

可参考阮一峰老师的尾调用，进一步理解优化递归的方法函数的扩展-尾调用优化

常见算法

斐波拉契数列

斐波那契数列的是这样一个数列：1、1、2、3、5、8、13、21、34....，即第一项 f(1) = 1,第二项 f(2) = 1.....,第 n 项目为 f(n) = f(n-1) + f(n-2)。求第 n 项的值是多少。

function fib(n) {
  if (n === 1 || n === 2) return n - 1
  return fib(n - 1) + fib(n - 2)
}

爬楼梯

假如楼梯有 n 个台阶，每次可以走 1 个或 2 个台阶，请问走完这 n 个台阶有几种走法

function climbStairs(n) {
  if (n == 1) return 1
  if (n == 2) return 2
  return climbStairs(n - 1) + climbStairs(n - 2)
}

深拷贝

原理: clone(o) = new Object; 返回一个对象

function clone(o) {
  var temp = {}
  for (var key in o) {
    if (typeof o[key] == 'object') {
      temp[key] = clone(o[key])
    } else {
      temp[key] = o[key]
    }
  }
  return temp
}

遍历Dom

递归函数可以非常高效的操作树形结构，在JavaScript有一种"天然的树形结构"浏览器端的文档对象模型（Dom）。每次递归调用时处理指定树的一小段。

/* 我们定义一个walk_the_DOM函数，
1） 它从某个指定的节点开始，按指定HTML源码的顺序，访问树的每个节点
2）它会调用一个函数，并依次传递每个节点给它，walk_the_DOM调用自身去处理每一个节点
*/
var walk_the_DOM = function walk( node , func ) {
  func(node);
  node = node.firstChild;
  while (node) {
    walk( node , func );
    node = node.nextSibling;
   }
}
/* 定义一个getElementByAttribute函数
1） 它以一个属性名称字符串和一个可选的匹配值作为参数
2） 它调用walk_the_DOM，传递一个用来查找节点属性名的函数作为参数，匹配得节点都会累加到一个数组中
*/
      
var getElementsByAttribute=function(att,value){
  var results=[];
  walk_the_DOM(document.body,function(node){
    var actual=node.nodeType===1&&node.getAttribute(att);
    if(typeof actual==='string' &&( actual===value|| typeof value!=='string')){
      results.push(node);
    }
  });
  return results;
}

汉诺塔

"汉诺塔"是印度的一个古老传说，也是程序设计中的经典的递归问题。
塔上有三根柱子和一套直径各不相同的空心圆盘，开始时源柱子上的所有圆盘都按从大到小的顺序排列。目标是通过每一次移动一个圆盘到另一根柱子上，最终把一堆圆盘移动到目标柱子上，过程中不允许把较大的圆盘放置在较小的圆盘上。

寻找规律（把所有的圆盘移动到C）：
　　1）n(圆盘个数) == 1
　　　　第一次：1号盘 A -> C sum(移动次数) = 1
　　2）n == 2
　　　　第一次：1号盘 A -> B
　　　　第二次：2号盘 A -> C
　　　　第三次：1号盘 B -> C　　sum = 3
　　3）n == 3
　　　　第一次：1号盘 A -> C
　　　　第二次：2号盘 A -> B
　　　　第三次：1号盘 C -> B
　　　　第四次：3号盘 A -> C
　　　　第五次：1号盘 B -> A
　　　　第六次：2号盘 B -> C
　　　　第七次：1号盘 A -> C　　sum = 7
　　以此类推...
　　故不难发现规律,移动次数为：sum = 2^n - 1
　　
算法分析（递归）：
　　把一堆圆盘从一个柱子移动另一根柱子，必要时使用辅助的柱子。可以把它分为三个子问题：
　　　　首先，移动一对圆盘中较小的圆盘到辅助柱子上，从而露出下面较大的圆盘，
　　　　其次，移动下面的圆盘到目标柱子上
　　　　最后，将刚才较小的圆盘从辅助柱子上在移动到目标柱子上
　　 把三个步骤转化为简单数学问题：
　　　　（1） 把 n-1个盘子由A 移到 B；
　　　　（2） 把 第 n个盘子由 A移到 C；
　　　　（3） 把n-1个盘子由B 移到 C；
　　我们创建一个JS函数，当它调用自身的时候，它去处理当前正在处理圆盘之上的圆盘。最后它回一个不存在圆盘去调用，在这种情况下，它不在执行任何操作。

var hanoi = function(disc,src,aux,dst){
  if(disc>0){
    hanoi(disc-1,src,dst,aux);
    console.log(' 移动 '+ disc +  ' 号圆盘 ' + ' 从 ' + src +  ' 移动到 ' +  dst);
    hanoi(disc-1,aux,src,dst)
  }
}

参考资料

1. 阮一峰-ECMAScript 6 入门-尾调用优化
2. 汉诺塔-递归算法（JS递归函数）