V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
xingyue
V2EX  ›  问与答

请问这个函数如何改写成尾递归?

  •  
  •   xingyue · 2019-08-28 00:43:23 +08:00 · 2064 次点击
    这是一个创建于 1906 天前的主题,其中的信息可能已经有所发展或是发生改变。

    今天在写一个层级菜单选中高亮的逻辑的时候,无意看到“尾递归”这个概念。看了阮老师的 一篇文章 感觉很好理解,但是当我尝试去把我的递归逻辑进行修改时,感觉无从下手,请大佬指导一下 O.O
    下面的代码在 codepen 上也放了个方便看些 求助,如何优化递归

    let menuList = [
      {
        path: '/A',
        selected: true
      },
      {
        path: '/B',
        selected: false,
        children: [
          {
            path: '/B/B-1',
            selected: false
          }
        ]
      },
      {
        path: '/C',
        selected: false,
        children: [
          {
            path: '/C/C-1',
            selected: false
          },
          {
            path: '/C/C-2',
            selected: false,
            children: [
              {
                path: '/C/C-2/C-2-1',
                selected: false
              }
            ]
          }
        ]
      }
    ];
    
    function checkSelected(path) {
      menuList = recursive(menuList, path);
    
      function recursive(list, path) {
        return list.map(item => {
          if (item.children && item.children.length) {
            item.children = recursive(item.children, path);
          }
          return {
            ...item,
            selected: path.includes(item.path)
          };
        });
      }
    }
    
    6 条回复    2019-08-28 19:42:25 +08:00
    msg7086
        1
    msg7086  
       2019-08-28 00:48:03 +08:00   ❤️ 1
    尾递归类似 BFS。
    leishi1313
        2
    leishi1313  
       2019-08-28 04:16:22 +08:00   ❤️ 1
    你这貌似是个树状结构啊,做不了尾递归的。因为要遍历你必要要保存父节点的信息,那么要么用函数栈(正常递归),要么用个 array,空间复杂度都是 O(n)。
    ikaiguang
        3
    ikaiguang  
       2019-08-28 09:21:23 +08:00
    参考下这里的菜单选中,说不定有收获。
    https://gitee.com/ikaiguang/bootstrap-vue-admin
    鄙人写的。现无时间维护更新
    wszgrcy
        4
    wszgrcy  
       2019-08-28 10:16:25 +08:00 via Android   ❤️ 1
    尾递归我记得之前查 caniuse 说只有 ios 上浏览器支持?还是我记错了
    bumz
        5
    bumz  
       2019-08-28 11:04:55 +08:00 via iPhone   ❤️ 1
    尾递归等价于循环
    你想想用循环怎么实现,再改成尾递归会比较容易(手动狗头)

    你的情况,因为树形结构,想用循环需要加个栈,不如老老实实递归 (手动狗头
    xingyue
        6
    xingyue  
    OP
       2019-08-28 19:42:25 +08:00
    @wszgrcy #4 你没记错,曾经支持过一段时间后来又删了,未来可能支持,参见 https://v8.dev/blog/modern-javascript#proper-tail-calls
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5365 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 08:19 · PVG 16:19 · LAX 00:19 · JFK 03:19
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.