杜龙少(sdvdxl)

递归查找的问题

字数统计: 1.1k阅读时长: 4 min
2020/03/14 Share

背景

前几天在开发过程中遇到一个需求,前端需要动态渲染一个菜单,这个菜单是一个树状结构,就是每个菜单中可能有多个子菜单,子菜单中又有子菜单,同时呢,每个菜单都可以单独绑定一个页面。为了加速前端加载页面和渲染速度,后端一次性将整个菜单和页面信息用树形结构返回给前端,结构大概如下(主菜单不算在后端返回的数据中,只是前端的一个入口,黄色虚线框中的数据才是真正需要的):

菜单结构

转化为树结构:

树结构

后端将如上数据结构返回给了前端,前端需要将其加载为树型结构。

同时另一个需求是点击某个菜单,如果有页面那么就直接展示其对应的第一个也没,如果没有需要继续找子菜单的第一个页面,都没有那就不显示页面。

按照上图所展示的数据,那么,如果点击 主菜单,那么需要战士 页面1-1-1-P1,也就是红色展示的部分;如果点击 菜单2 那么需要展示 页面2-P1,也就是绿色展示的部分。

实现

需求有了,数据也有了,那么我们考虑实现方式。

首先这个是树,如果加上主目录的话,算是1棵有多个节点的数;如果不算主目录那么算是多棵树。

不管是1棵树,还是多棵树的方式考虑,都是采用深度优先遍历的,这里呢我们按照多棵树遍历的方式使用js实现了一下:

1
2
3
4
5
6
7
8
9
10
11
12
13
function getFirstPage(list) {
for (const item of list) {
if (item.pages && item.pages.length) {
let path = (item.pages[0] || {}).path
console.log('第一个页面', item.pages[0])
return;
} else if (item.children && item.children.length) {
getFirstPage(item.children)
}
}
}

var list = [{"name":"菜单1","children":[{"name":"菜单1-1","children":[{"name":"菜单1-1-1","pages":[{"name":"页面1-1-1-P1"}]}]}]},{"name":"菜单2","pages":[{"name":"页面2-P1"},{"name":"页面2-P2"}]},{"name":"菜单3"}]

拷贝上面代码,粘贴到浏览器控制台(console)中,回车,然后输入 getFirstPage(list)并回车,将会得到执行结果:

执行结果

好像结果不太对,我们期望得到的应该是 页面1-1-1-P1,但是却打印出了2条页面信息。

问题排查

让我们再来看一下执行的代码:

执行的代码
红框里面很明显是找到页面就退出函数,为什么打印了2个信息?肯定是函数被重复执行了。

我们可以写个js脚本,并放到html里面执行,这样我们可以在浏览器里面debug该函数。

DEBUG

我们在 return 的地方增加一个断点,然后直接运行,当运行到该断点的时候,我们看到右侧degbug信息栏中的函数调用堆栈出现了3个 getFirstPage 函数,这是因为我们在上面的代码中使用了递归查找方式,执行递归的时候,对应的函数会被压入栈底,然后函数执行完毕的时候再从栈最上面开始弹出。

需要注意的是,虽然栈顶的函数执行完毕了,但是不代表整个栈的函数都会全部结束它的生命周期,它们还是会按照普通函数那样继续执行完毕。

这就类似下面这个图,执行1次该函数,就会再套一层,而每层之间是独立的,之间的逻辑并不会相互影响。
套娃

下面的图演示了函数栈的运行状况,注意观察函数运行的同时,观察右边函数调用

过程

所以为了能够在找到数据后就返回,不再继续执行栈底的函数的内部逻辑,我们需要加一个判断条件,找到了就不再继续执行了,修改代为:

修改后的正确处理流程

注意红框内的内容,需要在函数外部定义1个变量,如果找到了设置为true,最后判断一下,如果true,那么retrun,不再继续执行函数。

总结

递归需要注意终结条件,否则就会出现非预期的结果。

原文作者:杜龙少(sdvdxl)

原文链接:https://todu.top/posts/e899/

发表日期:2020-03-14 17:55:56

更新日期:2020-03-24 09:29:27

版权声明:本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 背景
  2. 2. 实现
  3. 3. 问题排查
  4. 4. 总结