# Parse a string of digits into an integer using recursion without Java library

William Koch
Ranch Hand
Posts: 76
I know that the ASCII characters of the digits 0-9 can be converted to integers by subtracting 48 from their decimal equivalent values (ex. char = 9 is dec = 57, therefore int = 57 - 48 = 9)

I know the base case would be if the length of the string is 1 then just return the integer just like the example I gave above. What I am having trouble with is strings of longer lengths or the recursive case.

For example str = 123, I know that the ones place is 3*1, the tens place is 2*10, and the hundreds place is 1*100 and the sum of these are the integer 123. How do I implement this recursively so it sums them up. Can anyone provide the recursive case and what the return statement should look like.

fred rosenberger
lowercase baba
Bartender
Posts: 12228
36
Step 1: forget about java
Step 2: write out the steps, in English, how you would do it if all you had was a pencil and a stack of papers.
Step 3: revise the steps, making them simpler and simpler, until they would make sense to a child.

You should not even consider writing a single line of Java code until you have done the above.

Further, you should define what you mean by "without java library methods". Almost anything you write is going to use SOMETHING...even if it is just System.out.println.

William Koch
Ranch Hand
Posts: 76
Fred,

I have not written any Java yet. And what I guess I meant was that I do not want to use a parser that is built into Java. I have written out steps but there is one I get tripped up on:

1) If the string is a single digit between 0 and 9 (we assume no empty strings) then convert it to the ascii decimal equivalent and subtract 48 and return that number
2) If the string is of a length longer than 1 then we need to convert each digit the same way we did in step one but we need to mulitply them by the same number as the place they are in (this is where i get tripped up)(ones-> multiply by 1, tens -> multiply by ten etc) and sum them up. How do I take into account what I need to multiply (1,10,100,1000...etc)?

Henry Wong
author
Marshal
Posts: 21724
85
William Koch wrote:I have not written any Java yet. And what I guess I meant was that I do not want to use a parser that is built into Java. I have written out steps but there is one I get tripped up on:

If you have not coded any Java yet, why would you want to do it recursively? Is there a reason why you can't use a loop?

Henry

William Koch
Ranch Hand
Posts: 76
because it is a homework assignment and my instructor is making us

Henry Wong
author
Marshal
Posts: 21724
85
William Koch wrote:because it is a homework assignment and my instructor is making us

Recursion isn't a beginners topic. Why is your instructor making you use recursion, when you haven't even coded Java yet?

Henry

fred rosenberger
lowercase baba
Bartender
Posts: 12228
36
William Koch wrote:1) If the string is a single digit between 0 and 9 (we assume no empty strings) then convert it to the ascii decimal equivalent and subtract 48 and return that number
2) If the string is of a length longer than 1 then we need to convert each digit the same way we did in step one but we need to mulitply them by the same number as the place they are in (this is where i get tripped up)(ones-> multiply by 1, tens -> multiply by ten etc) and sum them up. How do I take into account what I need to multiply (1,10,100,1000...etc)?

Well, I'd say your #1 needs a lot more revision. where did this string come from? How do you tell if it is a single anything...let alone a digit?

You're still thinking in terms of java. forget about ascii and subtracting 48.

pretend someone writes down on a piece of paper

"one eight seven nine".

How would you, personally, convert that? I'd start with something like

There is no concept of java here. there is no such thing as ascii here. Just the logic involved with what needs to be done, and not how do do it.

I'm not even 100% sure my directions are correct. I'd run a few test cases, and see how it falls out. If it does work, I may start coding it a piece at a time - i.e. first just printing out the tokens. Then printing out the conversion. then adding them up.

I'm not sure my algorithm will work for recursion. I would probably start at the other end...Recursion basically says "well, if I can figure out how to do what i need for a part of the problem, I can then just add this little piece to complete it."

For example, if I have the string "12345", i know that if I can figure out how to convert "1234" to an int, then I can multiply that by 10 and add five to get the final answer. To me, the recursive solution starts at the END of the string, not the beginning.

Jesper de Jong
Java Cowboy
Saloon Keeper
Posts: 15564
46
fred rosenberger wrote:I'm not sure my algorithm will work for recursion. I would probably start at the other end...Recursion basically says "well, if I can figure out how to do what i need for a part of the problem, I can then just add this little piece to complete it.

Yes, it will. Anything with a loop can be implemented with recursion, and vice versa.

Henry Wong
author
Marshal
Posts: 21724
85
Jesper de Jong wrote:
fred rosenberger wrote:I'm not sure my algorithm will work for recursion. I would probably start at the other end...Recursion basically says "well, if I can figure out how to do what i need for a part of the problem, I can then just add this little piece to complete it.

Yes, it will. Anything with a loop can be implemented with recursion, and vice versa.

I believe it goes by the name of "tail recursion" -- basically, the end of the method is a check and setup for the next "iteration" via a recursive method call. Now, as for the "vice versa" part -- I am not sure if I agree with it. Yes, you can get rid of recursion by using some sort of stack based data structure, but I seen some really complex recursive algorithms. The replacement for these recursive algorithms may contains loops, but they will likely contain much more too.

Henry

William Koch
Ranch Hand
Posts: 76
This topic has been resolved:

I just needed to think about how to do the powers of 10. Here is my fully functioning solution in your favorite language Ada2012:

function Parse(S: String) return Integer is
L : Integer := S'length;
X : Integer;
begin
if L = 1 then
return Character'Pos(S(S'First)) - 48;
else
X := 10**(L-1) * (Character'Pos(S(S'First)) - 48);
return X + Parse(S(S'First+1..S'Last));
end if;
end Parse;

Henry Wong
author
Marshal
Posts: 21724
85
William Koch wrote:I just needed to think about how to do the powers of 10. Here is my fully functioning solution in your favorite language Ada2012:

If it helps, Java has the Math.pow() method, which should provide the functionality of Ada's "**" operator.

Henry