使用trampoline编写ackermann函数

Question

我的ackermann函数代码导致RangeError:超出了最大调用堆栈大小。据我所知，我们可以使用trampoline函数来避免这个错误，但由于我是javascript新手，有人能帮助我了解如何使用Trampoline吗？

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

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

指数计算需要很长的时间。为了缩短它，您需要研究另一种称为memoisation的技术。现在，我将把这一部分留给学习者作为练习。我可能会在稍后编辑这篇文章来演示这项技术。