Ackermann function

gistfile1.scala

def ackermann(m: Int, n: Int): Int = {
   (m, n) match {
     case (0, _)                   ⇒ n + 1
     case (m, 0) if m > 0          ⇒ ackermann(m - 1, 1)
     case (m, n) if m > 0 && n > 0 ⇒ ackermann(m - 1, ackermann(m, n - 1))
   }
 }
 
import scalaz._, Scalaz._, Free.{suspend ⇒ _, _}, Trampoline._
def ackermannTramp(m: Int, n: Int): Trampoline[Int] = {
  (m, n) match {
    case (0, _)                   ⇒ done(n + 1)
    case (m, 0) if m > 0          ⇒ suspend(ackermannTramp(m - 1, 1))
    case (m, n) if m > 0 && n > 0 ⇒ for {
      internalRec ← suspend(ackermannTramp(m, n - 1))
      result      ← suspend(ackermannTramp(m - 1, internalRec))
    } yield result
  }
}

gistfile2.txt

scala> ackermann(4, 1)
java.lang.StackOverflowError
	at .ackermann(<console>:23)
	at .ackermann(<console>:23)
	at .ackermann(<console>:23)
        ...

scala> ackermannTramp(4,1).run
res2: Int = 65533

LOVE this! thank you so much for posting. I am now taking a deep dive into scalaz!