Recursion function - working

Question

public class Temp{
static int add(int m,int n){
    if(m==0)
        return n+1;
    else if(n==0)
        return add(m-1,1);
    else
        return add(m-1,add(m,n-1));
}
public static void main(String[] a){
    System.out.println(add(3,3));
}
}

I am not able to understand what this function is achieving. The output for (2,2) is 7 and for (3,3) is 61. I understand that the value of n decreases then value of m and then the base case is reached but how can I get the output without running the code for a given input?

Actually the question was about the function and it is the same in any language. Hence I did not add the language tag. — Shashank Gupta
– Shashank Gupta, Commented Nov 5, 2015 at 15:48

Jeff Morin · Accepted Answer · 2015-11-05 15:42:34Z

1

This is the Ackermann function (https://en.wikipedia.org/wiki/Ackermann_function), an example of non-primitive recursive function.

What do you mean by getting the output without running the code for a given input?

If you wish to compute a given value, I suggest you use a HashMap as a cache so that you can reuse already computed values. Also, I think you'd better use BigInteger values if you use m values greater than 3.

edited Nov 5, 2015 at 15:42

answered Nov 5, 2015 at 15:37

Jeff Morin

1,0101 gold badge13 silver badges25 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Recursion function - working

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related