Code gives java.lang.StackOverflowError for 123456789 but not for 9999999999999999999

Question

So I'm doing this exercise on finding the next palindrome with only the use of the String class.

I kinda solved it, but had a question about something.

When I enter a String like 123456789, I get a java.lang.StackOverflowError. While when I enter a larger string like 9999999999999999999, I won't get the error. I did some research on this website and I think it has something to do with the recursive palindrome method I use.

Is there any way I could improve my code so it will handle bigger numbers? And why would 123456789 give an error and 9999999999999999999 not? The latter is bigger.

import java.io.*;

public class mainclass {

public static void main(String[] args) throws IOException {
    InputStreamReader isr = new InputStreamReader(System.in);
    BufferedReader in = new BufferedReader(isr);
    System.out.println(palindroom(in.readLine()));
    }

public static String increment(String str){
    String incre="";
    if(str.equals("9")){incre = "10";}
    else{
        switch(str.charAt(str.length()-1)){
        case '0': incre = str.substring(0, str.length()-1)+"1";break;
        case '1': incre = str.substring(0, str.length()-1)+"2";break;
        case '2': incre = str.substring(0, str.length()-1)+"3";break;
        case '3': incre = str.substring(0, str.length()-1)+"4";break;
        case '4': incre = str.substring(0, str.length()-1)+"5";break;
        case '5': incre = str.substring(0, str.length()-1)+"6";break;
        case '6': incre = str.substring(0, str.length()-1)+"7";break;
        case '7': incre = str.substring(0, str.length()-1)+"8";break;
        case '8': incre = str.substring(0, str.length()-1)+"9";break;
        case '9': incre = increment(str.substring(0, str.length()-1))+"0";break;
        };
        }
    return incre;
    }

public static String palindroom(String str){
    String palin=increment(str);
    boolean isPalindroom=true;
    for(int i=0;i<palin.length();i++){
        if(palin.charAt(i)==palin.charAt(palin.length()-i-1)){}
        else{isPalindroom=false;}
    }
    if(isPalindroom){return palin;}
    else{return palindroom(increment(str));}
}
}

General observation: Your recursion could trivially be replaced with a loop, avoiding all risk of stack overflow. — keshlam, Jan 13 '14 at 22:05
Also, why do you need `str.substring(0, str.length()-1)`? It's exactly identical to `str`. — The Guy with The Hat, Jan 13 '14 at 22:10
Agree with the comments above. Can you post the stack trace? I copied your code into eclipse and it runs without any Overflow error. — Michael W, Jan 13 '14 at 22:12
I need that because I want a string without the last character, it's not the same as str. And how could you make palindroom into a loop? You can't now how much numbers until the next palindrome beforehand? Maybe I don't see it because I'm quite new to programming. — user3191960, Jan 13 '14 at 22:12
@user3191960 In that case use `str.substring(0, str.length() - 2)` — The Guy with The Hat, Jan 13 '14 at 22:13
@RyanCarlson The code works, str.substring(0,str.length()) equals the str. — user3191960, Jan 13 '14 at 22:18
@keshlam how would I be able to make it into a loop instead of recursion? — user3191960, Jan 13 '14 at 22:29

score 4 · Accepted Answer · edited May 23 '17 at 10:24

4

Because you recurse only if the entered value isn't a palindrome, and it would take over 10,000 recursions to increment 123456789 into a palindrome.

Your code is a bit weird, you take a string, which you assume to be a number, and increment it using string manipulation. Converting to a long (or BigInteger if Long isn't big enough) would be MUCH simpler.

Further, you seem to increment twice, once at the start of the palindroom method, and again in the else block.

UPDATE From your comment, I take it you may not be clear on what a Stack Overflow Error is. So the java call stack is the stack (i.e. LIFO) of methods. In your case, your call stack would be main, palindroom, palindroom, palindroom, palindroom, palindroom, etc... Please note java only allows a maximum size for the call stack, if this size is exceeded, you get a stack overflow exception. Java stack overflow error - how to increase the stack size in Eclipse? has some details on defaults and configuring this.

edited May 23 '17 at 10:24

Community

1
1

answered Jan 13 '14 at 22:18

Taylor

3,942
2
20
33

Yea we had to do it this way, we had to make an increment method by only using the String class. I also won't get an error when I'd do 99999999999999995, which isn't a palindrome. The reason why I increment is because the question is to find the next palindrome, even if the current number is already a palindrome. But your answer helped me, I think it's because 9999999999999999995 for instance is only 4 increments away from next palindrome. – user3191960 Jan 13 '14 at 22:23
2

But it will only require 4 increments to make it a palindrome, which will take 2 recursions given your double increment. – Taylor Jan 13 '14 at 22:24
Ok thanks, your update also made some things clear. Keshlam also commented I could easily replace the recursive method by using a loop. I think this is not possible? – user3191960 Jan 13 '14 at 22:32
Happy to help. Aside, your double increment means you're skipping some numbers, I'd take the increment out of the `else` block. Also, keshlam in the comments to your question has a solid point, switching to a loop would make your code much more robust. While recursion is a favourite subject in courses it is rarely (not never, but rarely) used in business coding because it is not scalable, and you can run into this exact error. – Taylor Jan 13 '14 at 22:35
If I'd take the increment out of the else block, I'd even get a stackoverflow for 1 (I tried it). – user3191960 Jan 13 '14 at 22:42
There have been cases where, even when we *have* wanted recursive code, we have rewritten it as a loop and maintained our own stack (and stack pointer) because it took less memory space than piling up call-stack frames. Useful trick to keep in mind for largescale tasks. – keshlam Jan 13 '14 at 22:43
@Taylor You're saying the code double increments. If I enter 99999999996, I still get 99999999999 returned. If the code does double, this is not possible? You made me doubt my code :p. – user3191960 Jan 14 '14 at 00:07
trace it through, it increments twice. I think the pattern would be increment, check, increment, increment, check, increment, increment, check, etc... – Taylor Jan 14 '14 at 02:09
@Taylor When you do it with integers and use ++, it would be double. But the increment method I wrote doesn't realy increase str. It merely returns a new string. So I think since I didn't write increment(increment(str)), but just increment(str) and later on increment(str), str remains unchanged. It would be different if I'd write str=increment(str). Whick obviously has same effect as ++. Am I wrong in this logic? – user3191960 Jan 14 '14 at 14:19
Yeah you're right, you the first increment assigns it to `palin`, then you increment in the else as the method param, so you wouldn't be double-incrementing, it seems you're just doing it unnecessarily (i.e. pass `palin` on recursion) – Taylor Jan 14 '14 at 17:15

score 0 · Answer 2 · answered Jan 13 '14 at 22:35

I know you had questions on how to replace your recursive method with a loop and I had coded this up for practice so you can check it out:

  public static void main(String[] args) throws IOException {
    InputStreamReader isr = new InputStreamReader(System.in);
    BufferedReader in = new BufferedReader(isr);

    String numString = in.readLine();
    BigInteger num = new BigInteger(numString);
    do {
      num = num.add(new BigInteger("1"));
    } while(pal(num));

    System.out.println(num);
  }

  public static boolean pal(BigInteger num){
    String isPal = num.toString();
    boolean isPalindroom=false;

    for(int ii=0; ii<isPal.length(); ii++){
      if(isPal.charAt(ii) != isPal.charAt(isPal.length()-ii-1))
        isPalindroom = true;
    }

    return isPalindroom;
  }

Thanks for showing! I would mark this answer as useful but since my reputation is lower than 15, I can't. — user3191960, Jan 13 '14 at 22:51

score 0 · Answer 3 · answered Jan 13 '14 at 22:50

0

A recursion which occurs only as the last step of a function -- a so-called "tail recursion" -- is generally a loop in disguise; you're just repeating the body of the function with a new set of parameters. A good optimizer will often rewrite tail recursions into loops; apparently Java didn't in your case.

Example of a trivial iterative rewrite of this example:

public static String palindroom(String str){
  while(true)
  {
    String palin=increment(str);
    boolean isPalindroom=true;
    for(int i=0;i<palin.length();i++){
        if(palin.charAt(i)==palin.charAt(palin.length()-i-1)){}
        else{isPalindroom=false;}
    }
    if(isPalindroom){return palin;}
    else{str=palin;} //increment str, and try again
  }
}

That won't solve your logic problems -- see other responses -- but it runs entirely within a single stack frame.

answered Jan 13 '14 at 22:50

keshlam

7,931
2
19
33

I tried you code and it works perfectly.,thanks. I don't think there are logic problems since the code works on every example I tried yet. One more thing, youre loop has while(true) in it. So my initial though would be it'd never stop. Does it stop because at a certain point it returns the string? So can I conclude a return statement in a loop would cause the loop to break? – user3191960 Jan 13 '14 at 23:00
Exactly. Explicitly exiting the loop when the test succeeds would have been a bit better stylistically, but since you already had the return statements and since I was focusing on why tail-recursion can be turned into a loop, I didn't change it. (Some folks will argue strongly that no function should have more than one return point; I don't worry about it too much as long as the intent is clear.) – keshlam Jan 13 '14 at 23:35

Code gives java.lang.StackOverflowError for 123456789 but not for 9999999999999999999

3 Answers3