Recursive functions in Javascript and depth-tracking

Question

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?

How about decrementing the traverse.depth after the last if condition? — Selvakumar Arumugam
– 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
– Matt Ball, Commented Feb 21, 2012 at 21:42
I'm sorry for voting to close as a duplicate - the one I linked to doesn't seem to work for recursion. — pimvdb
– pimvdb, Commented Feb 21, 2012 at 21:45

Rob W · Accepted Answer · 2012-02-21 22:29:12Z

20

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);
}

edited Feb 21, 2012 at 22:29

answered Feb 21, 2012 at 21:41

Rob W

350k87 gold badges811 silver badges683 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

jondavidjohn Over a year ago

there is no object being passed by reference here, he's attaching a property to the function object itself...

CaptSaltyJack Over a year ago

There are other solution but this appears to be the most concise and elegant. Thanks.

Rob W Over a year ago

@jondavidjohn You're correct (I read thing.depth). The explanation of the solution still stands, though.

jondavidjohn Over a year ago

@RobW no doubt, was just wanting to make sure we weren't confusing people as to why it works (and didn't work in the first place).

georg · Accepted Answer · 2012-02-21 22:21:29Z

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.

Mike Corcoran · Accepted Answer · 2013-05-31 14:06:08Z

4

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)

edited May 31, 2013 at 14:06

answered Feb 21, 2012 at 21:41

Mike Corcoran

14.6k4 gold badges42 silver badges51 bronze badges

Comments

Paul · Accepted Answer · 2012-02-21 21:42:31Z

1

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.

answered Feb 21, 2012 at 21:42

Paul

142k28 gold badges285 silver badges272 bronze badges

Comments

Selvakumar Arumugam · Accepted Answer · 2012-02-21 21:51:44Z

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

Collectives™ on Stack Overflow

Recursive functions in Javascript and depth-tracking

5 Answers 5

4 Comments

Comments

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

4 Comments

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related