JS递归与二叉树的遍历

貌似大部分语言中的递归都差不多， 之所以在标题加JS是因为搜了下后感觉网上用js来描述这概念的不多， 简单地说递归就是函数调用自己的过程。下面的栗子可以很直观地展示递归的执行过程：

function rec(x){
if(x!==1){
   console.log(x)
    rec(x-1)
   console.log(x) 
   }   
}
rec(5) //输出为5 4 3 2 2 3 4 5

由这个栗子?可知：在递归调用语句前的语句执行是正常顺序， 但是递归调用语句后的执行却是相反的也就是说在递归还没有完成时，函数的输出结果暂时被挂起，因为一般在计算机中，是以栈的形式来实现递归，这个过程如下：

5 rec(4)     //第一级
5 4 rec(3)   //第二级
5 4 3 rec(2)  //第三级
5 4 3 2 rec(1)  //第四级
console.log() 2 3 4 5  //以出栈形式输出结果

当递归完成时， 执行流开始处理上一级递归中的递归语句后面的语句， 在这里是输出当前变量console.log(x)

递归非常适用于相同函数不同参数的迭代循环。但是因为需要为每一级的递归开辟内存所以递归的开销相对来说蛮大的， 在很多编程的语言中,对于递归的开销问题有个TCO优化（Tail Call Optimization）戳这篇博客了解更多?[翻译] JS的递归与TCO尾调用优化

之所以想起码这篇博客，是因为最近看《算法与数据结构JavaScript描述》（请拉黑此书，bug极多，极不推荐）中使用递归遍历二叉树的算法挺绕的， 写篇博客厘清下。
这里直接借用原书的代码(有删改)， 以二叉树的的中序遍历为例：

// 节点对象的构造函数
function Node(data, left, right) {
   this.data = data;
   this.left = left;
   this.right = right;
   this.show = show;
}

function show() {
   return this.data;
}
//二叉树的构造函数
function BST() {
   this.root = null;
   this.insert = insert;
   this.inOrder = inOrder;
   
}
//插入方法
function insert(data) {
   var n = new Node(data, null, null);
   if (this.root == null) {
      this.root = n;
   }
   else {
      var current = this.root;
      var parent;
      while (true) {
         parent = current;
         if (data < current.data) {
            current = current.left;
            if (current == null) {
               parent.left = n;
               break;
            }
         }
         else {
            current = current.right;
            if (current == null) {
               parent.right = n;
               break;
            }
         }
      }
   }
}
//调用两次递归遍历二叉树
function inOrder(node) {
   if (!(node == null)) {
      inOrder(node.left);
      console.log(node.show() )
      inOrder(node.right);
   }
}

//将以下数据导入二叉树
nums.insert(23)
nums.insert(45)
nums.insert(16)
nums.insert(37)
nums.insert(3)
nums.insert(99)
nums.insert(22)

  
//中序遍历二叉树
inOrder(nums.root)  
 /*
输出结果为：
 3
 16
 22
 23
 37
 45
 99
*/

在inOrder函数中使用了两次递归，它的执行顺序是：沿左边找到最小值3，第一次递归完成， 之前被挂起的语句开始以出栈的形式执行，输出无子节点的节点3，然后回到上一级递归，输出其上一级递归中的节点16， 在节点16处， 存在子节点，于是执行向右递归，执行到无子节点的22，输出22后返回到节点16 ， 执行流继续往回执行， 执行到根节点23，输出23后又插入一次向右递归，右递归到45， 存在左子节点，执行向左递归， 以此类推，就完成了这棵二叉树的中序遍历

附张遍历顺序示意图：