javascript - 根据递归期间更改的值打破多重递归

Question

编辑:除了这个问题的其他解决方案之外，我还很想了解这种递归或递归问题是否有模式，我使用的技术是否有一个名称(即通过根据对象的更改中断 future 递归的引用)？这个技术在其他一些场景中有用吗？

我正在寻找 nAry 树中的值，一旦找到，我想打破递归(还有其他基本情况来打破该示例)。代码如下所示:

function getCommentById(root, commentId, foundComment) {
  if (root.id === commentId) {
    return root;
  }

  if (foundComment.comment) {
    return foundComment.comment;
  }

  if (!root.comments) {
    return foundComment.comment;
  } else {
    for (let i = 0; i < root.comments.length; i++) {
      foundComment.comment = getCommentById(
        root.comments[i],
        commentId,
        foundComment
      );
    }
  }

  return foundComment.comment;
}

基本上，我正在浏览嵌套评论，通过其 ID 查找评论。

我必须迭代当前评论的所有子级并递归调用此函数。假设我在当前评论的 child1 中找到了评论，我不想进一步递归，只是跳出递归，但循环将继续到下一个同级并递归。 这种事情在二叉树中很容易，因为我可以做类似的事情

return getCommentById(left) || getCommentById(right)

但是我在这里实现相同的逻辑时遇到了麻烦，因为我们需要以某种方式存储每个子调用的结果，并根据该结果决定我们是否找到了该值。所以我的解决方案使用一个辅助变量来表示何时找到该值。我发现这需要是一个对象而不是变量，以便在后续从 child1 到 child2 的递归调用中可以看到值的变化。如果我只是使用一个标志并将其在 child1 递归中设置为 true，这是不可能的，因为那样 child2 递归仍然会将该标志视为 false 并继续递归。

有更好的方法吗？ 这种使用对象引用来打破递归的技术有名称吗？还可以如何实现这一点？

编辑:用于测试的数据集

const post = {
id: "post1",
title: "Sample Post 1",
description: "This is a sample post",
createdBy: "user1",
createdAt: new Date(),
comments: [
  {
    id: "post1comment1",
    text: "This is comment 1",
    userId: "user1",
    timestamp: new Date().setFullYear(2018),
    comments: [
      {
        id: "post1comment1.1",
        text: "This is sub comment 1 of comment 1",
        userId: "user2",
        timestamp: new Date()
      }
    ]
  },
  {
    id: "post1comment2",
    text: "This is comment 2",
    userId: "user4",
    timestamp: new Date()
  },
  {
    id: "post1comment3",
    text: "This is comment 3",
    userId: "user4",
    timestamp: new Date()
  }
]
  },

用法:

const foundComment = { comment: null };
getCommentById(post, "post1comment1.1", foundComment);

Answer 1

您可以使用基于迭代堆栈的树遍历方法。这是基本思想:

function find_thing(root) {
  var stack = [ root ];
  
  while(0 < stack.length) {
     var current_thing = stack.pop();
     if(is_the_thing(current_thing)) {
       return current_thing;
     }
     
     stack = stack.concat(current_thing.AllMyKids());
  }

  return null;
}