时间戳

首页 > 解决方案 > 蹦床递归堆栈溢出

javascript - 蹦床递归堆栈溢出

问题描述

我有这个递归函数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 并不是一个很大的数字（这里可能是错误的）并且看不到任何可能导致内存泄漏的失控闭包。

有谁知道它有什么问题？

标签： javascriptrecursionecmascript-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会让人讨厌，当您goodsum单独查看时，并不能立即看出那里正在做什么done和bounce正在做什么，除非这可能是您的许多程序中非常常见的约定。

loop我们可以使用通用函数更好地编码我们的循环意图。循环被赋予一个函数，每当该函数调用时，该函数就会被调用recur。它看起来像一个递归调用，但实际上recur是在构造一个loop以堆栈安全方式处理的值。

我们赋予的函数loop可以有任意数量的参数，并且具有默认值。这也很方便，因为我们现在可以通过简单地使用初始化为...的索引参数来避免昂贵的解构和传播。函数的调用者无法在循环调用之外访问这些变量i0

这里的最后一个好处是，阅读器goodsum可以清楚地看到循环编码，并且done不再需要显式标记。该函数的用户不需要担心调用trampoline，因为它已经为我们处理好了loop

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

这是我们现在loop的recur配对。这次我们{ 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使用loop上面介绍的功能实现堆栈安全

下面，我们看一个示例程序，该程序生成整个序列的总和n。可以将其视为显示为上述程序得出答案的工作goodsum。总和n是数组中的最后一个元素。

这是一个很好的用例unfold。我们可以直接使用loop，但这样做的目的是为了扩展unfold

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 ↗  ...

如果我们使用不安全的unfold实现，我们可能会破坏堆栈

// 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

玩了一会儿之后，确实可以unfold使用我们的 stack-safe进行编码loop。...使用效果清理传播语法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
      ))

有了 stack-safe unfold，我们的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 ]

推荐阅读