Stack overflow error in Java recursion

Question

I'm trying to implement a code that returns the sum of all prime numbers under 2 million. I have an isPrime(int x) method that returns true if the the number is prime. Here it is:

public static boolean isPrime(int x) {

        for (int i = 2; i < x; i++) {

            if (x % i == 0) {
                return false;
            }

        }
        return true;

    }

And the other method, which I'm trying to implement recursively, only works until a certain number, over that number and I get a stack overflow error. The highest I got the code to work was for 10,000.

Here it is:

public static int sumOfPrimes(int a) {

    if (a < 2000000) {  //this is the limit

        if (isPrime(a)) {
            return a + sumOfPrimes(a + 1);

        } else {
            return sumOfPrimes(a + 1);
        }

    }
    return -1;
}

So why do I get a stack overflow error when the number gets bigger and how can I deal with this? Also, how do you normally deal with writing code for such big numbers? IE: normal number operations like this but for larger numbers? I wrote this recursively because I thought it would be more efficient but it still wont work.

Is there any reason at all you are not using a loop? You cannot have such huge recursion depth. You will fill up your whole stack which is why you get a Stack Overflow exception. — Xaver Kapeller, Aug 19 '15 at 14:16
@XaverKapeller I tried using a loop but the problem was when I tried 2 million, nothing happened. It was trying to complete the code but it was taking a long time. Which is why I switched to recursion. — ninesalt, Aug 19 '15 at 14:32
You aren't even really using recursion... Do you realize what your code is actually doing? I highly doubt it. Took me a few minutes to understand it so I am not surprised you are having problems. Suffice it to say that this program is not doing what you think it is doing. — Xaver Kapeller, Aug 19 '15 at 14:36
This isn't even really a problem which is suited for recursion. Whatever issues you had with the loop, that is the place to start. What you have now is very far removed any solution and fixing this is not the way to go. — Xaver Kapeller, Aug 19 '15 at 14:38
@XaverKapeller Okay then, but what do you mean do i realize what my code is doing? It works fine for numbers smaller than 10,000. Elaborate? — ninesalt, Aug 19 '15 at 14:41
@Swailem95 how do you even use this method? Do you pass in 0 as a parameter? You do realize that the parameter you pass in serves as a lower bound and determines at which point you start to sum up the primes right? — Xaver Kapeller, Aug 19 '15 at 14:50
@XaverKapeller Yes I know. I pass a 0 to it. I told you it's working fine for smaller numbers. If i'm missing something, you could just tell me, rather than pointing out everything you think is wrong. — ninesalt, Aug 19 '15 at 15:08

score 6 · Answer 1 · edited Aug 20 '15 at 07:30

6

Your isPrime function is inefficient, it doesn't have to go to x, it's enough to go to the square root of x.

But that is not the reason why your solution doesn't work. You cannot have a recursion depth of 1 million.

I would solve this problem iteratively, using the sieve of eratosthenes and for loop over the resulting boolean array.

edited Aug 20 '15 at 07:30

answered Aug 19 '15 at 14:05

Tawcharowsky

615
4
18

score 1 · Answer 2 · answered Aug 20 '15 at 06:20

In general if you would still like to use recursion, you can use tail recursion. In recursion each function call will push some data to the stack, which is limited, thus generating a stackoverflow error. In tail recursion you won't be pushing anything to the stack, thus not throwing the exception.

Basically all you need is sending the data of the previous computation as parameter instead of having it on the stack.

So:

function(int x) {
    // end condition
    return function(x - 1) + x;
}

with tail recursion would be

function (int max, int curr, int prev, int sum) {
    if (curr > max) 
        return sum;

    return function (max, curr + 1, curr, sum + curr)
}

Keep in mind this is just pseudo code not real java code, but is close enough to the java code.

For more info check

What is tail recursion?

Java does not support tail recursion. – Prashant Sep 02 '18 at 17:12 — Prashant, Sep 02 '18 at 17:12

Amit Bhati · Answer 3 · 2015-08-19T14:24:24.007

Use Sieve of Eratosthenes:-

Following is the algorithm to find all the prime numbers less than or equal to a given integer n by Eratosthenes’ method:

1) Create a list of consecutive integers from 2 to n: (2, 3, 4, …, n).
2) Initially, let p equal 2, the first prime number.
3) Starting from p, count up in increments of p and mark each of these numbers greater than p itself in the list. These numbers will be 2p, 3p, 4p, etc.; note that some of them may have already been marked.
4) Find the first number greater than p in the list that is not marked. If there was no such number, stop. Otherwise, let p now equal this number (which is the next prime), and repeat from step 3.

public static void main(String[] args) {
    int n = 30;
    System.out.printf("Following are the prime numbers below %d\n", n);
    SieveOfEratosthenes(n);
}

static void markMultiples(boolean arr[], int a, int n)
{
    int i = 2, num;
    while ( (num = i*a) <= n )
    {
        arr[ num-1 ] = true; // minus 1 because index starts from 0.
        ++i;
    }
}

// A function to print all prime numbers smaller than n
static void SieveOfEratosthenes(int n)
{
    // There are no prime numbers smaller than 2
    if (n >= 2)
    {
        // Create an array of size n and initialize all elements as 0
        boolean[] arr=new boolean[n];
        for(int index=0;index<arr.length-1;index++){
            arr[index]=false;
        }

        for (int i=1; i<n; ++i)
        {
            if ( arr[i] == false )
            {
                //(i+1) is prime, print it and mark its multiples
                System.out.printf("%d ", i+1);
                markMultiples(arr, i+1, n);
            }
        }
    }
}

Output:-
Following are the prime numbers below 30
2 3 5 7 11 13 17 19 23 29

Stack overflow error in Java recursion

3 Answers3