Implementing the Ackermann function in Raku

This is the Task 1 from the Perl Weekly Challenge Week 17. You have to implement the so-called Ackermann function.

This is an interesting function that is defined kind of recursively but actually this is not a recursion, as the recurrent formula is using the function as an argument of itself.

Let me come to the solution in Raku, where you will immediately see the details of the definition. Multi-functions together with the where clause are very handy here.

multi A($m, $n where $m == 0) {
    $n + 1
}

multi A($m, $n where $m > 0 && $n == 0) {
    A($m - 1, 1)
}

multi A($m, $n where $m > 0 && $n > 0) {
    A($m - 1, A($m, $n - 1))
}

Notice that the condition in the last variant can be omitted but I prefer keeping it for clarity.

Let us test the function against small numbers and compare the results with the table on Wikipedia. Note that for arguments bigger than 4-5 the return value of the function are so high that it may take very long to compute it.

for ^4 X ^5 -> ($m, $n) {
    say "A($m, $n) = " ~ A($m, $n);
}

This program prints the following lines:

A(0, 0) = 1
A(0, 1) = 2
A(0, 2) = 3
A(0, 3) = 4
A(0, 4) = 5
A(1, 0) = 2
A(1, 1) = 3
A(1, 2) = 4
A(1, 3) = 5
A(1, 4) = 6
A(2, 0) = 3
A(2, 1) = 5
A(2, 2) = 7
A(2, 3) = 9
A(2, 4) = 11
A(3, 0) = 5
A(3, 1) = 13
A(3, 2) = 29
A(3, 3) = 61
A(3, 4) = 125

Seems to be correct, so we can stop here.

→ GitHub repository
→ Navigation to the Raku challenges post series

Leave a Reply Cancel reply