java.lang.StackOverFlowError for values of 5 digits or more

Question

Here is how my code is supposed to work. First it takes a number of test cases in variable t. Now the number of text cases can be anything upto 100000. Then it takes two inputs, one for a row and another for a column. Input sample-

what is supposed to happen is this-

We have the following matrix 
1 0 0 0 0 0 ...
2 2 0 0 0 0 ...
3 3 3 0 0 0 ...
4 4 4 4 0 0 ... 
5 5 5 5 5 0 ... 
6 6 6 6 6 6 ...
and so on ... 
The matrix is created as follows, first row contains one 1 and rest 0's, second row
contains 2 twos and rest zeros, third row contains 3 threes and so on.

Given R and C, calculate the count of even and odd numbers in sub matrix[R,C].
0 is neither odd nor even and 1 based indexing is used i.e. matrix[1,1]=1

Output
For each test case print count of even and odd numbers in sub matrix[R,C].

Output Sample-

2 1
12 9
30 25

now everything works fine for small numbers in my code. The maximum value of the row and column is supposed to be 100000 each. That's where the problem occurs.For input value of 25000 in either row or column, the code works fine, but if I enter around 30000 or greater value for any of them I get stackoverflowerror.

Here is my complete code-

import java.util.Scanner;

public class TestClass {
public static void main(String args[]) throws Exception {

    Scanner input = new Scanner(System.in);
    int t = input.nextInt();
    int[][] storage = new int[t][2];

    for (int i = 0; i < t; i++) {
        for (int j = 0; j < 2; j++) {
            int x = input.nextInt();
            storage[i][j] = x;

        }
    }
    TestClass test = new TestClass();
    for (int i = 0; i < storage.length; i++) {
        int a = storage[i][0];
        int b = storage[i][1];
        test.theMethod(a, b);
    }
    input.close();
}

public void theMethod(int x, int y) {
    int d = x - y;
    int first = 0;
    int second = 0;
    int[][] resultarray = new int[1][2];
    if (x % 2 == 0) {
        if (x >= 1) {
            if (y >= x) {
                first = number(x);
                second = number(x - 1) + 1;
                resultarray[0][0] = first;
                resultarray[0][1] = second;
            } else if (y < x) {
                first = (number(x) - number(d)) - 1;
                second = (number(x - 1) - number(d - 1)) + 1;
                resultarray[0][0] = first;
                resultarray[0][1] = second;
            }
        }
    } else if (x % 2 != 0) {
        if (x >= 1) {
            if (y >= x) {
                first = number(x) + 1;
                second = number(x - 1);
                resultarray[0][0] = first;
                resultarray[0][1] = second;
            } else if (y < x) {
                first = (number(x) - number(d));
                second = number(x - 1) - number(d - 1);
                resultarray[0][0] = second;
                resultarray[0][1] = first;
            }
        }
    }
    for (int i = 0; i < resultarray.length; i++) {
        for (int j = 0; j < resultarray[i].length; j++) {
            System.out.print(resultarray[i][j]);
            System.out.print(" ");
        }
        System.out.println();
    }

}

public int number(int x) {
    if (x == 1 || x == 0) {
        x = 0;
    } else if (x > 1) {
        x = x + number(x - 2);      //*****this is the error line
    }
    return x;
}
}

The error stack trace -

Exception in thread "main" java.lang.StackOverflowError
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)
at TestClass.number(TestClass.java:74)

Now, for values greater than 25000 or somewhere around 30000 maybe , this error is displayed. One thing I would like to mention is, I have tried using long for every int value in this program, but I still get the same error for surprisingly even lower input values. Anyone knows what am i doing wrong?

You are recursing too far and using too much memory on your stack. Take a look at http://stackoverflow.com/questions/4734108/what-is-the-maximum-depth-of-the-java-call-stack for more information. — mkobit, Sep 24 '14 at 01:36

score 2 · Answer 1 · answered Sep 24 '14 at 01:37

You need to stop using recursion. You are running out of stack space due to the recursive call in your number method. You can modify the method to use a loop rather than a recursive call to itself. That will keep you from running out of stack space.

score 0 · Answer 2 · answered Sep 24 '14 at 01:46

The stack trace is giving you very clear on what is causing the stack overflow, which is the number() method.

Just a brief look, for every number n, it is going to have around n/2 levels of recursive call of number(). If you are passing 30000, that will be 15000 levels in call stack, which is quite a lot.

Your number() can actually be rewritten using a simple loop like this:

int number(int x) {
    int result = 0;

    while (x > 1) {
       result += x;
       x -= 2;
    }
    return result;
}

java.lang.StackOverFlowError for values of 5 digits or more

2 Answers2