Why does this tail recursive loop cause stack overflow in javascript / node?

Question

exports.tailLoop = function(A) {
    const asc = A.sort((a,b) => a - b)
    function tailRecur (rest) {
        if (!rest.length) return 0
        const pair = rest.splice(0,2)
        if (pair[0] != pair[1]){
            return pair[0]
        } else {
            return tailRecur(rest)
        }   
    }   
    return tailRecur(asc)
}

I have also tried this with:

first = rest.shift()
next = rest.shift()

instead of the splice method.

When I input an array with 1 million elements it fails. Am I not understanding tail recursion correctly or does tail recursion not work on sizes of 1 million (note sort works fine on a 1 million sized array)

Only a few environments have implemented proper tail calls. Node.js is not one of them yet. — CertainPerformance
– CertainPerformance, Commented Jan 2, 2019 at 1:03
ok that is an answer any advice on how to deal with large inputs in node? I am running node 10 BTW. — liminal18
– liminal18, Commented Jan 2, 2019 at 1:04
I think the only real way is to find a non-recursive way, if the recursive way requires tons of calls. — CertainPerformance
– CertainPerformance, Commented Jan 2, 2019 at 1:06

Mark · Accepted Answer · 2019-01-02 01:24:43Z

2

To answer the comment question: how to deal with large inputs in node — You can always find ways to turn a recursive function into a non-recursive function. Sometimes it's not as elegant, but in this case, you are basically using recursion for a loop, which would be faster and easier to understand as a simple loop.

Something like:

function nonRec(A){
    const asc = A.sort((a,b) => a - b)
    while (asc.length){
        const pair = asc.splice(0,2)
        if (pair[0] != pair[1])
            return pair[0]
    }
    return 0
}

a = [1, 2, 3, 2, 4, 2, 2, 1, 3]
console.log(nonRec(a))

answered Jan 2, 2019 at 1:24

Mark

92.6k8 gold badges116 silver badges156 bronze badges

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

5 Comments

liminal18 Over a year ago

unfortunately when you get a million this simple does not return with in 7 minutes at least. tried this.

Mark Over a year ago

Yes @liminal18 , I was trying to keep the code the same as yours for the most part to illustrate the point. The most obvious optimization is to avoid the splice() and keep track of where you are in the array with an index variable. It will be much faster because you won't be recreating the giant array on every loop.

ibrahim mahrir Over a year ago

@liminal18 "unfortunately when you get a million this simple does not return with in 7 minutes". Well, the while loop will certainly be faster than any recursive function (tail recursion or not).

Mark Over a year ago

@liminal18 Also, I just ran a for loop version of this with 50 milion random integers. The sort is by far the biggest bottleneck. The actual iteration took around 300ms. Not sure what you can do about that.

liminal18 Over a year ago

@ibrahimmahrir weird I was finding the tail recursive method was faster than a while loop when the array has 50,001 elements.

ibrahim mahrir · Accepted Answer · 2019-01-02 01:44:25Z

2

@Mark has already answered the question, so this is merely a refactor of OP's code.

Your code is basically just checking for the two successive items that are equal by looping the array two items a time, this can be drastically optimized by using a for loop to get rid of the expensive calls to splice:

exports.tailLoop = function(A) {
    const asc = A.sort((a,b) => a - b);

    for(let i = 0; i < asc.length; i += 2) {
        if(asc[i] != asc[i + 1]) {
            return asc[i];
        }
    }

    return 0;
}

answered Jan 2, 2019 at 1:44

ibrahim mahrir

31.8k5 gold badges50 silver badges78 bronze badges

3 Comments

Mark Over a year ago

Yes, this is what I just tried. The sort is by far the biggest bottleneck.

ibrahim mahrir Over a year ago

@MarkMeyer Yeah, especially with OP's "array with 1 million elements". Removing the splices might not be a big optimization against sort but at least it will help speed things up a little bit, especially with the worst cases where the results are near the end of the array. I'm also begining to think that the sort might be avoided as I'm getting a vibe that OP is trying to look for duplicates, but I'm not quiet sure

liminal18 Over a year ago

ok this is cool because it increments by 2 so thanks. kind of weird for me to come from a functionalist background and find out tail call optimization is not in the language yet.

Timothy Lee · Accepted Answer · 2019-01-02 01:44:34Z

1

You could try increasing NodeJS maximum call stack, not sure whether this will help in this case.

Another way to skip from the maximum call stack is to change your code from synchronous to asynchronous.

tailLoop = function(A) {
  let resolver;
  const promise = new Promise((res,_rej)=>{
    resolver = res
  })
  const asc = A.sort((a,b) => a - b)
  function tailRecur (rest) {
    if (!rest.length) return 0
    const pair = rest.splice(0,2)
    if (pair[0] != pair[1]){
      resolver(pair[0])
    } else {
      setImmediate(()=>{
        tailRecur(rest)
      })
    }   
  }
  tailRecur(asc)
  return promise
}

now it won't exceed maximum call stack.

const a = []
for(let i=0;i<10000;i++){
  for(let j=0;j<100;j++){
    a.push(0)
  }
}
a.push(1)

tailLoop(a).then(result=>{
  console.log(result) //1
})

By the way, the code above takes minutes to get the result...

I think you could find a better method/algorithm to solve this problem.

answered Jan 2, 2019 at 1:44

Timothy Lee

8281 gold badge5 silver badges15 bronze badges

2 Comments

liminal18 Over a year ago

the while loop is pretty fast less than 20 seconds for a million yeah all those abstractions have a cost I tried using destructuring instead of shift or splice and man that leads to pretty fast stackoverflow. I do like this idea though.

Timothy Lee Over a year ago

In my case, using the worst-case input, both took about 4 minutes, but the while loop solution was faster 20 seconds.

Collectives™ on Stack Overflow

Why does this tail recursive loop cause stack overflow in javascript / node?

3 Answers 3

5 Comments

3 Comments

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

5 Comments

3 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related