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

How do I break out of loops in recursive functions?

提问by jmk2142

I'm working with a array of category objects that can have an array of child category objects. The tricky part is that the depth of this nested data is unknown (and can change). (See sample at bottom.) What I'm trying to do is return a "trail" to the category object but I'm having all sorts of difficulties.

我正在使用一组类别对象，这些对象可以有一组子类别对象。棘手的部分是这个嵌套数据的深度是未知的（并且可以改变）。（请参阅底部的示例。）我想做的是将“轨迹”返回到类别对象，但我遇到了各种困难。

Ideally something like findCategory('b4')would return: ['c1', 'd2', 'd3', 'b4'](See sample).

理想情况下，类似的东西findCategory('b4')会返回：（['c1', 'd2', 'd3', 'b4']见示例）。

I think my issue is I'm having trouble with properly breaking out of the nested loops caused by my recursion. Sometimes I'll get extra categories in my trail or when I think I've broken out, some deeper nested category ends up in the trail.

我认为我的问题是我无法正确打破由我的递归引起的嵌套循环。有时我会在我的跟踪中获得额外的类别，或者当我认为我已经突破时，一些更深的嵌套类别最终会出现在跟踪中。

One result might look like this. Clearly it's not killing the loop at b4 and I'm not sure why the result is found twice.

一种结果可能如下所示。显然，它并没有杀死 b4 处的循环，我不确定为什么会发现两次结果。

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

Bonus if you can also show me an underscore.js version.

如果您还可以向我展示 underscore.js 版本，那就太棒了。

JSFiddle Linkhere...

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'));

E.g. The array category objects, with nested array of category objects. Assume the depth of nesting is unknown.

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

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:[]
                }
            ]
        }
    ]
}
];

回答by Arun P Johny

Try

尝试

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
}

Demo: Fiddle

演示：小提琴

回答by Anand Kishore

the return stmt does work but remember it will be called everytime the loop unwinds and that's not what you are looking at. Example

return stmt 确实有效，但请记住，每次循环展开时都会调用它，这不是您要查看的内容。例子

// 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.
  }

}