orangewarp orangewarp - 5 months ago 10
Javascript Question

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.

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.

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"]


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

JSFiddle Link here...

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

Answer

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