Python - String of Digits to Integer using Recursion?

Question

Say I have a string = '123' but I want to convert it into 123 without using the int() function. How would I go upon doing this using recursion? The idea I have so far is to put the string into an array as such ['1','2','3'] and then convert them based on ASCII representations.

for i in string:

myArr.append (ord(i) - ord('0'))

So now I'd have a list looking like [1,2,3]. What should I do next to recursively get 123? I have an idea of using the place values and add them together (ie. 100 + 20 + 3 = 123), but I don't know how to do this. Any ideas would be helpful !

Óscar López · Accepted Answer · 2014-03-29 18:09:09Z

2

I guess this is an academic exercise, because it's a rather contrived thing to ask. Here's how, assuming that s represents an integer number greater than or equal to zero:

def strToInt(s, acc):
    if not s:
        return acc
    return strToInt(s[1:], 10 * acc + ord(s[0]) - 48)

Or even shorter:

def strToInt(s, acc):
    return strToInt(s[1:], 10 * acc + ord(s[0]) - 48) if s else acc

The trick is to accumulate the result of the conversion in an extra parameter, this has the nice side effect of yielding a tail-recursive solution (not that it matters much in Python, but still…). Also notice how we use ord() to get the numeric value of a character representing a digit, and by simply subtracting 48 we get to the actual digit's value. Test it, it works as expected:

strToInt('123', 0) # the accumulator always starts in zero
=> 123

edited Mar 29, 2014 at 18:09

answered Mar 29, 2014 at 18:02

Óscar López

237k38 gold badges321 silver badges391 bronze badges

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

2 Comments

user3128178 Over a year ago

An exercise given to me to practice recursion! I thought this was a ridiculous exercise when I can just use int() but I guess it's good practice to really understand recursion

Selcuk Over a year ago

The ridiculous part is not that you can use int, but that it can be solved with a for loop.

JackGibbs · Accepted Answer · 2014-03-29 18:05:27Z

1

This wouldn't be recursive (I don't think you understand what that means), but:

for char in string:
    array.append(ord(char) - ord('0'))

array.reverse()

num = 0
for index, val in enumerate(array):
        num += val * (10 ** index)

EDIT: Ah, I see this is for an exercise. Yeah, it's a ridiculous problem to solve via recursion, but one of the other answers does it.

answered Mar 29, 2014 at 18:05

JackGibbs

2302 silver badges9 bronze badges

Comments

ooga · Accepted Answer · 2014-03-29 19:33:15Z

1

Another possibility:

def strToInt(s):
  if s:
    return (ord(s[-1]) - ord('0')) + 10 * strToInt(s[:-1])
  else:
    return 0

edited Mar 29, 2014 at 19:33

answered Mar 29, 2014 at 18:23

ooga

15.6k2 gold badges23 silver badges23 bronze badges

1 Comment

Óscar López Over a year ago

Recursive call should be strToInt

M. K. Hunter · Accepted Answer · 2014-03-29 18:03:40Z

0

The first thing that comes to mind is the famous C method atoi(). Python had a similar method, also called atoi(), but it was deprecated, with the instruction to use int().

Therefore, despite your comment, I would recommend using int(). Python documentation encourages you to use it, so do so without fear.

int() documentation for Python 2.7

int() documentation for Python 3.3

answered Mar 29, 2014 at 18:03

M. K. Hunter

1,8683 gold badges22 silver badges31 bronze badges

Collectives™ on Stack Overflow

Python - String of Digits to Integer using Recursion?

4 Answers 4

2 Comments

Comments

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

2 Comments

Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related