Javascript递归遍历树

递归是一个很常用的算法，虽然，因为调用栈的原因，资源消耗比较大，但其简单优雅的用法，使之广受欢迎。递归常用在不可预期层级数的树形数据结构遍历。

递归有三个基本的概念：入栈、出栈、出口。这三个概念说简单也简单，说复杂也复杂，关键在于对函数的理解，这里不展开讨论该内容。

由于，经常需要在前端遍历菜单等树形结构，又不想每次翻以前的夹杂着业务逻辑的代码，这里干脆做一个原始的深度优先遍历demo，以备查阅。

<ul id="ul"></ul>

var menu = {
  text: 'root',
  childMenu: [{
    text: 'menu 1',
    childMenu: [{
      text: 'child menu 1',
      childMenu: null
    }, {
      text: 'child menu 2',
      childMenu: null
    }]
  }, {
    text: 'menu 2',
    childMenu: null
  }, {
    text: 'menu 3',
    childMenu: null
  }]
}

var str = '';

function recursion(data) {
  var child = data.childMenu;
  // 出口
  if (child == null) {
    str += '<li>' + data.text + '</li>'
    return;
  }
  // 进入子级
  if (child.length) {
    // 入栈前，拼接前置标签
    str += '<li><span>' + data.text + '</span><ul>'
    for (var i = 0; i < child.length; i++) {
      recursion(child[i])
    }
    // 出栈后，拼接后置标签
    str += '</ul></li>'
  }

  return str;

}

ul.innerHTML = recursion(menu)