Recursion extracting digits

Question

I need to write a a recursive function getdigits(n) that returns the list of digits in the positive integer n.

Example getdigits(124) => [1,2,4]

So far what I've got is:

def getdigits(n):
    if n<10:
        return [n]
    else:
        return [getdigits(n/10)]+[n%10]

But for 124 instead of [1, 2, 4] I get [[[1], 2], 4]

Working that in in my head it goes like:

getdigits(124) = [getdigits(12)] + [4]
getdigits(12) = [getdigits(1)] + [2]
get digits(1) = [1]

Therefore getdigits(124) = [1] + [2] + [4] = [1, 2, 4]

I figure there's something wrong in the second part of it as I can't see anything wrong with the condition, any suggestions without giving the entire solution away?

Does it have to be recursion? The simple solution would simply be `return list(str(n))` — Glider, May 13 '12 at 12:47
So, then, why don't you return just 'getdigits(n/10) + [n%10]' instead of '[getdigits(n/10)] + [n%10]'? — user1227804, May 13 '12 at 12:51
possible duplicate of [How to rewrite this function as a recursive function?](http://stackoverflow.com/questions/10568848/how-to-rewrite-this-function-as-a-recursive-function) — Óscar López, May 13 '12 at 13:25
Added the homework tab - the only reason you would *need* a function to be recursive is homework. It's fine to post it on here, but tag it as such. — Gareth Latty, May 13 '12 at 13:38
None of the functions posted so far is able to convert a 1000-digit long number. Can anyone write `getdigits` so that 1) it's recursive, 2) it doesn't exhaust the stack? — georg, May 13 '12 at 14:28
@thg435: those requirements are incompatible in python. If you are using recursion, then you are consuming stack space. It will run out. — Ned Batchelder, May 13 '12 at 15:25
@NedBatchelder: still, I think it's possible. You're going to need a decorator though. — georg, May 13 '12 at 15:32
@thg435: you think it's possible to write a recursive function in Python without consuming stack space? I don't see how, and I don't see what a decorator would do for you. — Ned Batchelder, May 13 '12 at 15:39
@Ned: we can make it tail-recursive, and then apply a decorator that converts tail recursion to iteration. — georg, May 13 '12 at 15:48
@thg435: I don't think a decorator will be able to do that, they typically don't deal with the internals of the functions they wrap. But if you manage it, lots of people would like to see it! — Ned Batchelder, May 13 '12 at 15:54
@Ned: someone already did that: http://code.activestate.com/recipes/496691-new-tail-recursion-decorator — georg, May 13 '12 at 16:03
@Ned: yes, this is a rather ugly hack, and unfortunately, [TRO/TCO is not going to be added to Python](http://neopythonic.blogspot.de/2009/04/final-words-on-tail-calls.html). — georg, May 13 '12 at 17:21

score 2 · Answer 1 · answered May 13 '12 at 12:44

2

getDigits return a list, so why do you wrap the list into another one (last line)?

answered May 13 '12 at 12:44

Vito De Tullio

2,332
3
33
52

Ahhh I didn't realise that until now, can't believe how slow I am. – Markaj May 13 '12 at 12:59

score 1 · Answer 2 · answered May 13 '12 at 12:47

Your problem is either that you're returning [n] instead of n or using [getDigits(n / 10)] instead of getDigits(n / 10).

For instance, with your example:

getDigits(124) = [getDigits(12)] + [4] = [getDigits(12), 4]
getDigits(12) = [getDigits(1)] + [2] = [getDigits(1), 2]
getDigits(1) = [1]

Therefore it follows:

getDigits(12) = [[1], 2]
getDigits(124) = [[[1], 2], 4]

score 1 · Answer 3 · edited May 25 '22 at 13:09

1

The same question has been answered before, see the link for more details.

def getdigits(n):
    if n < 10:
        return [n]
    return getdigits(n // 10) + [n % 10]

getdigits(123)
> [1, 2, 3]

The above will work for an integer n >= 0, notice that you don't have to wrap the result of getdigits(n // 10) inside another list.

edited May 25 '22 at 13:09

Aadi Shah

99
1
8

answered May 13 '12 at 13:26

Óscar López

232,561
37
312
386

Does python optimise recursive functions like this to avoid overloading the stack? – Will Mar 02 '14 at 12:47
@Will no, Python doesn't [optimize tail recursion](http://stackoverflow.com/a/13592002/201359). – Óscar López Mar 02 '14 at 13:20

score 0 · Answer 4 · answered May 13 '12 at 13:05

0

Your question sounds like homework (recursive requirement), but this could be done with a list comprehension

>>> def getdigits(n):
...    return [int(y) for y in str(n)]
... 
>>> getdigits(12345)
[1, 2, 3, 4, 5]

answered May 13 '12 at 13:05

Burhan Khalid

169,990
18
245
284

Ashwini Chaudhary · Answer 5 · 2012-07-20T07:43:25.113

0

You can simply use this:

>>> num=124
>>>list(map(int,str(num)))
[1,2,4]

edited Jul 20 '12 at 07:43

answered May 13 '12 at 13:23

Ashwini Chaudhary

244,495
58
464
504

With which version of Python does this work? I can't get this to work on 2.7.3. – octopusgrabbus Jul 17 '12 at 19:28
@octopusgrabbus edited my solution, made a silly mistake. :)\ – Ashwini Chaudhary Jul 20 '12 at 07:44

score 0 · Answer 6 · edited Jan 29 '13 at 09:24

0

Using Lambda

(lambda x: [int(a) for a in str(y)])(number)

edited Jan 29 '13 at 09:24

fthiella

48,073
15
90
106

answered Jan 29 '13 at 09:06

Mirage

30,868
62
166
261

score 0 · Answer 7 · edited Oct 18 '19 at 16:09

0

def getdigits(n):
    if n<10:
        return [n]
    else:
        return getdigits(n//10)+[n%10]

your answer is in float. You need to use floor division to make it [1] instead of 1.2

edited Oct 18 '19 at 16:09

M_S_N

2,764
1
17
38

answered Oct 18 '19 at 15:29

Ngoc

1

Recursion extracting digits

7 Answers7

Linked