The Ackermann Function and Recursion

Question

I've tried to write the recursive Ackermann function in Java. But I think I've gone very very wrong somewhere! Could anyone take a look, check and maybe point my in the right direction of correcting my code? Thanks!

Ackermann

The issue I have with the code is that after I wrote it, I thought, what if n == 0 and m == 0, there's not an area for this? Would this fall under the if (m == 0) or would it need it's own if-statement?

Is my following solution correct? If I give it there same numbers in different sequence it gives a different result and I'm unsure if this is meant to be the case.

public static int ackermann(int m, int n) {

        if (m == 0) {

            return n + 1;

        } else if ((m > 0) && (n == 0)) {

            return ackermann(m-1, n);

        } else if ((m > 0) && (n > 0)) {

            return ackermann(m-1, ackermann(m,n-1));

        } else {

            return 0;

        }

    }

I thought about it some more and I think I've gone even more wrong. If you can't figure out what I've done I gave each if statement an opposite, because I thought if the m and n values are given in a different way the following code will work. It clearly doesn't but could someone try to explain where I've gone wrong?

public static int ackermann(int m, int n) {

        if (m == 0) {

            return n + 1;

        } else if (n == 0) {

            return m + 1;

        } else if ((m > 0) && (n == 0)) {

            return ackermann(m-1, n);

        } else if ((n > 0) && (m == 0)) {

            return ackermann(n-1, m);

        } else if ((m > 0) && (n > 0)) {

            return ackermann(m-1, ackermann(m,n-1));

        } else if ((n > 0) && (m > 0)) {

            return ackermann(n-1, ackermann(n, m-1));

        } else {

            return 0;

        }

    }

Your final `else` should throw an `InvalidArgumentException`. — SLaks, Jan 01 '12 at 16:18

score 5 · Answer 1 · edited Jan 01 '12 at 16:26

5

This part is wrong:

    } else if ((m > 0) && (n == 0)) {
        return ackermann(m-1, n);

That should be A(m - 1, 1)

edited Jan 01 '12 at 16:26

Perception

79,279
19
185
195

answered Jan 01 '12 at 16:19

SLaks

868,454
176
1,908
1,964

Ted Hopp · Accepted Answer · 2012-01-04T18:18:06.440

I think your first version is almost correct. I'd modify it slightly:

public static int ackermann(int m, int n) {
    if (m < 0 || n < 0) {
        throw new IllegalArgumentException("Non-negative args only!");
    }

    if (m == 0) {
        return n + 1;
    } else if (n == 0) {
        return ackermann(m-1, 1); // Corrected!
    } else {
        // perforce (m > 0) && (n > 0)
        return ackermann(m-1, ackermann(m,n-1));
    }
}

The m == 0 && n == 0 case should be included in the m == 0 case.

EDIT: Note that the Ackermann function is defined only for non-negative arguments. In particular, ackermann(0, -1) should throw an exception. Thus, you cannot just convert your last else clause to a throw.

score 2 · Answer 3 · answered Dec 16 '17 at 01:37

It's interesting that all the answers to your question pointed out your error in first version but says nothing about the big error in second version

 else if (n == 0) {
        return m + 1;
    }

Which, for positive integers, is equivalent in condition with

else if ((m > 0) && (n == 0)) {
        return ackermann(m-1, n);
    }

So your function will return m+1 but not ackermann(m-1, 1) which should for the second case ((m > 0) && (n == 0)) .

Jonathan Leffler · Answer 4 · 2012-01-01T16:24:26.260

1

The 'if m = 0' rule applies for all values of n, so A(0, 0) is 1.

The 'else' clause could only be used if m and n were both negative on entry to the function, which could be diagnosed as an exception. Indeed, if either m or n is negative, you should diagnose the error. Alternatively, since A(m, n) never returns zero otherwise, the 0 could be taken as signalling the error.

Note that the stack depth required to evaluate A(m, n) is the same as the answer - and A(m, n) gets very big very quickly. Don't bother to try evaluating A(4, 4); your computer does not have enough memory.

edited Jan 01 '12 at 16:24

answered Jan 01 '12 at 16:18

Jonathan Leffler

730,956
141
904
1,278

Actually, the Ackermann function is defined only for non-negative arguments. (It is not defined, for instance, for m == 0, n == -1.) – Ted Hopp Jan 01 '12 at 16:30
Agreed: but the Java code takes signed integers, so it can be misused when it is called - and maybe the code should diagnose that. – Jonathan Leffler Jan 01 '12 at 17:29
My point was simply that the code as it stands will cheerfully return 0 when called with (0, -1). Changing the `else` clause isn't enough to fix this. – Ted Hopp Jan 01 '12 at 17:39

score 0 · Answer 5 · answered Jan 01 '12 at 16:20

0

The first snippet is OK, except it returns ackermann(m-1, n) instead of ackermann(m-1, 1) in the second case. The default case, which should never happen, should throw an IllegalStateException in case it actually happens.

answered Jan 01 '12 at 16:20

JB Nizet

678,734
91
1,224
1,255

The Ackermann Function and Recursion

5 Answers5