user
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 {\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 {\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.
assistant
(formerly Perl 6)

**Works with**: Rakudo version 2018.03

```
sub A(Int $m, Int $n) {
    if    $m == 0 { $n + 1 } 
    elsif $n == 0 { A($m - 1, 1) }
    else          { A($m - 1, A($m, $n - 1)) }
}
```

An implementation using multiple dispatch:

```
multi sub A(0,      Int $n) { $n + 1                   }
multi sub A(Int $m, 0     ) { A($m - 1, 1)             }
multi sub A(Int $m, Int $n) { A($m - 1, A($m, $n - 1)) }
```

Note that in either case, Int is defined to be arbitrary precision in Raku.

Here's a caching version of that, written in the sigilless style, with liberal use of Unicode, and the extra optimizing terms to make A(4,2) possible:

```
proto A(Int \𝑚, Int \𝑛) { (state @)[𝑚][𝑛] //= {*} }

multi A(0,      Int \𝑛) { 𝑛 + 1 }
multi A(1,      Int \𝑛) { 𝑛 + 2 }
multi A(2,      Int \𝑛) { 3 + 2 * 𝑛 }
multi A(3,      Int \𝑛) { 5 + 8 * (2 ** 𝑛 - 1) }

multi A(Int \𝑚, 0     ) { A(𝑚 - 1, 1) }
multi A(Int \𝑚, Int \𝑛) { A(𝑚 - 1, A(𝑚, 𝑛 - 1)) }

# Testing:
say A(4,1);
say .chars, " digits starting with ", .substr(0,50), "..." given A(4,2);
```

Output:

```
65533
19729 digits starting with 20035299304068464649790723515602557504478254755697...
```