The Ackermann Function in Java: Why Computers are Stupid

I’ve started teaching myself Java, right from the basics and as a guide I’m using the Java version of the How to Think Like a Computer Scientist book. One of the exercises at the end of the fifth chaper (called Fruitful Functions) is to implement the Ackermann Function as a recursive method. The Ackermann function is mathematically defined as:


Now, the Ackermann function is quite well suited to computerization, it takes little real intelligence to solve for any two numbers, and is mostly repetitive calculation (which computers are good at). It took me less than a minute to implement the function as a Java method as follows:

public static int ackerman(int ack1, int ack2){

if (ack1 == 0)

	return ack2+1;

else if (ack1 >0 && ack2 == 0)

	return ackerman(ack1-1, 1);
else if (ack1 >0 && ack2>0)

	return  ackerman(ack1-1, ackerman(ack1, ack2-1);
)

I passed it to the compiler and the compiler replied with a cheery: “missing return statement”. Since I already had three return statements, that meant that there was a possible path through the method where the method would end without a value being returned. The Ackermann function doesn’t work with negative numbers, so I had already implemented a check for negatives before the function call. I tried putting in another check for negatives in the function itself, but that didn’t work. By this point I was getting rather frustrated because the above code would catch all non-negative numbers and produce appropriate returns. I ran the code in my mind with a few small numbers and everything seemed to check out as it should, the values of ack1 and ack2 would keep on reducing until ack1 hit zero and the method would end with a proper return.

Finally on a hunch, I decided to remove the last if-else and make the last return statement free-standing. Semantically it was the same thing, because there was only one possible case if the first two conditions were not satisfied. And for some reason the compiler thought that this new version was perfectly passable. I haven’t entirely ruled out the possibility that there was really some path that would have resulted in no return. But I think that it is far more probable that the compiler for some reason couldn’t handle the multiple recursions and simply gave up. Of course, I’m not an expert in these things and if someone knows of a proper explanation please let me know. Until then I’ll stick to the knowledge that a computer is still quite some distance away from what would be common sense to a human (or at least the Java compiler is).

Advertisements

Published by

Shrutarshi Basu

Programmer, writer and engineer, currently working out of Cornell University in Ithaca, New York.

2 thoughts on “The Ackermann Function in Java: Why Computers are Stupid”

  1. You have declared the ‘ackerman’ function with two parameters, ‘ack1’ and ‘ack2’, each of which is an ‘int’ – in other words, an integer that can be positive or negative (or zero).
    You have promised that you will only call the function when ack1>=0 and ack2>=0, but this is simply a decision that you have happened to take and you might change your mind at any moment. What should the function do if you break your promise? The compiler can’t guess: it needs to know, and it’s complaining because you haven’t told it.
    So all your reasoning about “there was only one possible case if the first two conditions were not satisfied” is simply wrong. ack1=-1 is a possible case, because ‘int’ values can be negative as well as positive.
    If you told the compiler that ack1>=0 and ack2>=0 then it would know that you had exhausted the possibilities by the end of the last of your ‘if’ statements. In C you can do this by declaring ack1 and ack2 to be an ‘unsigned’ type. I can’t remember whether Java has unsigned types but I don’t think it does.
    Given that the compiler can’t detect this for you, the thing to do, after you’ve had ‘return’ statements for all the valid arguments, is to add a statement that throws an IllegalArgumentException if the arguments aren’t valid. I’m not sure whether you’ll then have to have a dummy ‘return 0’ after that or not.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s