This week's book giveaway is in the Performance forum.We're giving away four copies of The Java Performance Companion and have Charlie Hunt, Monica Beckwith, Poonam Parhar, & Bengt Rutisson on-line!See this thread for details.
Win a copy of The Java Performance Companion this week in the Performance forum!

# Recursive sum of terms

John Lockheart
Ranch Hand
Posts: 115
I need to use recursion to return a string containing the "sum of terms" of an integer. SumOfTerms(1234) = 1000 + 200 + 30 + 4, SumOfTerms(103) = 100 + 3. I had a rough idea but it involves a loop. Any ideas???

Keith Lynn
Ranch Hand
Posts: 2409
Remember that when using recursion you want to work toward an exit with a known answer. So if you look at what you're doing, where would you exit? That is, at what point would you no longer have to make a recursive call?

John Lockheart
Ranch Hand
Posts: 115
Well i was thinking of converting the integer to a string(sumString). Use the substring() method to get the first number, then add it to a string of zeroes (length determined by sumString.length()). Then i would have to recursively call the method removing the first number(using the substring() method). Does that sound completely stupid or like a good start?

John Lockheart
Ranch Hand
Posts: 115
Here's the code I wrote to fit with the description I posted above. If there's another way I should go about it, please let me know. For now, i need to get rid of the for loop and the zeroes, i.e 1234007 = 1000000 + 200000 + 30000 + 4000 + 000 + 00 + 7. The terms with only zeroes shouldn't be there.

Jeanne Boyarsky
author & internet detective
Marshal
Posts: 34681
367
John,
To get rid of the zeros, you can add another if statement. Right now, you have:
result = String1 + zeroes + UnSum(String2);

You really only want this if String1 is not "0." If is, result should just be UnSum(String2).

Why do you need to get rid of the for loop? It's doing something important. Recursion doesn't mean you can't have a loop. (unless this is for class and you were explicitly told not to use loops.) It means the solution should work towards something smaller. Which yours does.

John Lockheart
Ranch Hand
Posts: 115
thanks, i got it all working now. I replaced the for loop with a recursive method (which is dumb if you ask me). I don't see any other way of doing it unless I have the for loop, or a recursive method which replaces the for loop. What are your thoughts? What code could i insert in place of the for loop inside that method?

pete stein
Bartender
Posts: 1561
You can also get the same result but by doing most of the work w/ integers or longs, not strings:
/Pete

edited to remove all for-loops
[ February 25, 2007: Message edited by: pete stn ]

pete stein
Bartender
Posts: 1561
Or you could do it using string manipulation like you have done, but your code could be greatly simplified. A string manipulation routine could look similar to my Long manipulation routine but not involve any significant math (such as Math.log10()).

I would recommend against method overloading like you have done. Your different UnSum methods are vastly different in what they do and what they return and should be given different names. Also, I'm not so sure about using recursion to add the "0"'s to your string. Better for a simple for loop here.

Again, the key is to simplify.

Good luck!
/Pete
[ February 25, 2007: Message edited by: pete stn ]

John Lockheart
Ranch Hand
Posts: 115
i'm practising for a class. not supposed to use for loops, i don't see why though, obviously if i'm implementing recursion i understand it...anyway, thanks for all the input

Stan James
(instanceof Sidekick)
Ranch Hand
Posts: 8791
This may be redundant by now, but here's a solution in REXX you can use as pseudo code. Some REXX oddities ... // is the modulo or remainder operator, the "procedure" keyword gives us local variables for recursion, trunc truncates REXX's arbitrary precision to integer.

What's fun is you can change this to any base ... try it with input 1234 and base 2 and get this:

For base > 10 you can use the termCount as an index into an array of digits, eg 0123456789ABCDEF for hex.
[ February 25, 2007: Message edited by: Stan James ]

pete stein
Bartender
Posts: 1561
One more thing. I'm not so sure about how your routine handles leading zeros in a substring. Otherwise your routines work fine. You might want to look into having a separate routine that trims leading zeros... it can even be called recursively. Let me know if you're interested in implementing this and if you need any help.
/Pete

John Lockheart
Ranch Hand
Posts: 115
ya your right, it screws it completely up if I use a zero at the beginning of the number. I'm going to try taking a crack at it and i'll keep you updated.

Henry Wong
author
Marshal
Posts: 21216
81
Originally posted by John Lockheart:
i'm practising for a class. not supposed to use for loops, i don't see why though, obviously if i'm implementing recursion i understand it...anyway, thanks for all the input

I actually agree with this. The best way to learn something is to abuse it -- use it for everything, even when there are better ways of doing it. If you get enough practice, you'll start thinking about potential recursive solutions during design, instead of after implementation.

Henry

Nathan Leniz
Ranch Hand
Posts: 132
You could have a main method that that handles how big the number is initially, then recursively break it down with another method fairly easily. Just have an array that holds your base values(other ways to get it but they are a bit heavier), then you can completely ignore bothering with strings.

By using Modulo and a few other tricks, you can effectively break off the numbers one at a time. Then to format them the way you want, just multiply the broken off number by the base you used to separate it. Using it this way and parsing the number in, if the user supplies a number with leading zeros, the zeros will be ignored when Java parses it to an integer.

Hope it helps,

Nathan