Very big recursion javascript

Question

I have this code, which is counting array elements sum with recursion, but when the array is too big it throwing Maximum call stack size exceeded error.

var a = new Array(10 ** 7);
a.fill(0);

function sum(arr, i = 0) {
  if(i === arr.length) {
      return 0;
  }

  return arr[i] + sum(arr, i + 1);
}

sum(a);

So I need to change it somehow to work normally for all cases and I thought I can make it work asynchronously with Promises, but it always returning Promise pending.

var a = new Array(10 ** 7);
a.fill(0);

var sum = (arr, i = 0) => new Promise((resolve) => {
  setTimeout(() => {
    if(i === arr.length) {
      return resolve(0);
    }

    return  sum(arr, i + 1).then(el => el + arr[i]);
  }, 0);
});

sum(a);

How can I fix it?

Any help would be appreciated!

Answer 1

You are only resolving the case where i is arr.length, so all the chained promises remain pending forever. Return won´t automatically resolve it for us, so need to be explicit:

var a = new Array(10);
a.fill(0);
a[0] = 3;
var sum = (arr, i = 0) => new Promise((resolve) => {
  setTimeout(() => {
    if(i === arr.length) {
      resolve(0);
    } else {
      resolve(sum(arr, i + 1).then(el => el + arr[i]));
    }
  }, 0);
});

sum(a).then(console.log)

Answer 2

I have no idea why you would want to use promises and make the function async. But if you do you need to resolve both cases:

const sum = (arr, i = 0) => new Promise((resolve) => {
  setTimeout(() => {
    if(i === arr.length) {
      return resolve(0);
    }

    return  sum(arr, i + 1).then(el => resolve(el + arr[i]));
  }, 0);
});

Now this also returns a promise. Once you've gone async you can never go back. You need to use the returned promise to get the return value:

sum([1, 2, 3, 4]).then(return => console.log(return));

Its better to not make it async. ES6 supports tail recursion so you can just make it like this:

function sum(arr) {
    function helper(acc, i) {
        if (i<0) {
            return acc;
        }
        return helper(arr[i]+acc, i-1);
    }

    return helper(0, arr.length - 1);
}

Since the order doesn't matter I took the liberty to sum the values in reverse. Now believe it or not, but that helper already exists in the language as an abstraction that gives you the value of each element and the acc in each iteration. Thus you can do this instead:

function sum(arr) {
    return arr.reduce((acc, val) => acc + val, 0)
}

Answer 3

setTimeout is not a solution for the stack overflow problem. Managing your stack is a matter of sequencing your function calls. You can do this in a variety of ways, the most intuitive being the loop/recur trampoline.

const loop = f =>
{ let acc = f ()
  while (acc && acc.tag === recur)
    acc = f (...acc.values)
  return acc
}

const recur = (...values) =>
  ({ tag: recur, values })

const sum = (xs = []) =>
  loop ((result = 0, i = 0) =>         // initial state
    i >= xs.length                     // exit condition
      ? result                         // return value
      : recur (result + xs[i], i + 1)) // next state
      
const tenMillionNumbers =
  Array.from (Array (1e7), (_,n) => n)
  
console.time ('recursion is not slow')
console.log (sum (tenMillionNumbers))
console.timeEnd ('recursion is not slow')

// => 49999995000000
// recursion is not slow: 2171ms

I cover many other techniques for this problem here.

Stack-safe recursion is something I write about a lot, with almost 30 answers on the topic

Answer 4

There are some solutions for your issue with using native tasks. this one is using Promise to schedule a microtask:

(function() {
  function sum(arr, i = 0) {
    if(arr.length === i) {
        return Promise.resolve(0);
    }

    return Promise.resolve(null)
      .then(() => sum(arr, i + 1))
      .then((x) => x + arr[i]);
  }

  sum(a).then(s => console.log(s));
}());

but this will force the engine to wait until the execution is completed. So for huge arrays, I wouldn't recommend you doing this on the main thread.

You can also do the following:

(function() {
  function sum(arr, i = 0) {
    if(arr.length === i) {
        return Promise.resolve(0);
    }

    return new Promise(resolve => {
      setTimeout(() => {
        sum(arr, i + 1).then(x => resolve(x + arr[i]));
      });
    });
  }

  sum(a).then(s => console.log(s));
}());

then with make a few changes to this code and making it more elegant, we can do the following:

(function() {
  const defer = () => new Promise((resolve) => setTimeout(resolve));

  async function sum(arr, i = 0) {
    if(arr.length === i) {
        return 0
    }

    await defer();
    return await sum(arr, i + 1) + arr[i];
  }

  sum(a).then(s => console.log(s));
}());

and if your environment supports tail recursion you can change this to use it: http://2ality.com/2015/06/tail-call-optimization.html

UPDATE

actually, there is one more way to do this. rxjs library provides a queue scheduler which can help you make a recursive logic to be iterative without making many changes in your code. I've created an example of your sum method here.

Answer 5

var a = new Array(1000);
a.fill(1);
function sum(arr, i = 0, res = 0, resolve) {
  if(!i) return new Promise((resolve) => sum(arr, i + 1, res + arr[i], resolve), 0); 
  if(i === arr.length) return resolve(res);
  setTimeout(function(){
    sum(arr, i + 1, res + arr[i], resolve);
  }, 0); 
}
sum(a).then(console.log);

Answer 6

You need to use an iterative process instead of recursive one. So instead of accumulating calls, you'd compute your sum on each iteration call. This can be achieved by using a helper function which will get (sum, array, currentValue)

Answer 7

If for whatever reason you need to use recursion and don't mind this taking a long, you could use a timeout; however I would absolutely not recommend using this. I'm mostly posting it because it's possible.

var arr = new Array(10 ** 7);
    arr.fill(0);

var len = arr.length,
    idx = 0,
    sum = 0,
    sumFn = () => {
      setTimeout(() => {
        sum += arr[idx];
        idx++;

        if (idx < len) {
            sumFn();
        } else {
            //complete
        }
      }, 1);
    }

sumFn();