Java recursion code

Question

public class Temp {
    public static void main(String[] args) {
        System.out.println(recursion(1, 100));
        System.out.println(recursion(4, 5));
        System.out.println(recursion(99, 100));
        System.out.println(recursion(100, 100));
    }

    public static int recursion(int m, int n) {
        int number = 0;
        if (m == 1) {
            number = ((2 * n) - 1);
        } else {
            number = 2 * recursion(m - 1, n - 1);
        }
        return number;
    }
}

When I run this code, the last two tests return 0's and I know they are supposed to be big numbers, is that why? How can I figure out the value of the last two??

You can easily find out the reason by debugging the code. Just add a breakpoint on the return statement. — Rohit Jain
– Rohit Jain, Commented Apr 9, 2013 at 5:24

Dawood ibn Kareem · Accepted Answer · 2013-04-09 05:15:43Z

7

You're running into arithmetic overflow. An int can only store values between -2^31 and 2^31-1. To deal with numbers this big, you need a more suitable data type, such as BigInteger.

answered Apr 9, 2013 at 5:15

Dawood ibn Kareem

80.2k15 gold badges102 silver badges112 bronze badges

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

5 Comments

tlauer Over a year ago

Would I just replace BigInteger for every int?

Alex Kreutznaer Over a year ago

Oh, you were 5 minutes earlier, sorry, when I started answering your answer was absent.

Alex Kreutznaer Over a year ago

In your case the result grows as ~ 2^m, which is really fast. Are you sure you need it?

Mel Nicholson Over a year ago

The BigInteger class implements the aritmetic operations as methods, so instead of m - 1 you have m.subtract(BigInteger.ONE) --- take a look at docs.oracle.com/javase/1.5.0/docs/api/java/math/BigInteger.html

tlauer Over a year ago

It says "cannot invoke subtract(BigInteger) on the primitive type int" so I tried different things but it's still giving me an error

Alex Kreutznaer · Accepted Answer · 2013-04-09 05:31:32Z

0

At some point you number exceeded maximum for int type. Then the result of multiplication turns negative, then - zero.

m = 31, n = 32 : number = -1073741824
m = 32, n = 33 : number = -2147483648

Next step you multiply them (m = 33, n = 34):

System.out.println((-1073741824) * (-2147483648));

Which is 0.

Starting from this point everything is 0.

edited Apr 9, 2013 at 5:31

answered Apr 9, 2013 at 5:20

Alex Kreutznaer

1,1708 silver badges18 bronze badges

1 Comment

tlauer Over a year ago

do you know what the final answer for the problem is though?

Collectives™ on Stack Overflow

Java recursion code

2 Answers 2

5 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

5 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related