StackOverFlowError in java program

Question

I am trying to solve a problem which asks to find the smallest prime palindrome, which comes after a given number which means that if the input is 24, the output would be 101 as it is the smallest number after 24 which is both prime and a palindrome.

Now my code works perfectly for small values but the moment I plug in something like 543212 as input, I end up with a StackOverFlowError on line 20, followed by multiple instances of StackOverFlowErrors on line 24. Here is my code :

package nisarg;
import java.util.Scanner;

public class Chef_prime_palindromes {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        long num = input.nextLong();
        isPalindrome(num + 1);
    }

    public static boolean isPrime(long num) {
        long i;
        for (i = 2; i < num; i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }

    public static void isPalindrome(long num) {
        String word = Long.toString(num);
        int i;
        for (i = 0; i < word.length() / 2; i++) {
            if (word.charAt(i) != word.charAt(word.length() - i - 1)) {
                isPalindrome(num + 1);
            }
        }
        if (i == word.length() / 2) {
            if (isPrime(num)) {
                System.out.println(num);
                System.exit(0);
            } else {
                isPalindrome(num + 1);
            }
        }
    }
}

andih · Answer 1 · 2014-11-16T09:53:19.340

All shown exiting solutions use recursion and have the problem that at some point they will reach the point where a StackOverflowException will occur. A better solution which would also be parallelizable would be to change it into a loop.

It could be something like:

package nisarg;

import java.math.BigInteger;
import java.util.Scanner;
import java.util.concurrent.CopyOnWriteArrayList;


public class Chef_prime_palindromes {
    private static  final CopyOnWriteArrayList<BigInteger> PRIMESCACHE 
        = new CopyOnWriteArrayList<>();


    public static void main(String[] args) {
        try (Scanner input = new Scanner(System.in)) {
            BigInteger num = new BigInteger(input.nextLine());

            initPrimes(num);

            for (num = num.add(BigInteger.ONE);
                    !isPrimePalindrome(num); 
                    num = num.add(BigInteger.ONE)); 

            System.out.println(num.toString());
            }
    }

    private static void initPrimes(BigInteger upTo) {
        BigInteger i;
        for (i = new BigInteger("2"); i.compareTo(upTo) <= 0 ; i = i.add(BigInteger.ONE)) {
            isPrime(i);
        }
    }


    public static boolean isPrimePalindrome(BigInteger num) {
        return isPrime(num) && isPalindrome(num);
    }

    // could be optimized
    public static boolean isPrime(BigInteger num) {

        for (int idx = PRIMESCACHE.size() - 1; idx >= 0; --idx) {
            if (num.mod(PRIMESCACHE.get(idx)).compareTo(BigInteger.ZERO) == 0) {
                return false;
            }   
        }

        if (!PRIMESCACHE.contains(num)) {
            PRIMESCACHE.add(num);
        }
        return true;
    }

    public static boolean isPalindrome(BigInteger num) {
        String word = num.toString();
        int i;
        for (i = 0; i < word.length() / 2; i++) {
            if (word.charAt(i) != word.charAt(word.length() - i - 1)) {
                return false;
            }
        }
        return true;
    }
}

Sorry, I did not read closely enough ;-) – andih Nov 16 '14 at 10:02 — andih, Nov 16 '14 at 10:02

marcelv3612 · Accepted Answer · 2014-11-16T05:58:27.433

A new String object is created in each recursive call and placed onto stack (the place where all variables created in methods are stored until you leave the method), which for a deep enough recursion makes JVM reach the end of allocated stack space.

I changed the locality of the String object by placing it into a separate method, thus reducing its locality and bounding its creation and destruction (freeing of stack space) to one recursive call.

package com.company;

import java.util.Scanner;

public class Chef_prime_palindromes {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        long num = input.nextLong();
        isPalindrom(num + 1);
    }

    public static boolean isPrime(long num) {
        long i;
        for (i = 2; i < num; i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }

    private static void isPalindrom(long num) {
        for (; ; ) {
            if (isPalindrome(num)) {
                if (isPrime(num)) {
                    System.out.println(num);
                    System.exit(0);
                } else {
                    num++;
                }
            } else {
                num++;
            }
        }
    }

    public static boolean isPalindrome(long num) {
        String string = String.valueOf(num);
        return string.equals(new StringBuilder(string).reverse().toString());
    }
}

thank you I understand what you are saying. I can't help but ask another question. Would the size of this stack be machine dependent or language dependent or both or none? — tofu, Nov 16 '14 at 06:04
It is dependent on both machine and language. See this post for default stack sizes in java for different jvms http://stackoverflow.com/questions/6020619/where-to-find-default-xss-value-for-sun-oracle-jvm — marcelv3612, Nov 16 '14 at 06:11

score 1 · Answer 3 · edited May 23 '17 at 11:44

First thing you should be aware of is the fact that your resources are limited. Even if your implementation was precise and all recursive calls were correct, you may still get the error. The error indicates your JVM stack ran out of space. Try to increase the size of your JVM stack ( see here for details).

Another important thing is to look for the distribution of prime and palindrome numbers. Your code runs by testing every num+1 against palindrome property. This is incorrect. You test for palindrome only when the number is prime. This will make the computation much much easier (and reduce recursive calls). I have edited your code accordingly and got the closest palindrome number after 543212 (1003001) . Here it is:

    public static void main(String[] args) {

     Scanner input = new Scanner(System.in);
    long num = input.nextLong();
    //isPalindrome(num+1);
    nextPrimePalindrome(num+1);
    }

    public static void nextPrimePalindrome(long num)
    {
        boolean flag=true;
        while(flag)
        {
            if(isPrime(num))
                if(isPalindrome(num))
                {
                    System.out.println(num);
                    flag=false;
                }
              num++;      
        }
    }

public static boolean isPrime(long num){
    long i;
    for(i=2;i<num;i++){
        if(num%i == 0){
            return false;
        }
    }
    return true;
}

public static boolean isPalindrome(long num)
{
    String word=Long.toString(num);
    for(int i=0;i<word.length()/2;i++)
        if(word.charAt(i)!=word.charAt(word.length()-i-1))
            return false;
    return true;
}
}

StackOverFlowError in java program

3 Answers3