如何在递归函数中跳出循环？

Question

我正在使用一个类别对象数组，其中包含一个子类别对象的数组。问题在于这个嵌套数据的深度未知（并且可能会改变）。 （请参见底部示例。）我的目标是返回到类别对象的“路径”，但我遇到了各种困难。

理想情况下，像findCategory('b4')这样的东西将返回：['c1'，'d2'，'d3'，'b4']（请参见示例）。

我认为我的问题是我在处理递归引起的嵌套循环时遇到了麻烦。有时我的路径中会有额外的类别，或者当我认为我已经跳出循环时，一些更深层次的嵌套类别会出现在路径中。

结果可能看起来像这样。显然，它没有在b4处结束循环，而且我不确定为什么结果被找到两次。

b4
FOUND
["c1", "d2", "d3", "b4"]
e2
FOUND
["c1", "d2", "d3", "b4", "e2"] 

如果您能展示一个underscore.js版本，将会有额外的奖励。

这里是JSFiddle链接...

// Start function
function findCategory(categoryName) {
    var trail = [];
    var found = false;

    function recurse(categoryAry) {

        for (var i=0; i < categoryAry.length; i++) {
            console.log(categoryAry[i].category);
            trail.push(categoryAry[i].category);

            // Found the category!
            if ((categoryAry[i].category === categoryName) || found) {
                console.log('FOUND');
                found = true;
                console.log(trail);
                break;

            // Did not match...
            } else {

                // Are there children / sub-categories? YES
                if (categoryAry[i].children.length > 0) {

                    console.log('recurse');
                    recurse(categoryAry[i].children);

                // NO
                } else {
                    trail.pop();
                    if (i === categoryAry.length - 1) {
                        trail.pop();
                    }
                }
            }

        } 
    }

    return recurse(catalog);
}

console.clear();
console.log(findCategory('b4'));

例如，数组类别对象，带有嵌套的类别对象数组。假设嵌套深度未知。

var catalog = [
{
    category:"a1",
    children:[
        {
            category:"a2",
            children:[]
        },
        {
            category:"b2",
            children:[
                {
                    category:"a3",
                    children:[]
                },
                {
                    category:"b3",
                    children:[]
                }
            ]
        },
        {
            category:"c2",
            children:[]
        }
    ]
},
{
    category:"b1",
    children:[]
},
{
    category:"c1",
    children:[
        {
            category:"d2",
            children:[
                {
                    category:"c3",
                    children:[]
                },
                {
                    category:"d3",
                    children:[
                        {
                            category:"a4",
                            children:[]
                        },
                        {
                            category:"b4",
                            children:[]
                        },
                        {
                            category:"c4",
                            children:[]
                        },
                        {
                            category:"d4",
                            children:[]
                        }
                    ]
                }
            ]
        },
        {
            category:"e2",
            children:[
                {
                    category:"e3",
                    children:[]
                }
            ]
        }
    ]
}
];

- jmk2142

---

不要中断，只需返回而不再调用该函数。 - Dagg Nabbit

只需将 break; 替换为 return; 吗？ - jmk2142

没错，那应该可以解决问题（我想，没有注意到你把这些函数嵌套了两层...但如果你不想再次调用函数，解决方案就是不要调用它）。 - Dagg Nabbit

我猜这就是我的困惑所在。我的意思是，从技术上讲，我只知道可能有一个数组。如果有的话，我会调用它，它已经在飞快地运转了。如果我找到匹配项，那么我已经深陷其中，所以我必须打破它。将break;更改为return;似乎并没有改变输出结果。我的头真的很疼。;-) - jmk2142

你能得到的最接近的答案是：https://dev59.com/BGoy5IYBdhLWcg3wFqNT - OnesimusUnbound

Answer 1

尝试

function findCategory(categoryName) {
    var trail = [];
    var found = false;

    function recurse(categoryAry) {

        for (var i = 0; i < categoryAry.length; i++) {
            trail.push(categoryAry[i].category);

            // Found the category!
            if ((categoryAry[i].category === categoryName)) {
                found = true;
                break;

                // Did not match...
            } else {
                // Are there children / sub-categories? YES
                if (categoryAry[i].children.length > 0) {
                    recurse(categoryAry[i].children);
                    if(found){
                        break;
                    }
                }
            }
            trail.pop();
        }
    }

    recurse(catalog);

    return trail
}

演示：Fiddle

- Arun P Johny

---

不错，除了返回 trail 之外，你还改了什么？ - Dagg Nabbit

这正是应该有效的。它只需要一个哨兵标志来阻止原始循环继续运行，如果递归函数调用找到了匹配项，则您的代码就能实现这一点。 - Joseph Myers

啊，我现在明白了。该睡觉了 ;) - Dagg Nabbit

太好了，我的头有点晕了 - 需要吃饭和睡觉。谢谢大家的友善建议。我明天会深入研究这个问题。 :-) - jmk2142

Answer 2

return语句确实可以工作，但请记住它会在每次循环展开时被调用，这不是你想要的。例如：

// global scope
String matchingVariable;

int getMatch(index count, String input, String[] inputs){

  if(isValid(input) || count < inputs.length){
    // your condition is met and break
    // assign your value to global scope variable 
    matchingVariable = input;
  }else if(matchingVariable ==null){
     ++count
     if(count < inputs.length){
       getMatch(count, input+inputs[count], inputs)
     }

    // NOTE RETURN - I WOULDN'T DO THIS
    return input;  

   // doesn't work instead assign the input to global scope variable when a match is found.
  }

}

- Anand Kishore

---

期望一个 JavaScript 递归函数。 - Nithin P.H

Answer 3

我改编了 @arun-p-johny 的答案以满足我的需求，避免使用嵌套递归函数（每次调用时都需要重新定义，可能效率低下）和外部状态。

在我的情况下，我需要获取与文件路径类似的匹配路径。

// Generic function to return matching node path.
// Usage: const path = findMatch(data, key, value);
// Can ignore last 2 params. They will be initialized internally on first call.
function findMatch(entries, key, value, path, tracker) {
  if (!path) { path = []; }
  if (!tracker) { tracker = { found: false }; }

  for (var i = 0; i < entries.length; i++) {
  path.push(entries[i].name); // <----- whatever we want in the final returned value
  if (entries[i][key] === value) {
      tracker.found = true;
      return path.join("/");
  } else {
      if (entries[i].entries) {
          findMatch(entries[i].entries, key, value, path, tracker);
          if (tracker.found) {
              return path.join("/");
          }
      }
  }
  path.pop();
  }
}

const dirs = [{"name":"web","id":1,"entries":[{"name":"localfiles","id":2},{"name":"remotefiles","id":3,"entries":[{"name":"remote1.js","id":4},{"name":"scripts","id":5,"entries":[{"name":"run.sh","id":6}]}]}]},{"name":"mobile","id":6,"entries":[{"name":"assets","id":7,"entries":[{"name":"images","id":8,"entries":[{"name":"logo.png","id":9},{"name":"banner.png","id":10},{"name":"location.png","id":11}]}]},{"name":"src","id":12,"entries":[{"name":"index.js","id":13}]}]}];

// Partial funtions to mtch by a specific property
const getFilePathById = (dirs, id) => findMatch(dirs, 'id', id);
const getFilePathByName = (dirs, name) => findMatch(dirs, 'name', name);

console.clear();
console.log('getFilePathById:', getFilePathById(dirs, 4));
console.log('getFilePathByName:', getFilePathByName(dirs, 'remote1.js'));

通过接受子键和我们想要返回值的键，可以使其更加通用。

- manikanta