代码之家 › 专栏 › 技术社区 › Matus Dubrava

蹦床递归堆栈溢出

ecmascript-6 recursion javascript

Matus Dubrava · 技术社区 · 6 年前

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

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 这样它就可以接受更多的论点。

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个数字,但第二个版本是。但是如果我把100000个数字传给第二个版本,我会得到 call stack overflow 再次出错。

我会说100000并不是一个很大的数字(这里可能是错误的),并且没有看到任何可能导致内存泄漏的失控的闭包。

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

3 回复 | 直到 6 年前

user3297291 6 年前

Browsers have practical limits on the number of arguments a function can take

你可以改变 sum 签名接受一个数组而不是不同数量的参数,并使用析构函数使语法/可读性与您拥有的相似。这“修复”了stackoverflow错误,但速度慢得令人难以置信:d

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

例如:如果遇到最大参数计数的问题,那么递归/蹦床方法可能太慢,无法使用…

Mulan 6 年前

另一个答案指出了函数参数数量的限制,但我想说明一下您的蹦床实现。我们正在进行的长期计算可以想要返回一个函数。如果你使用 typeof res === 'function' ,无法再将函数计算为返回值!

相反,用某种独特的标识符对蹦床变体进行编码。

const bounce = (f, ...args) =>
  ({ tag: bounce, f: f, args: args })

const done = (value) =>
  ({ tag: done, value: value })

const trampoline = t =>
{ while (t && t.tag === bounce)
    t = t.f (...t.args)
  if (t && t.tag === done)
    return t.value
  else
    throw Error (`unsupported trampoline type: ${t.tag}`)
}

在我们开始之前,让我们先获取一个要修复的示例函数

const none =
  Symbol ()

const badsum = ([ n1, n2 = none, ...rest ]) =>
  n2 === none
    ? n1
    : badsum ([ n1 + n2, ...rest ])

我们会扔一个 range 在它的数字看它工作

const range = n =>
  Array.from
    ( Array (n + 1)
    , (_, n) => n
    )

console.log (range (10))
// [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]

console.log (badsum (range (10)))
// 55

但它能应付大联盟吗?

console.log (badsum (range (1000)))
// 500500

console.log (badsum (range (20000)))
// RangeError: Maximum call stack size exceeded

到目前为止在浏览器中查看结果

const none =
  Symbol ()

const badsum = ([ n1, n2 = none, ...rest ]) =>
  n2 === none
    ? n1
    : badsum ([ n1 + n2, ...rest ])

const range = n =>
  Array.from
    ( Array (n + 1)
    , (_, n) => n
    )

console.log (range (10))
// [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]

console.log (badsum (range (1000)))
// 500500

console.log (badsum (range (20000)))
// RangeError: Maximum call stack size exceeded

介于 10000 和 20000 我们的 badsum 函数意外地导致堆栈溢出。

除了将函数重命名为 goodsum 我们只需要使用蹦床的变体对返回类型进行编码。

const goodsum = ([ n1, n2 = none, ...rest ]) =>
  n2 === none
    ? n1
    ? done (n1)
    : goodsum ([ n1 + n2, ...rest ])
    : bounce (goodsum, [ n1 + n2, ...rest ])

console.log (trampoline (goodsum (range (1000))))
// 500500

console.log (trampoline (goodsum (range (20000))))
// 200010000
// No more stack overflow!

您可以在浏览器中查看此程序的结果。现在我们可以看到递归和蹦床都不是这个程序慢的错误。不过别担心,我们稍后会解决的。

const bounce = (f, ...args) =>
  ({ tag: bounce, f: f, args: args })
  
const done = (value) =>
  ({ tag: done, value: value })
  
const trampoline = t =>
{ while (t && t.tag === bounce)
    t = t.f (...t.args)
  if (t && t.tag === done)
    return t.value
  else
    throw Error (`unsupported trampoline type: ${t.tag}`)
}

const none =
  Symbol ()

const range = n =>
  Array.from
    ( Array (n + 1)
    , (_, n) => n
    )

const goodsum = ([ n1, n2 = none, ...rest ]) =>
  n2 === none
    ? done (n1)
    : bounce (goodsum, [ n1 + n2, ...rest ])

console.log (trampoline (goodsum (range (1000))))
// 500500

console.log (trampoline (goodsum (range (20000))))
// 200010000
// No more stack overflow!

额外的呼叫 trampoline 当你看着 古德萨姆 单独一个人,不太明显什么 done 和 bounce 在那里,除非这在你的许多程序中是一个很常见的约定。

我们可以用泛型更好地编码循环意图 loop 功能。循环被赋予一个函数,该函数在函数调用时被调用。 recur . 它看起来像一个递归调用,但实际上 复发 正在构造一个值 环 以安全的方式处理。

我们赋予的功能 环 可以有任意数量的参数,并且具有默认值。这也很方便,因为我们现在可以避免 ... 简单使用索引参数进行破坏和扩展 i 初始化为 0 . 函数的调用方不能在循环调用之外访问这些变量

这里的最后一个优点是 古德萨姆 可以清楚地看到循环编码和显式 完成 不再需要标记。函数的用户不需要担心调用 蹦床 不管是因为我们已经在 环

const goodsum = (ns = []) =>
  loop ((sum = 0, i = 0) =>
    i >= ns.length
      ? sum
      : recur (sum + ns[i], i + 1))

console.log (goodsum (range (1000)))
// 500500

console.log (goodsum (range (20000)))
// 200010000

console.log (goodsum (range (999999)))
// 499999500000

这是我们的 环 和 复发 现在配对。这一次我们扩展了 { tag: ... } 使用标记模块的约定

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

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

const T =
  Symbol ()

const tag = (t, x) =>
  Object.assign (x, { [T]: t })

const is = (t, x) =>
  t && x[T] === t

在浏览器中运行它以验证结果

const T =
  Symbol ()

const tag = (t, x) =>
  Object.assign (x, { [T]: t })

const is = (t, x) =>
  t && x[T] === t

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

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

const range = n =>
  Array.from
    ( Array (n + 1)
    , (_, n) => n
    )

const goodsum = (ns = []) =>
  loop ((sum = 0, i = 0) =>
    i >= ns.length
      ? sum
      : recur (sum + ns[i], i + 1))

console.log (goodsum (range (1000)))
// 500500

console.log (goodsum (range (20000)))
// 200010000

console.log (goodsum (range (999999)))
// 499999500000

额外的

我的大脑在变形装置中停留了几个月,我很好奇能否实现一个安全的堆栈。 unfold 使用 环 上面介绍的函数

下面,我们看一个示例程序,它生成了一系列 n . 把它看作是展示工作来得到 古德萨姆 以上程序。总计达 n 是数组中的最后一个元素。

这是一个很好的使用案例 展开 . 我们能够写这个用 环 直接,但这一点是为了扩大 展开 所以这里是

const sumseq = (n = 0) =>
  unfold
    ( (loop, done, [ m, sum ]) =>
        m > n
          ? done ()
          : loop (sum, [ m + 1, sum + m ])
    , [ 1, 0 ]
    )

console.log (sumseq (10))
// [ 0,   1,   3,   6,   10,  15,  21,  28,  36, 45 ]
//   +1 â +2 â +3 â +4 â +5 â +6 â +7 â +8 â +9 â  ...

如果我们使用不安全的 展开 实现,我们可以将堆栈

// direct recursion, stack-unsafe!
const unfold = (f, initState) =>
  f ( (x, nextState) => [ x, ...unfold (f, nextState) ]
    , () => []
    , initState
    )

console.log (sumseq (20000))
// RangeError: Maximum call stack size exceeded

玩了一会儿之后,确实可以进行编码 展开 使用我们的堆栈安全 环 . 清理 … 使用扩展语法 push 效果也让事情变得更快。

const push = (xs, x) =>
  (xs .push (x), xs)

const unfold = (f, init) =>
  loop ((acc = [], state = init) =>
    f ( (x, nextState) => recur (push (acc, x), nextState)
      , () => acc
      , state
      ))

有烟囱保险箱 展开 我们的 sumseq 功能现在起作用

console.time ('sumseq')
const result = sumseq (20000)
console.timeEnd ('sumseq')

console.log (result)
// sumseq: 23 ms
// [ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ..., 199990000 ]

在下面的浏览器中验证结果

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

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

const T =
  Symbol ()

const tag = (t, x) =>
  Object.assign (x, { [T]: t })

const is = (t, x) =>
  t && x[T] === t

const push = (xs, x) =>
  (xs .push (x), xs)

const unfold = (f, init) =>
  loop ((acc = [], state = init) =>
    f ( (x, nextState) => recur (push (acc, x), nextState)
      , () => acc
      , state
      ))

const sumseq = (n = 0) =>
  unfold
    ( (loop, done, [ m, sum ]) =>
        m > n
          ? done ()
          : loop (sum, [ m + 1, sum + m ])
    , [ 1, 0 ]
    )

console.time ('sumseq')
const result = sumseq (20000)
console.timeEnd ('sumseq')

console.log (result)
// sumseq: 23 ms
// [ 0, 1, 3, 6, 10, 15, 21, 28, 36, 45, ..., 199990000 ]

user6445533 6 年前

另一个答案已经用您的代码解释了这个问题。这个答案表明蹦床对于大多数基于数组的计算来说足够快,并且提供了更高的抽象级别:

// trampoline

const loop = f => {
  let acc = f();

  while (acc && acc.type === recur)
    acc = f(...acc.args);

  return acc;
};


const recur = (...args) =>
  ({type: recur, args});


// sum

const sum = xs => {
  const len = xs.length;

  return loop(
    (acc = 0, i = 0) =>
      i === len
        ? acc
        : recur(acc + xs[i], i + 1));
};


// and run...

const xs = Array(1e5)
  .fill(0)
  .map((x, i) => i);


console.log(sum(xs));

如果基于蹦床的计算导致性能问题,那么您仍然可以用一个裸循环替换它。