如何在递归函数中突破循环？ [英] How do I break out of loops in recursive functions?

问题描述

我正在处理一组类别对象，这些对象可以包含子类别对象数组。棘手的部分是这个嵌套数据的深度是未知的（并且可以改变）。 （请参阅底部的示例。）我要做的是返回类别对象的踪迹，但我遇到各种各样的困难。

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.

理想情况下类似 findCategory（'b4'）会返回： ['c1'，'d2'，'d3'，'b4'] （参见示例）。

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

我认为我的问题是我在正确分解由递归引起的嵌套循环方面遇到了麻烦。有时我会在我的路上获得额外的类别，或者当我认为我已经爆发时，一些更深层次的嵌套类别最终会出现在路径中。

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.

一个结果可能看起来像这个。显然它不会在b4处杀死循环，我不确定为什么结果被发现两次。

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
FOUND
["c1", "d2", "d3", "b4"]
e2
FOUND
["c1", "d2", "d3", "b4", "e2"] 

如果你还能给我看一个underscore.js版本，你可以获得奖励。

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

JSFiddle Link 此处......

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

推荐答案

尝试

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
}

演示：小提琴

这篇关于如何在递归函数中突破循环？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！