V2EX = way to explore
V2EX 是一个关于分享和探索的地方
Sign Up Now
For Existing Member  Sign In
xingyue
V2EX  ›  问与答

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

  •  
  •   xingyue · Aug 28, 2019 · 2714 views
    This topic created in 2448 days ago, the information mentioned may be changed or developed.

    今天在写一个层级菜单选中高亮的逻辑的时候,无意看到“尾递归”这个概念。看了阮老师的 一篇文章 感觉很好理解,但是当我尝试去把我的递归逻辑进行修改时,感觉无从下手,请大佬指导一下 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 replies    2019-08-28 19:42:25 +08:00
    msg7086
        1
    msg7086  
       Aug 28, 2019   ❤️ 1
    尾递归类似 BFS。
    leishi1313
        2
    leishi1313  
       Aug 28, 2019   ❤️ 1
    你这貌似是个树状结构啊,做不了尾递归的。因为要遍历你必要要保存父节点的信息,那么要么用函数栈(正常递归),要么用个 array,空间复杂度都是 O(n)。
    ikaiguang
        3
    ikaiguang  
       Aug 28, 2019
    参考下这里的菜单选中,说不定有收获。
    https://gitee.com/ikaiguang/bootstrap-vue-admin
    鄙人写的。现无时间维护更新
    wszgrcy
        4
    wszgrcy  
       Aug 28, 2019 via Android   ❤️ 1
    尾递归我记得之前查 caniuse 说只有 ios 上浏览器支持?还是我记错了
    bumz
        5
    bumz  
       Aug 28, 2019 via iPhone   ❤️ 1
    尾递归等价于循环
    你想想用循环怎么实现,再改成尾递归会比较容易(手动狗头)

    你的情况,因为树形结构,想用循环需要加个栈,不如老老实实递归 (手动狗头
    xingyue
        6
    xingyue  
    OP
       Aug 28, 2019
    @wszgrcy #4 你没记错,曾经支持过一段时间后来又删了,未来可能支持,参见 https://v8.dev/blog/modern-javascript#proper-tail-calls
    About   ·   Help   ·   Advertise   ·   Blog   ·   API   ·   FAQ   ·   Solana   ·   843 Online   Highest 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 38ms · UTC 20:50 · PVG 04:50 · LAX 13:50 · JFK 16:50
    ♥ Do have faith in what you're doing.