Learning Java Recursion, Ackerman function

I'm working on a recursive Ackermann function in Java. I am getting an error at may recursive line开发者_开发知识库, 23.

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

Thanks so much if anyone could point out what's wrong.

-Kyle

   /*enter code here

     Ackerman's function, A(m, n) is defined:
     A(0 , n) = n + 1 for n  >= 0 
     A(m , 0) = A(m – 1 , 1) for m > 0
     A(m , n) = A(m – 1 , A(m , n - 1)) for n >= 0

    */

    public class AckFun {

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

      if (m == 0) {
       return 2 * n;
      } else if (m >= 1) {
       if (n == 0) {
        return 0;
       } else if (n == 1) {
        return 2;
       } else {
        return Ack(m - 1, Ack(m, n - 1));
       }
      }
      return n; // Not sure what to return here, Eclipse suggested this.
     }

     public static void main(String args[]) {
      System.out.println(Ack(3, 4));
     }
    }

You need to make your stack larger:

http://thilinamb.wordpress.com/2008/12/22/how-to-increase-the-java-stack-size/

With larger stack it runs without stackoverflow, but gives 0.

EDIT: Your code is wrong, that is why it gives the error. Try to rewrite the code exactly as the definition says:

    //I assume that you check that n and m are non-negative before you run this
    if (m == 0) {
         return n + 1;
    } else if (n == 0) {
        return Ack(m - 1, 1);
    } else {
        return Ack(m - 1, Ack(m, n - 1));
    }

PS. Don't blame me for posting source code for homework problems. I believe that the best way to learn programming is by reading and understanding someone else's code.

You've exceeded the maximum recursion depth. That's one of the features of the Ackermann function. :)

If you call it with smaller numbers, like Ack(3,3), then it doesn't overflow the stack.

It's possible to increase Java's recursion depth limit, but that's not necessarily a good solution. This may be an exercise in transforming the program so that it doesn't use Java's built-in call stack, but keeps track of each call in a data structure (perhaps a Stack). You can also use memoization, where you record the result of the function call so you don't have to compute the same result over and over.

With a return in front, you don't need 'else'.

if (m == 0)    return n + 1;
if (n == 0)    return ack (m - 1, 1);
return ack (m - 1, ack (m, n - 1));