How to prevent an infinite recursion

I am trying to recursively print out the contents of jQuery. I'm planning on using this to analyze an existing instance of jQuery (loaded in a page) against a small database of known "jQuery signatures", to determine what changes have been made (i.e. what plugins have been loaded, functions modified, etc.).

To do this, I have this small function:

function recurse(obj, iter){
    var padding = (new Array(iter + 1)).join("  ") + ">";

    for (var i in obj){
    document.writeln(padding + i + "<br/>");

    if (iter < 5)
        recurse(obj[i], iter + 1);
    }
}

When I execute this:

recurse(jQuery, 1);

I get something like this:

  >p开发者_如何学Pythonrototype
    >init
      >prototype
        >init
          >prototype
        >selector
        >jquery
          >0

.... On and on and on .....

My problem is, at the very beginning, you can see that prototype and then init repeat over and over again. The only reason it stopped at 5 deep is because of the if (iter < 5) check. If the limit wasn't there, it would have recurred [sic?] forever. The iteration limit helps, but what if there is a critical function 6 deep? Essentially, I have no idea what I should make this iteration limit, or if there should be one at all.

Instead, I'm thinking there must be some kind of algorithm that can prevent never-ending recursion. Does such an algorithm exist? Or should I change how I go about traversing jQuery? Thanks,

You could keep track of what values you've already seen, and just bail out when you see one again.

function recurse(obj) {
  var marker = '__' + new Date().getTime() + '__';
  function r(obj, iter) {
    if (marker in obj) return;

    var padding = (new Array(iter + 1)).join("  ") + ">";
    obj[marker] = true;

    for (var i in obj) {
      if (!obj.hasOwnProperty(i) || i === marker) continue;

      document.writeln(padding + i + "<br/>");

      recurse(obj[i], iter + 1);
    }
  }
  r(obj, 0);      
}

Now this of course has the disadvantage of leaving your traversed object graph littered with extra properties, but for some applications that wouldn't be a problem. Also using the clock to make a "unique" marker is really lame; you might want to just use a counter, or maybe just a fixed nonsense string.

edit — Also, another issue (present in the original code too) is that this really should be checking to see if the "obj" values are really objects. If they're scalars, then there's no point doing anything, really. You'd just need to do a "typeof" check right after checking for the marker, and if you see null, a number, a string, or a boolean, just return.

Your recursion is missing a base case. See the definition of Recursion. You introduced an arbitrary base case of (depth < 5). Maybe instead use the length of the array, or as Pointy pointed out, the hasOwnProperty check to skip the recursive call.

Unless i am missing something, all you need to do is to skip strings (if you use a modern browser that allows indexing of strings, otherwise it doesn't matter) and the init function which is the jQuery self reference that gives you the infinite recursion

function recurse(obj, iter){
    var padding = (new Array(iter + 1)).join("  ") + ">";

    for (var i in obj){
        document.writeln(padding + i + "<br/>");
        if (i != 'init' && typeof obj[i] != 'string') 
            recurse(obj[i], iter + 1);
    }
}

As several answers said: You algorithm must contain a proper break case to prevent infinite recursion.

But what happen if you cannot control the input of your algorithm?

For that case, or just for development purposes, you could use this:

function acmeRecursion(){
  var count = localStorage.getItem("count");
  if(count>50){
    throw new Error("recursion limit exceeded");
  }
  count++;

  //put your logic here
}

Building off of Pointy's answer (ideally this would be a comment, but alas, code doesn't work great in those), a better solution might be to just pass along an object to the the recurse function that will keep track of objects you've already seen. Something like this:

var recurse = function(obj)
{
    var seen = {};
    var inner = function(obj, padding)
    {
        for (var i in obj)
        {
            if (!(obj[i] in seen))
            {
                document.writeln(padding + i + '<br />');
                seen[obj[i]] = true;
                inner(obj[i], padding + '  ');
            }
        }
    };
    return inner(obj, '');
};

Which uses a closure rather than an argument to pass along the seen object, for the sake of simplicity, but the basic concept is the same.

This approach has the advantage of not adding extra attributes to the objects you're traversing.

Edit: I meant to explain this, but forgot. I'm not using hasOwnProperty here because in the case of printing an object graph, you probably do want to see inherited attributes.