javascript - 使用蹦床编写ackermann函数

我的ackermann函数代码导致RangeError：超出了最大调用堆栈大小。据我了解，我们可以使用蹦床功能来避免此错误，但是由于我是javascript新手，所以有人可以帮助我知道如何使用蹦床。

ackermannCalc(m, n) {
   if (m === 0) {
     return n + 1;
   } else if (m > 0 && n === 0) {
       return this.ackermannCalc(m - 1, 1);
   } else if (m > 0 && n > 0) {
       return this.ackermannCalc(m - 1, this.ackermannCalc(m, n - 1));
   }
}

最佳答案

不能将阿克曼放在蹦床上是不正确的。所有纯函数都可以设置为尾递归，因此可以始终使用蹦床技术。

仅仅因为ackermann调用了两次本身并不妨碍我们正确地对调用进行排序。实现此目的的一种技术是使用延续传递样式-

const identity = x =>
  x

const ack = (m, n, k = identity) => {
  if (m === 0)
    return k(n + 1)             // tail
  else if (m > 0 && n === 0)
    return ack(m - 1, 1, k)     // tail
  else
    return ack(m, n - 1, r => { // tail
      return ack(m - 1, r, k)   // tail
    })
}

console.log(ack(3,2))
// 29

console.log(ack(3,4))
// RangeError: Maximum call stack size exceeded

然后，您可以将其放在蹦床上-

const call = (f, ...values) =>
  ({ call, next: () => f (...values) })

const run = r =>
{ while (r && r.call === call)
    r = r.next()
  return r
}

const identity = x =>
  x

const ack = (m, n, k = identity) => {
  if (m === 0)
    return call(k, n + 1)
  else if (m > 0 && n === 0)
    return call(ack, m - 1, 1, k)
  else
    return call(ack, m, n - 1, r => {
      return call(ack, m - 1, r, k)
    })
}

console.log(run(ack(3,2)))
// 29

console.log(run(ack(3,4)))
// 125

console.log(run(ack(3,6)))
// 509

即使没有堆栈溢出，您仍有另一个问题-

console.log(run(ack(4,1)))
// ... (takes forever)

指数计算需要非常长的时间。为了缩短它，您需要研究另一种称为备忘录的技术。现在，我将把这部分留给学习者练习。我可能会在以后编辑帖子以演示该技术。