I'm writing a recursive function in JS and having some trouble. Let's start with this very basic function:

function traverse(thing)
{
    if (typeof traverse.depth == 'undefined')
        traverse.depth = 1;
    else
        traverse.depth ++;

    if (thing.child)
        traverse(thing.child);
}

So this works fine, and depth acts as a static var of sorts, but the problem is that in a language like C that has proper static vars, as you back out of the function, this variable would (ostensibly) decrease, so it is a true depth. If I have three boxes that contain three boxes and each of those contain three boxes, etc., we're essentially drilling down into the deepest one till there are no children, then backing out up a level to a sibling, and traversing its children. The problem with the above code is that the depth keeps increasing and increasing infinitely, even though the TRUTH depth may only be 3 or 4 from the oldest ancestor to the youngest child. If there are 80 siblings on each level, that depth counter is going to skyrocket.

How do I keep track of true depth in JS recursive functions?

I'm writing a recursive function in JS and having some trouble. Let's start with this very basic function:

function traverse(thing)
{
    if (typeof traverse.depth == 'undefined')
        traverse.depth = 1;
    else
        traverse.depth ++;

    if (thing.child)
        traverse(thing.child);
}

So this works fine, and depth acts as a static var of sorts, but the problem is that in a language like C that has proper static vars, as you back out of the function, this variable would (ostensibly) decrease, so it is a true depth. If I have three boxes that contain three boxes and each of those contain three boxes, etc., we're essentially drilling down into the deepest one till there are no children, then backing out up a level to a sibling, and traversing its children. The problem with the above code is that the depth keeps increasing and increasing infinitely, even though the TRUTH depth may only be 3 or 4 from the oldest ancestor to the youngest child. If there are 80 siblings on each level, that depth counter is going to skyrocket.

How do I keep track of true depth in JS recursive functions?

• javascript
• recursion

• 1 How about decrementing the traverse.depth after the last if condition? – Selvakumar Arumugam Commented Feb 21, 2012 at 21:40
• To start, you have not shown any code which decrements the value of traverse.depth... – Matt Ball Commented Feb 21, 2012 at 21:42
• 1 I'm sorry for voting to close as a duplicate - the one I linked to doesn't seem to work for recursion. – pimvdb Commented Feb 21, 2012 at 21:45

5 Answers 5

Don't attach the counter to the function. The counter is shared by all recursive calls, so the counter represents the number of function calls, instead of the recursion depth.

When depth is passed as a separate variable, the counter shows the true depth.

function traverse(thing, depth)
{
    if (typeof depth == 'number')
        depth++;
    else
        depth = 1;

    if (thing.child)
        traverse(thing, depth);
}

Another (and perhaps nicer) solution would be to utilize JS functional programming strengths and use a high-order function to keep all depth-related housekeeping outside of the main function. Consider, for example, the following classic example:

function fac(n) {
    if(n < 3)
        return n;
    return n * fac(n - 1);
}

We want this one to break the recursion once its goes deeper than a given value. Let's code a wrapper:

function wrapDepth(fn, max) {
    var depth = 0
    return function() {
        if (++depth > max) 
            throw "Too much recursion"
        var out = fn.apply(null, [].slice.call(arguments, 0))
        depth--;
        return out;
    }
}

Create a wrapper with max depth = 20:

fac = wrapDepth(fac, 20)

and test:

 console.log(fac(10)) // 3628800
 console.log(fac(100)) // Too much recursion

Note that we didn't make any change in the main function fac itself, but still, its recursion depth is now under control.

why don't you just modify the function signature to take a thing and an index? So you would call it like:

function traverse(thing, idx)
    ...
    if (condition)
        traverse(thing.child, ++idx)

Just add:

traverse.depth--;

Right before any return statements. So

if(x === 5)
    return thing;

Would become:

if(x === 5){
    traverse.depth--;
    return thing;
}

And then add traverse.depth--; before your closing } of the function.

If I understood correctly, it looks to me like you want to track the depth of recursion.. but in your code you never decrement the depth as you finish 1 level in the recursion.

I tried out a simple code and I think this what you wanted,

DEMO

HTML:

<div id="result"></div>

JS:

var result = document.getElementById('result');

var tmpArray = [1,2,3,4,5,6,7,8];

function depthTest() {
    if (typeof depthTest.depth == 'undefined')
        depthTest.depth = 0;
    else
        depthTest.depth++;

    result.innerHTML += depthTest.depth;

    if (typeof tmpArray[depthTest.depth] != 'undefined')
        depthTest();

    result.innerHTML += depthTest.depth;
    depthTest.depth--;
}

depthTest(tmpArray);

OUTPUT:

012345678876543210