Win a copy of Functional Reactive Programming this week in the Other Languages forum!

# adding commas as thousands separators recursively

Subhash L. Sriram
Greenhorn
Posts: 28
Hi,

I am trying to write a program that will take in a positive integer and return it back to the user with commas in the appropriate places, and it has to be done recursively.

I have it kind of working, but I think the code is too long. Basically, my function is not recursive unless someone enters a digit that is larger than 7 digits. For 4, 5, & 6 digits, I have it exactly defined for what it should output back.

I am having a hard time thinking about the best way to make it work recursively no matter how many digits the input number is, but I am getting stuc!!

If anyone could give me an idea, I would really appreciate it.

Here is an example of what mine does.

public int putCommas(String n)
{
int l = n.length();
if (l == 4)
{
System.out.println(n.substring(0,1) + "," + n.substring(1,length));
}

Then, it has the same basic definition if l = 5 & 6. When l = 7 though, I just tell it to:

System.out.print(n.substring(0,1) + ",");
n = n.substring(0, length-1);
return putCommas(n);

Again, all help would be appreciated!

Thanks,

David Harkness
Ranch Hand
Posts: 1646
There are two parts to any recursive algorithm:
• It has a stop condition where it doesn't need to call itself, and
• It calls itself to handle the other cases.

• You've already got the stop condition (n doesn't need any commas), so the tricky part, of course, is the second case. You need to define the algorithm as a function of itself. Take the classic factorial example:Now, just because the factorial algorithm uses "n - 1" in its next call doesn't mean that your algorithm must call itself with one less character of the input String.

Given that hint, how could you define your algorithm as a function of itself? Think of the thing that you need to do x number of times, and then write it such that each call to putCommas(n) does that thing only one time, calling itself to do it the other (x - 1) times.

By the way, putCommas() needs to return String, but I assume you've got that in your actual program. Also, see if you can generalize it a bit to handle the cases of 4, 5, and 6 in one step. You'll need to play with the substring indices a bit, but it will be shorter and give you more practice.

Finally, welcome to JavaRanch!
[ January 31, 2005: Message edited by: David Harkness ]

Subhash L. Sriram
Greenhorn
Posts: 28
Thanks for the help. I will think about what you said, and give it a shot

Michael Dunn
Ranch Hand
Posts: 4632
>I am having a hard time thinking about the best way to make it work
>recursively no matter how many digits the input number is, but I am getting stuc!!

this might be one way

check for the first comma - indexOf() (if < 0 make it length of string)
if the length of the string && firstComma are both > 3, call recursively with
new StringBuffer(str).insert(firstComma-3,",").toString()

Steven Bell
Ranch Hand
Posts: 1071
This looks like something that should take 3 or 4 lines of code.

Hints:
Under what condition do you not need to put in any commas.

What information do you need to place just the next comma.

Subhash L. Sriram
Greenhorn
Posts: 28
Originally posted by David Harkness:

Finally, welcome to JavaRanch!

[ January 31, 2005: Message edited by: David Harkness ][/QB]

Thanks

Subhash L. Sriram
Greenhorn
Posts: 28
Originally posted by Michael Dunn:
>I am having a hard time thinking about the best way to make it work
>recursively no matter how many digits the input number is, but I am getting stuc!!

this might be one way

check for the first comma - indexOf() (if < 0 make it length of string)
if the length of the string && firstComma are both > 3, call recursively with
new StringBuffer(str).insert(firstComma-3,",").toString()

Branching off that idea, would this work?

[ January 31, 2005: Message edited by: Subhash S ]

[ January 31, 2005: Message edited by: Subhash S ]
[ January 31, 2005: Message edited by: Subhash S ]

Michael Dunn
Ranch Hand
Posts: 4632
>Branching off that idea, would this work?

I didn't get past this line
public int putCommas(String n)

I thought you were trying to recursively add commas, returning the String (with commas)
i.e. the return value should be a String

This is the way I put it together

Steven Bell
Ranch Hand
Posts: 1071
I hate to do this, but this is what I was thinking (I didn't run this).

Assuming you are getting some string such as "54856254100025400" and you want the return value to be "54,856,254,100,025,400" .

There might be a one off error in there on the subString, but I don't think so.
edit: forgot a parens
[ January 31, 2005: Message edited by: Steven Bell ]

Subhash L. Sriram
Greenhorn
Posts: 28
Originally posted by Michael Dunn:
>Branching off that idea, would this work?

I didn't get past this line
public int putCommas(String n)

I thought you were trying to recursively add commas, returning the String (with commas)
i.e. the return value should be a String

This is the way I put it together

Thanks for the reply. Yes, it should be returning a String, I am not sure why I did it as an int in the first place, it is not like that in my code. When I typed it, I just typed away, and I didnt look at it.

Subhash L. Sriram
Greenhorn
Posts: 28
Originally posted by Michael Dunn:
>Branching off that idea, would this work?

I didn't get past this line
public int putCommas(String n)

I thought you were trying to recursively add commas, returning the String (with commas)
i.e. the return value should be a String

This is the way I put it together

Using what you wrote, I was able to get mine to work. If you dont mind, I have a couple of questions:

In my code, I used a variable offSet to find where the first comma needed to be, and you went straight and said

Does that work because if there is no comma the first time, it will return a -1? If so, I wish I knew that before!

Is that why you have the if statement to see if it is less than zero?

Thank you very much for all the help, I really appreciate it.

Stephen Bell,

I was looking at your code, and I ran it, and I got an infinite loop of exceptions. I think it is because you are returning a substring, instead of a subtring back to the function, and it is always the same.

Thank you though for your help, I really appreciate it.

Ernest Friedman-Hill
author and iconoclast
Marshal
Posts: 24212
35
Mr. S --

Welcome to JavaRanch!

You may not have read our naming policy on the way in. It reqiures that you use a full, real (sounding) first and last name for your display name. Initials aren't enough. You can change your display name here. Thanks!

Michael Dunn
Ranch Hand
Posts: 4632
>Does that work because if there is no comma the first time, it will return a -1?

Correct

>Is that why you have the if statement to see if it is less than zero?

Yes, and then to set 'firstComma' at the end of the string so the
stringbuffer.insert(firstComma-3) will work on the first instance.

Steven Bell
Ranch Hand
Posts: 1071
Hmm, I ran this and it worked.

Subhash L. Sriram
Greenhorn
Posts: 28
Originally posted by Steven Bell:
Hmm, I ran this and it worked.

Hmm...I must have done something wrong? The only difference I see between yours & mine is that my tester was in a different file.

I used input from the console, but I dont see how that could have been a problem. I tried entering 454, and ofcourse it worked, but when I entered 1234, I got a full page of Java exceptions...

I will check again.

Subhash L. Sriram
Greenhorn
Posts: 28
Originally posted by Ernest Friedman-Hill:
Mr. S --

Welcome to JavaRanch!

You may not have read our naming policy on the way in. It reqiures that you use a full, real (sounding) first and last name for your display name. Initials aren't enough. You can change your display name here. Thanks!

Hi,

Thanks! When I first registered, I tried to put in Subhash Sriram, but it said it was already taken, and that is why I put in an initial. Anyway, I have updated it with my middle initial as well.

David Harkness
Ranch Hand
Posts: 1646
I hate to be the bad guy here, but when did we stop helping people learn and start running a homework service?

Subhash L. Sriram
Greenhorn
Posts: 28
Originally posted by David Harkness:
I hate to be the bad guy here, but when did we stop helping people learn and start running a homework service?

I apologize. In the future, I will try to get help with the concept only, as I originally asked for.

I had an idea how to do it, but I just wasnt getting it with the least code as possible.

Steven Bell
Ranch Hand
Posts: 1071
Originally posted by David Harkness:
I hate to be the bad guy here, but when did we stop helping people learn and start running a homework service?

Generally I would agree with you, but Subhash started his post with code and after some suggestions reposted with some reworked code. On something that can be so simple, with somebody who at least appears to be trying to learn and has put forth some effort, I don't feel as bad about posting a few lines of code.

Subhash, if you have any questions on what is happening in any of the code please post with your questions.

Subhash L. Sriram
Greenhorn
Posts: 28
Stephen,

Thank you for your help. I do understand all the code. I must say, I did not think it could be so simple, and I did not know that the indexOf function returned a -1 if the character you are searching for is not in the string.

I have programmed in Java, but it has been a while, so I am trying to gain back all I had learned before.

Thanks again,

David Harkness
Ranch Hand
Posts: 1646
Subhash: Please don't apologize as you asked just the right questions without asking to be given a solution.

Steven: I hope I didn't come across as too nagging. I don't really like that gremlin because it looks so much like "I'm better than you, how dare you do that" to me. There's just nothing in between. I think I saw "I hate to do this, but this is what I was thinking" and read it as "Ah heck, I can beat Michael's solution!" which I'll be the first to admit I have done more than once myself.

I remember my early days of programming, and I so rarely get that same wonderful feeling of working a problem every which way to figure it out and then BAM getting it finally. So I try now to avoid robbing it from others who are at that level of wonder and exploration and, yes, frustration. But that's what makes a good puzzle.

Anyway, I certainly enjoy the friendly atmosphere here, so I hope my admonishment didn't come across too snooty; it wasn't intended as such. Besides, Subhash, you'll get plenty more chances to try your hand at recursion, so no worries!

Mayank Verma
Greenhorn
Posts: 1
[/code][/code]

Campbell Ritchie
Sheriff
Posts: 50266
79
Welcome to the Ranch

Not a recursive solution, and by no means simple. There is a much easier way to do it (but recursive).