CODEWITHSUNDEEP
javascriptrecursion
Ryu
Ryu

Reputation: 41

Writing ackermann function using trampoline

my ackermann function code causes RangeError: Maximum call stack size exceeded. As i understood we can avoid this error using Trampoline function, but since i'm new with javascript, could anyone help me to know how i can use 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));
   }
}

Upvotes: 0

Views: 156

Answers (1)

Mulan
Mulan

Reputation: 135287

It's untrue that Ackermann cannot be put on a trampoline. All pure functions can be made tail-recursive and therefore a trampoline technique can always be used.

Just because ackermann calls itself twice doesn't preclude us from properly sequencing the calls. One technique to do this is using continuation-passing style -

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

Then you could put it on a trampoline -

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

Even though there's no stack overflow, you have another problem -

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

The exponential computation takes an extremely long time. To shorten it, you'll need to look into another technique called memoisation. For now, I'll leave this portion as an exercise for the learner. I may edit the post at a later time to demonstrate the technique.

Upvotes: 1

Related Questions