**Advent Calendar 2020**

### | **Day 19** | **Day 20** | **Day 21** |

The gift is presented by **Yozen Hernandez**. Today he is talking about his solution to the task `Ackermann function`

of **“The Weekly Challenge - 017”**. This is re-produced for **Advent Calendar 2020** from the original **post** by **Yozen Hernandez**.

The Weekly Challenge is back, and our first challenge was to implement a function known as the Ackermann function:

Create a script to demonstrate Ackermann function. The Ackermann function is defined as below, m and n are positive number:

A(m, n) = n + 1 if m = 0 A(m, n) = A(m - 1, 1) if m > 0 and n = 0 A(m, n) = A(m - 1, A(m, n - 1)) if m > 0 and n > 0

Technically, the above formulation is known as the **“Ackermann-Péter function”**, but as the Wikipedia page states, many authors refer to it as “the” Ackermann function.

This is looked like a fairly straightforward implementation of a recursive function, but it did have a few hairs. Firstly, as can be seen above, the function is piecewise, and is defined only for non-negative integers. In fact, the recursive calls gradually step the values down to 0, with the deepest call possible being reached when m=0.

```
sub A ( $m = 3, $n = 3) {
croak "Error: function only defined for nonnegative integers."
. "(got: m = $m, n = $n)"
if ( $m < 0 && $n < 0 );
# A(m, n) = n + 1 if m = 0
return $n + 1 if $m == 0;
# A(m, n) = A(m - 1, 1) if m > 0 and n = 0
# A(m, n) = A(m - 1, A(m, n - 1)) if m > 0 and n > 0
return A( $m - 1, ($n == 0) ? 1 : A($m, $n-1) );
}
```

One thing I initially missed when implementing this, is that the function not only should subtract 1 from $n when both values are greater than 0, but it should actually make a second, embedded call there! It took me forever to notice that was missing 😒.

Once that was implemented, I decided to test it with larger values, because I don’t read whole Wikipedia pages. After about a minute of waiting, I decided to scoll down… You should check out the table of values on the wiki page. The short version is that the Ackermann function grows. VERY quickly. I kept my testing down to some smaller values, and those all passed.

Finally, I decided to compare performance with and without memoization. Memoizing really only makes sense with repeated execution, and I don’t know of the actual applications of this function so I don’t know how true that would be.

With default parameters, using `Benchmark::Forking`

gets me the following results;

```
Rate no_memo memo
no_memo 269501/s -- -68%
memo 850801/s 216% --
```

Its a definite improvement, but again, I’m not sure how useful it would be in a real world application.

If you have any suggestion then please do share with us perlweeklychallenge@yahoo.com.