蹦床递归堆栈溢出 [英] Trampoline recursion stack overflow

问题描述

我有这个递归函数sum，它计算传递给它的所有数字的总和.

I have this recursive function sum which computes sum of all numbers that were passed to it.

function sum(num1, num2, ...nums) {
  if (nums.length === 0) { return num1 + num2; }
  return sum(num1 + num2, ...nums);
}

let xs = [];
for (let i = 0; i < 100; i++) { xs.push(i); }
console.log(sum(...xs));

xs = [];
for (let i = 0; i < 10000; i++) { xs.push(i); }
console.log(sum(...xs));

如果仅向其传递很少"的数字，它将正常工作，否则将溢出call stack.因此，我尝试对其进行一些修改并使用trampoline，以便它可以接受更多参数.

It works fine if only 'few' numbers are passed to it but overflows call stack otherwise. So I have tried to modify it a bit and use trampoline so that it can accept more arguments.

function _sum(num1, num2, ...nums) {
  if (nums.length === 0) { return num1 + num2; }
  return () => _sum(num1 + num2, ...nums);
}

const trampoline = fn => (...args) => {
  let res = fn(...args);
  while (typeof res === 'function') { res = res(); }
  return res;
}

const sum = trampoline(_sum);

let xs = [];
for (let i = 0; i < 10000; i++) { xs.push(i); }
console.log(sum(...xs));

xs = [];
for (let i = 0; i < 100000; i++) { xs.push(i); }
console.log(sum(...xs));

第一个版本不能处理10000个数字，而第二个版本可以处理10000个数字.但是，如果我将100000个数字传递给第二个版本，则会再次出现call stack overflow错误.

While the first version isn't able to handle 10000 numbers, the second is. But if I pass 100000 numbers to the second version I'm getting call stack overflow error again.

我要说的是100000确实不是那么大(这里可能是错误的)，并且看不到任何可能导致内存泄漏的失控闭包.

I would say that 100000 is not really that big of a number (might be wrong here) and don't see any runaway closures that might have caused the memory leak.

有人知道这是怎么回事吗?

Does anyone know what is wrong with it?

推荐答案

浏览器对函数可以采用的参数数量有实际限制

您可以更改sum签名以接受一个数组而不是可变数量的参数，并使用解构使语法/可读性保持与所拥有的相似.这可以修复" stackoverflow错误，但是速度很慢:D

You can change the sum signature to accept an array rather than a varying number of arguments, and use destructuring to keep the syntax/readability similar to what you have. This "fixes" the stackoverflow error, but is increadibly slow :D

function _sum([num1, num2, ...nums]) { /* ... */ }

即:如果您遇到了最大参数数的问题，那么递归/蹦床方法可能会太慢而无法使用...

I.e.:, if you're running in to problems with maximum argument counts, your recursive/trampoline approach is probably going to be too slow to work with...

这篇关于蹦床递归堆栈溢出的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！