The Ackermann function is a classic example of a recursive function, notable especially because it is not a primitive recursive function. It grows very quickly in value, as does the size of its call tree.



The Ackermann function is usually defined as follows:







A
(
m
,
n
)
=


{



n
+
1



if 

m
=
0




A
(
m
−
1
,
1
)



if 

m
>
0

 and 

n
=
0




A
(
m
−
1
,
A
(
m
,
n
−
1
)
)



if 

m
>
0

 and 

n
>
0.








{\displaystyle A(m,n)={\begin{cases}n+1&{\mbox{if }}m=0\\A(m-1,1)&{\mbox{if }}m>0{\mbox{ and }}n=0\\A(m-1,A(m,n-1))&{\mbox{if }}m>0{\mbox{ and }}n>0.\end{cases}}}






Its arguments are never negative and it always terminates.



Task

Write a function which returns the value of 



A
(
m
,
n
)


{\displaystyle A(m,n)}

. Arbitrary precision is preferred (since the function grows so quickly), but not required.



See also

 Conway chained arrow notation for the Ackermann function.


 
tailrec fun A(m: Long, n: Long): Long {
    require(m >= 0L) { "m must not be negative" }
    require(n >= 0L) { "n must not be negative" }
    if (m == 0L) {
        return n + 1L
    }
    if (n == 0L) {
        return A(m - 1L, 1L)
    }
    return A(m - 1L, A(m, n - 1L))
}
 
inline fun<T> tryOrNull(block: () -> T): T? = try { block() } catch (e: Throwable) { null }
 
const val N = 10L
const val M = 4L
 
fun main() {
    (0..M)
        .map { it to 0..N }
        .map { (m, Ns) -> (m to Ns) to Ns.map { n -> tryOrNull { A(m, n) } } }
        .map { (input, output) -> "A(${input.first}, ${input.second})" to output.map { it?.toString() ?: "?" } }
        .map { (input, output) -> "$input = $output" }
        .forEach(::println)
}
 