CODEWITHSUNDEEP
javascriptnode.js
liminal18
liminal18

Reputation: 563

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

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)

Upvotes: 1

Views: 209

Answers (3)

Timothy Lee
Timothy Lee

Reputation: 828

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.

Upvotes: 1

ibrahim mahrir
ibrahim mahrir

Reputation: 31692

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

Upvotes: 2

Mark
Mark

Reputation: 92440

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

Upvotes: 2

Related Questions