2

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!

8
  • 5
    why do you need recursion at all, can't you just reduce() it? Commented Jun 18, 2018 at 19:24
  • Possible duplicate: stackoverflow.com/questions/1230233/… Commented Jun 18, 2018 at 19:26
  • It doesn’t hurt to learn the roots Commented Jun 18, 2018 at 19:26
  • Of course, I can, but it's a task and I have to modify the code and make it work for big arrays Commented Jun 18, 2018 at 19:27
  • 3
    Don't use recursion for for this task (in javascript). You are overcomplicating this: const sum = arr => arr.reduce((a, b) => a + b, 0) Commented Jun 18, 2018 at 19:35

7 Answers 7

2

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)

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

Comments

1

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.

Comments

1

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

4 Comments

"ES6 supports tail recursion" not on any implementation I'm aware of. Babel pulled the feature over a year ago too.
Also, why setTimeout in the Promise constructor?
@user633183 It's OPs code. I just added the missing resolve. Since it is a requirement it will work on all ES6 compliant implementations. Safari/iOS supports tail recursion and is perhaps the most ES6 compliant. Now you are aware of one.
whoa, newfound respect for Safari ✊
1

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

Comments

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

1 Comment

Need some explanation of code what you wrote and how it will solve problem.
-1

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)

3 Comments

Even inside your function?
@AngelaHayrapetian Sure don't use prebuilts but you must be able to make your own helpers
@AliaksandrSushkevich Yes. I have to make it work asynchronously, that's why I've tried to do that with promises, but I'm doing something wrong
-1

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

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.