用户界面数据结构和算法：递归和javascript模型代码

递归意味着自我调整。递归是用户界面中比较常见的算法。假设有一组数据要处理，并且下一个请求必须在上一个请求完成之前完成。一种是使用本文提到的 Promise。但有时你不想引入 Promise，你可以简单地先处理它。目前，您可以使用递归，如下代码所示：

var ids = [34112, 98325, 68125];
(function sendRequest(){
    var id = ids.shift();
    if(id){
        $.ajax({url: "/get", data: {id}}).always(function(){
            //do sth.
            console.log("finished");
            sendRequest();
        });
    } else {
        console.log("finished");
    }
})(); 
复制代码

上面的代码定义了一个 sendRequest 函数，然后在请求完成时自行调整。每次调用之前获取一大块数据。如果表为空，则表示处理完成。这样就简单的实现了非阻塞批量请求的功能。

我们来说另一个场景：DOM树。

由于DOM是一棵树，并且树本身的定义是递归定义的，所以使用递归的方法来处理树是非常简单和自然的。例如，使用递归实现DOM查询函数document.getElementById。

function getElementById(node, id){
    if(!node) return null;
    if(node.id === id) return node;
    for(var i = 0; i < node.childNodes.length; i++){
        var found = getElementById(node.childNodes[i], id);
        if(found) return found;
    }
    return null;
}
getElementById(document, "d-cal");复制代码

文档是 DOM 树的根节点。通常从文档开始向下搜索。在for循环中，首先找到文档中的所有子节点，然后逐层递归地找到它们的子节点。如果到达叶子节点但没有找到，则根据第二行代码返回null。返回后，for循环中的i加1，继续到下一个子节点。如果当前节点的ID满足搜索条件，则逐层返回。所以这是深度的第一遍，从根节点开始一直到叶子节点，然后从底部向上返回。

最后在控制台确认即可。执行结果如下图：

使用递归的优点是代码简单易懂，缺点是效率不如非递归实现。 Chrome 浏览器使用非递归实现来验证 DOM。如何实现非递归？

如下代码：

function getByElementId(node, id){
    //遍历所有的Node
    while(node){
        if(node.id === id) return node;
        node = nextElement(node);
    }
    return null;
}复制代码

依然是按顺序遍历所有DOM节点，不过这次改为while循环，函数nextElement负责寻找下一个节点。所以关键是如何非递归地实现这个nextElement，如下代码所示：

function nextElement(node){
    if(node.children.length) {
        return node.children[0];
    }
    if(node.nextElementSibling){
        return node.nextElementSibling;
    }
    while(node.parentNode){
        if(node.parentNode.nextElementSibling) {
            return node.parentNode.nextElementSibling;
        }
        node = node.parentNode;
    }
    return null;
}复制代码

还是使用深度遍历，先找到当前节点的子节点，如果有子节点，则下一个元素是它的第一个子节点，否则判断是否有相邻元素，如果有则返回下一个相邻元素。如果没有子节点，也没有下一个相邻元素，则返回其父节点向上的下一个相邻元素，相当于上面递归实现中for循环中的i加1。

在控制台也正确打印结果。无论是非递归还是递归，它们都是深度优先遍历。流程如下图所示。

实际上，浏览器使用哈希映射存储 getElementById，该哈希映射通过 ID 直接映射到 DOM 节点，而 getElementsByClassName 使用此类非递归查找。

作者：人人FED
来源：掘金