Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Recursive functions in Javascript and depth-tracking

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?

like image 337
CaptSaltyJack Avatar asked Feb 21 '12 21:02

CaptSaltyJack


People also ask

How do you keep track of value in recursion?

For keeping the indices, the logic I have is to push current index of str to a "local indices array" within a recursive call when the pattern character matches the string character, and once the pattern is finished, push the "local indices" to the "global indices" and reset the "local indices" for the next recursion ...

What is recursion in depth?

Abstract. The maximum depth of recursion refers to the number of levels of activation of a procedure which exist during the deepest call of the procedure.

How recursive function works in JavaScript?

Recursion is when a function calls itself until someone stops it. If no one stops it then it'll recurse (call itself) forever. Recursive functions let you perform a unit of work multiple times. This is exactly what for/while loops let us accomplish!

How deep can a recursive function go?

The maximum recursion depth in C depends on a lot of factors, of course. On a typical 64-bit Linux system the default stack size is 8 MB, and the stack alignment is 16 bytes, so you get a recursion depth of about 512K for simple functions.


1 Answers

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);
}
like image 106
Rob W Avatar answered Sep 27 '22 20:09

Rob W