Recursive functions in Javascript and depth tracking

Question

I am writing a recursive function in JS and am experiencing some problems. 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 like a static var sort, but the problem is that in C, which has its own static vars, when you return from a function, this variable will (supposedly) decrease, so this is true depth. If I have three boxes that contain three boxes, and each of them contains three boxes, etc., We essentially drill to the deepest until there are children, then we step back from the level to the brother and cross his children , The problem with the code above is that the depth continues to increase and increase indefinitely, although the depth of TRUTH can only be 3 or 4 from the oldest ancestor to the youngest child. If there are 80 brothers and sisters at each level, this depth counter will grow rapidly.

How do I track true depth in JS recursive functions?

Answer 1

Do not attach a counter to a function. The counter is used by all recursive calls, so the counter represents the number of function calls, not the depth of the recursion.

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

Answer 2

Another (and perhaps more enjoyable) solution would be to use the strengths of JS functional programming and use a high-order function to maintain the entire depth of housekeeping outside 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 to break the recursion when it goes deeper than the given value. Let the wrapper code:

 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 maximum depth = 20:

 fac = wrapDepth(fac, 20) 

and test:

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

Please note that we have not made any changes to the main function of fac , but, nevertheless, its depth of recursion is now under control.

Answer 3

Why don't you just change the function signature to take the thing and index? Therefore, you would call it this:

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

Answer 4

Just add:

 traverse.depth--; 

Right in front of any return statements. So

 if(x === 5) return thing; 

It would be:

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

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

Answer 5

If I understood correctly, it seems to me that you want to track the depth of the recursion. But in code, you never decrease depth as level 1 is completed in recursion.

I tried simple code, and I think this is 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