非常大的递归JavaScript

Question

我有这段代码，它用递归计算数组元素的总和，但是当数组太大时，它会抛出">超出最大调用堆栈大小"错误。

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

所以我需要以某种方式更改它以在所有情况下正常工作，我认为我可以让它与 Promise 异步工作，但它总是返回待处理的承诺。

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

我该如何解决它？

任何帮助将不胜感激！

Answer 1

你只是在解决 i arr.length 的情况，所以所有链式的承诺永远悬而未决。退货不会自动为我们解决该问题，因此需要明确说明：

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

对于使用本机任务的问题，有一些解决方案。 这个是使用 Promise 来安排微任务：

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

但这将迫使引擎等到执行完成。因此，对于大型数组，我不建议您在主线程上执行此操作。

您还可以执行以下操作：

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

然后，通过对此代码进行一些更改并使其更加优雅，我们可以执行以下操作：

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

如果您的环境支持尾递归，您可以将其更改为使用它：http://2ality.com/2015/06/tail-call-optimization.html

更新

实际上，还有另一种方法可以做到这一点。 RXJS 库提供了一个队列调度程序，它可以帮助您使递归逻辑成为迭代逻辑，而无需在代码中进行许多更改。我在这里创建了一个sum方法的示例。

Answer 3

我不知道你为什么要使用承诺并使函数异步。但是，如果您这样做，则需要解决这两种情况：

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

现在这也返回了一个承诺。一旦你异步了，你就再也回不去了。你需要使用返回的承诺来获取返回值：

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

最好不要让它异步。ES6 支持尾递归，所以你可以这样做：

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

由于顺序无关紧要，我冒昧地对值进行了反向求和。 现在信不信由你，但helper已经作为抽象存在于语言中，它为您提供每个元素的值和每次迭代中的acc。因此，您可以改为这样做：

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

Answer 4

setTimeout

不是堆栈溢出问题的解决方案。管理堆栈是排序函数调用的问题。您可以通过多种方式执行此操作，最直观的是loop/recur蹦床。

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

我在这里介绍了这个问题的许多其他技术。

堆栈安全递归是我写了很多的东西，关于这个主题有近 30 个答案

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

您需要使用迭代过程而不是递归过程。因此，您无需累积调用，而是计算每次迭代调用的总和。这可以通过使用辅助函数来实现，该函数将获得(sum, array, currentValue)

Answer 7

如果出于某种原因您需要使用递归并且不介意花费很长时间，您可以使用超时; 但是我绝对不建议使用它。我主要是发布它，因为它是可能的。

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