How do I break out of loops in recursive functions?

Question

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

Just return without calling the function again instead of breaking. — Dagg Nabbit, Apr 26 '13 at 03:53
Yeah, that should do the trick (I think, didn't notice you had those functions nested two levels deep... but if you don't want to call the function again, the solution is not to call it). — Dagg Nabbit, Apr 26 '13 at 03:56
I guess that's where I'm confused. I mean, all I technically know is that there MIGHT be an array. If there is, I call it and it's already steaming ahead. If I do find a match, I'm already knee deep so I have to break out. Changing the `break;` to `return;` didn't seem to change the output. http://jsfiddle.net/7A6hB/3/ My head really hurts. ;-) — jmk2142, Apr 26 '13 at 04:03
The closest you can get http://stackoverflow.com/questions/8779799/how-to-break-the-each-function-in-underscore-js — OnesimusUnbound, Apr 26 '13 at 04:03
Yeah, I saw that one. I can do it (and conceptually understand the breaking out) on a flat array, 1 layer. I think my problem (either real or in my head) is the fact that I have this function that loops, and I'm producing these subroutines through recursion. So I'm missing some logic to keep them under control. — jmk2142, Apr 26 '13 at 04:07
Ah, I see what's going on there. It's not just recursive, it's sort of "massively recursive," kicking itself off potentially several times for each loop. Hmm... — Dagg Nabbit, Apr 26 '13 at 04:08
Hey guys, is this a bad question? (-1) I think the content here could help people. I couldn't quite find something along these lines which led me to ask it. But maybe it would benefit from editing the question itself to target the heart of the content. Suggestions? — jmk2142, Apr 30 '13 at 15:00

score 28 · Accepted Answer · answered Apr 26 '13 at 04:21

28

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

answered Apr 26 '13 at 04:21

Arun P Johny

384,651
66
527
531

1

Nice, what did you change besides returning `trail`? – Dagg Nabbit Apr 26 '13 at 04:25
1

That's exactly what should work. It just needs a sentinel flag to stop the original loop from running if the recursive function call found a match, and your code does that. – Joseph Myers Apr 26 '13 at 04:25
Ah, I see it now. Must be time to sleep ;) – Dagg Nabbit Apr 26 '13 at 04:25
Bravo. My head is spinning - need to eat and sleep. Thank you guys for your kind input. Will study this in depth tomorrow. :-) – jmk2142 Apr 26 '13 at 05:05

score 0 · Answer 2 · answered Jun 29 '16 at 17:50

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

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

}

was expecting a js recursive function – Nithin P.H Jan 18 '19 at 09:10 — Nithin P.H, Jan 18 '19 at 09:10

manikanta · Answer 3 · 2023-03-19T16:57:46.860

I improvised @arun-p-johny answer for my requirement without nested recursive function (which will be defined each time which could be inefficient when called several times) and without the external state.

In my case, I need to get the matching path like a file path.

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

This can be made even more generic by accepting children key & the key we want the returned value to be made of.

How do I break out of loops in recursive functions?

3 Answers3

Linked

Related