理解递归算法

递归算法的概念

递归（Recursion）在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法，其核心思想是分治策略。 递归式方法可以被用于解决很多的计算机科学问题，因此它是计算机科学中十分重要的一个概念。绝大多数编程语言支持函数的自调用，在这些语言中函数可以通过调用自身来进行递归。

关于递归算法

在日常开发中，我们使用循环语句远远大于递归，但这不能说明递归就没有用武之地，实际上递归算法的解决问题的步骤更符合人类解决问题的思路，这是递归算法的优点，同时也是它的缺点。递归算法是比较好用，但是理解起来可能不太好理解，所以在递归算法和循环算法对比中，流行一句话：人理解循环，神理解递归。当然这只是一个段子，不过也从侧面反映出递归算法不容易理解的事实。这个我自己也深有体会，就拿排序算法里面的快排和归并排序来说吧，这两种算法采用的都是分治思想来处理排序问题，所以递归在这里就出现了，如果你不理解递归算法，就去学习这两种排序算法，可能理解起来就非常费事，尽管你知道这两种排序的算法原理和它的时间及空间复杂度，但就是不知道它是如何使用递归完成的，所以学习和理解递归算法是非常有必要的。

实际上递归算法的使用场景，远不止上面说的排序算法，在链表，树，图及其他只要符合分治思想的问题中，其实都可以采用递归来处理。

自己调用自己，就叫递归。

编写正确的递归算法，一定要有 ”归“ 的步骤，也就是说递归算法，在分解问题到不能再分解的步骤时，要让递归有退出的条件，否则就会陷入死循环，最终导致内存不足引发栈溢出异常。

1. 阶乘

阶乘计算是最简单的用来展示递归的一个案例。
5!=5 * 4!
4!=4 * 3!
...
1!=1*0!
在对阶乘计算中，我们第一步是分治，把复杂的大的问题，给拆分成一个一个小问题，直到不能再拆解，通过退出条件retrun，然后再从最小的问题开始解决，只到所有的子问题解决完毕，那么最终的大问题就迎刃而解。
所以实现阶乘的方法就迎刃而出了：

function factrial(n){
  if(n<1){
    return 1;
  }
  // 当n>=1时，返回值为n*（n-1）！
  return  n*factrial(n-1);
}

console.log(factrial(3))
// 6

2. 斐波那契数列

斐波那契数列由0和1开始，之后的斐波那契系数就是由之前的两数相加而得出。前几个斐波那契系数是：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233....。我们可以发现以下规律：
斐波那契第0位：0
斐波那契第1位：1
斐波那契第2位：1（斐波那契第1位+斐波那契第0位）
斐波那契第3位：2（斐波那契第2位+斐波那契第1位）
斐波那契第4位：3（斐波那契第3位+斐波那契第2位）
...
斐波那契第n位：3（斐波那契第n-1位+斐波那契第n-2位）
所以我们可以通过以下方法实现对任意位斐波那契数列的求解：

function fibonacci(n){
  // 当n为0时，返回值为0
  if(n==0){
    return 0
  }
  // 当n为1时，返回值为1
  if(n==1){
    return 1
  }
  //当n>1时，返回值为前两位斐波那契数之和
  return fibonacci(n-1)+fibonacci(n-2)
}

console.log(fibonacci(6))
// 8

3.十进制转二进制

下面的例子为使用递归实现十进制转二进制，关键在于一直除2一直到除不尽2为止，具体的算法作为程序员应该没有不知道的。

function tenToTwo(number){
  // 除2后的商
  var intNum = Math.floor(number/2)
  // 除2后的余数
  var restNum = number%2
  if(intNum>1){
    // 除2后的的商大于1，需要继续除2
    // 商的二进制转换+余数
    return tenToTwo(intNum)+new String(restNum)
  }else{
    // 这步为归的步骤：商+余数
    return new String(intNum)+new String(restNum)
  }
}
console.log(tenToTwo(100))
// "1100100"

4. array to tree

在网上看到一道阿里的面试题，感觉比较有意思，可以通过递归的方式来解决：

题目截图

题目一样是对于问题的一个拆解而已，从根级开始，一级一级找出所有对应的节点，这里避免不了循环：

const comments = [
 {id: 1, parent_id: null, sort: 0, name: '菜单1'},
 {id: 2, parent_id: 1, sort: 0, name: '菜单1-1'},
 {id: 3, parent_id: 1, sort: 0, name: '菜单1-2'},
 {id: 4, parent_id: 2, sort: 2, name: '菜单1-1-2'},
 {id: 5, parent_id: 2, sort: 1, name: '菜单1-1-1'},
 {id: 6, parent_id: null, sort: 0, name: '菜单2'},
 {id: 7, parent_id: 6, sort: 0, name: '菜单2-1'},
 {id: 8, parent_id: 6, sort: 0, name: '菜单2-2'},
 {id: 9, parent_id: 8, sort: 2, name: '菜单2-2-2'},
 {id: 10, parent_id: 8, sort: 1, name: '菜单2-2-1'},
 {id: 11, parent_id: 10, sort: 0, name: '菜单2-2-1-1'},
];
function getTree(data, root, id_key ='id', parent_id_key='parent_id', child_key='children') {
    // 递归方法
    function getNode(id) {
      var node = []
      for (var i = 0; i < data.length; i++) {
        if (data[i][parent_id_key] == id) {
          // 判断是不是这个父节点下面的子节点。
          data[i][child_key] = getNode(data[i][id_key])
          node.push(data[i])
        }
      }
      if (node.length == 0) {
        return
      } else {
        return node
      }
    }
    // 使用根节点
    return getNode(root)
  }

getTree(comments, null)