recursively add to strings in java

Question

I am trying to convert int 123 to String "CBA" in java

I know I have some something misunderstood in recursion

After many println statements, I know that at a point

ss is going to be "CBA"

but then it will return "CB" and "C"

I kind of know recursion will work like this, but I don't know how to fix it

Can anyone help me with the code, thanks!

public String recur ( int x, String ss )
{
    if ( x >= 1 && x < 10 )
        ss = ss + "A";

    if ( x >= 10 && x < 100 )
    {
        ss = ss + "B";
        recur( x % 10, ss);
    }

    if ( x >= 100 && x < 1000 )
    {
        ss = ss + "C";
        recur( x % 100, ss);    
    }
return ss;

Even though Java allows it, it is bad practice to reuse method parameter values. Hint: use a StringBuilder. — fge
– fge, Commented Jun 1, 2013 at 1:53
Note that while @fge's comment is correct, it does not help to solve the OP's problem. Also the "hint" is highly questionable. At best it is a marginal microoptimization. If the OP was concerned about performance, then the correct optimization would be to implement this iteratively ... — Stephen C
– Stephen C, Commented Jun 1, 2013 at 2:01
@StephenC I wouldn't call something which guarantees data safety a "micro-optimization" — fge
– fge, Commented Jun 1, 2013 at 2:03
@fge - How does using a StringBuilder "guarantee data safety"? And what is this "data safety" you are talking about anyway? The issue here is code correctness, robustness and readability, not "data safety". — Stephen C
– Stephen C, Commented Jun 1, 2013 at 2:04
@StephenC simple: whatever optimization on a stringbuilder affects the stringbuilder itself; as a result, you can recurse and pass it as an argument, and then return sb.toString() as the argument. This is unlike String which is immutable. — fge
– fge, Commented Jun 1, 2013 at 2:07

FDinoff · Accepted Answer · 2013-06-01 02:03:15Z

1

You are ignoring the return value of recur so only the first level of recursion is being seen at the ouptput.

So you could do this to take into account the return value. (Just assign the output of recur to ss)

ss = recur( x % 10, ss);

and the other call.

ss = recur( x % 100, ss);

edited Jun 1, 2013 at 2:03

answered Jun 1, 2013 at 1:49

FDinoff

31.6k5 gold badges79 silver badges99 bronze badges

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

9 Comments

userNew Over a year ago

thanks, right I think I'm ignoring something I have changed recur( x % 10, ss); to ss = recur( x % 10, ss); ... but I am still getting only C in the ouput

FDinoff Over a year ago

did you do it for both your recur calls? I think not

Óscar López Over a year ago

OP's solution, as it is, will only work if the integer contains the digits 1, 2 or 3 - it's not general enough, and will fail for any number containing different digits

Stephen C Over a year ago

@ÓscarLópez - I think we are all guessing at what the actual problem statement really is. Certainly you can't infer it from a single example ... and a broken attempt at solving it

FDinoff Over a year ago

@ÓscarLópez I thought it was trying to convert 1 digit numbers to A, 2 digit numbers to BA and 3 digit numbers to CBA (ignoring edge cases)

|

Stephen C · Accepted Answer · 2013-06-01 03:12:12Z

(This Answer is largely for the peanut gallery ...)

Here's my take on the "best" recursive solution to the problem as stated:

public String recur ( int x )
{
    if ( x >= 1 && x < 10 ) {
        return "A";
    } else if ( x >= 10 && x < 100 ) {
        return "B" + recur( x );
    } else if ( x >= 100 && x < 1000 ) {
        return "C" + recur( x );    
    } else {
        throw new IllegalArgumentException();
    }
}

System.err.println(recur(123));

or a bit more generally:

public String recur ( int x)
    return recur0( x, 0 );
}

public String recur0 ( int x, int i )
{
    if ( x <= 0 ) {
        return "";
    else {
        return recur0( x % 10, i + 1 ) + ((char) ('A' + i));
    } 
}

System.err.println(recur(123));

As you can see, no StringBuilder is needed. At best, a StringBuilder is a micro-optimization. It does not make the code any safer, or any more readable. To illustrate, here's the first version redone using a StringBuilder

public void recur ( int x, StringBuilder sb )
{
    if ( x >= 1 && x < 10 ) {
        sb.append("A");
    } else if ( x >= 10 && x < 100 ) {
        sb.append("B");
        recur( x, sb );
    } else if ( x >= 100 && x < 1000 ) {
        sb.append("C");
        recur( x, sb );    
    } 
}

StringBuilder sb = new StringBuilder();
recur(123, sb);
System.err.println(sb.toString());

But the simplest solution for the problem as originally stated is this:

public String nonRecur(int x) {
    if ( x >= 1 && x < 10 ) {
        return "A";
    } else if ( x >= 10 && x < 100 ) {
        return "BA";
    } else if ( x >= 100 && x < 1000 ) {
        return "CBA";    
    } else {
        throw new IllegalArgumentException();
    }
}

System.err.println(nonRecur(123));

Note that there is considerable ambiguity in the way that the problem was stated, and @ÓscarLópez's solution is based on a different interpretation of the problem than mine. He is mapping the digits of the numbers to letters, rather than using the letters to signify magnitude.

In fact, the OP's actual problem is neither of these interpretations, and I don't think that any of the Answers will actually help him ... even though they do answer his Question.

Óscar López · Accepted Answer · 2013-06-01 03:17:31Z

Your approach is not correct, for starters, you don't even need to pass a string as a parameter - just build the string in the return values. Also, the logic for converting from integers to strings is overly complicated and only works if the integer contains the digits 1, 2, 3 in that exact order! Here's a simpler, working approach that processes each character in turn and works for integers with any digits:

public String recur(int x) {
    if (x <= 0)
        return "";
    return (char) (x % 10 + 'A' - 1) + recur(x / 10);
}

Explanation:

The base case occurs when the integer is equal or less than zero, and we must return an empty string in such case
The recursive step works as follows:
- We obtain the current digit from the integer by taking the remainder: x % 10, and converting the digit to an uppercase character by adding 'A' and subtracting 1
- We concatenate the previous result with the result of advancing the recursion, dividing the integer by 10

Collectives™ on Stack Overflow

recursively add to strings in java

3 Answers 3

9 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

9 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related