How to write Ackermann Function iteratively?

Question

I wrote a recursive version of Ackermann Function, and it worked properly:

int ackermann_r(int m, int n) {
    if(m == 0) {
        return n + 1;
    } else if(n == 0) {
        return ackermann_r(m - 1, 1);
    } else {
        return ackermann_r(m - 1, ackermann_r(m, n - 1));
    }
}

Then I tried to rewrite the code iteratively:

(I don't know how to use 2D array using malloc, so you could feel the code is dirty...)

int ackermann_i(int m, int n) {
    int* A = (int*) malloc((m+1) * (n+1) * sizeof(int));
    for(int i = 0; i <= m; i++) {
        for(int j = 0; j <= n; j++) {
            if(i == 0) {
                A[i*(n+1) + j] = j + 1;
            } else if(j == 0) {
                A[i*(n+1) + j] = A[(i-1)*(n+1) + 1];
            } else {
                A[i*(n+1) + j] = A[(i-1)*(n+1) + A[i*(n+1) + (j-1)]];
            }
        }
    }
    return A[m*(n+1) + n];
}

But the iterative version printed a wrong answer. For example:

m: 3
n: 2
recursive: 29
iterative: 3

Why my iterative code doesn't work?

Zeta · Accepted Answer · 2020-03-05T07:01:14.443

Undefined behaviour

Unfortunately, your code shows undefined behaviour due to access on an uninitialized value and out-of-bounds access. The simplest test that shows this behaviour is m = 1, n = 0. This indicates only two iterations of the outer loop and one iteration of the inner loop and thus is easier to analyze:

int ackermann_i(int m, int n) {
    int* A = (int*) malloc((m+1) * (n+1) * sizeof(int));
    for(int i = 0; i <= m; i++) {
        for(int j = 0; j <= n; j++) {
            if(i == 0) {
                A[i*(n+1) + j] = j + 1;              //       (1)
            } else if(j == 0) {
                A[i*(n+1) + j] = A[(i-1)*(n+1) + 1]; //       (2)
            } else {
                A[i*(n+1) + j] = A[(i-1)*(n+1) + A[i*(n+1) + (j-1)]]; // (3)
            }
        }
    }
    return A[m*(n+1) + n];
}

So let's iterate by hand:

i = 0, j = 0. We enter (1) and set A[0 + 0] = 1.
i = 1, j = 0. We enter (2) and set A[2 + 0] = A[0 + 1].
there's always at least j == 0, so we don't care about (3).

But there's the issue: we never set A[0 + 1]. That value might be zero, it might as well be something else at random; undefined behaviour ensues. Even worse, our A is not large enough: (m+1)*(n+1) is only 2 here, so A[2] is an out-of-bound array access.

This indicate two issues:

our allocated memory isn't large enough and may never be, as the inner term in a(m, a(m-1,n)) can grow much larger than n.

if we had a solution for that, we'd need to handle the trivial cases first, e.g.

for(int j = 0; j <= (n+1); ++j) {
    A[0 + j] = j + 1;          // set all A[i,j] where i = 0
}

A deeper issue with the algorithm

There is however one deeper issue. Your code implies that the Ackermann function can be calculated in θ(m * n). That's however impossible. Instead, you need at least a stack or something similar that can grow in size to calculate the result. This implementation in Java provides some inspiration.

How to write Ackermann Function iteratively?

1 Answers1

Undefined behaviour

A deeper issue with the algorithm