python build a list recursively

Question

Let's say I have a string

S = "qwertyu"

And I want to build a list using recursion so the list looks like

L = [u, y, t, r, e, w, q]

I tried to write code like this:

 def rec (S):
    if len(S) > 0:
        return [S[-1]].append(rec(S[0:-1]))

Ideally I want to append the last element of a shrinking string until it reaches 0 but all I got as an output is None

I know I'm not doing it right, and I have absolutely no idea what to return when the length of S reaches 0, please show me how I can make this work

(sorry the answer has to use recursion, otherwise it won't bother me)

Thank you very much!!!

gstukelj · Accepted Answer · 2019-10-27T15:36:14.620

There are many simpler ways than using recursion, but here's one recursive way to do it:

def rec (S):
    if not S:
        return []
    else:
        temp = list(S[-1])
        temp.extend(rec(S[:-1]))
        return temp

EDIT:

Notice that the base case ensures that function also works with an empty string. I had to use temp, because you cannot return list(S[-1]).extend(rec(S[:-1])) due to it being a NoneType (it's a method call rather than an object). For the same reason you cannot assign to a variable (hence the two separate lines with temp). A workaround would be to use + to concatenate the two lists, like suggested in Aryerez's answer (however, I'd suggest against his advice to try to impress people with convoluted one liners):

def rec (S):
    if not S:
        return []
    else:
        return list(S[-1]) + rec(S[:-1])

In fact using + could be more efficient (although the improvement would most likely be negligible), see answers to this SO question for more details.

score 2 · Answer 2 · answered Oct 27 '19 at 15:25

2

This is the simplest solution:

def rec(S):
    if len(S) == 1:
        return S
    return S[-1] + rec(S[:-1])

Or in one-line, if you really want to impress someone :)

def rec(S):
    return S if len(S) == 1 else S[-1] + rec(S[:-1])

answered Oct 27 '19 at 15:25

Aryerez

3,417
2
9
17

score 0 · Answer 3 · answered Oct 27 '19 at 15:23

Since append mutates the list, this is a bit difficult to express recursively. One way you could do this is by using a separate inner function that passes on the current L to the next recursive call.

def rec(S):
    def go(S, L):
        if len(S) > 0:
            L.append(S[-1])
            return go(S[0:-1], L)
        else:
            return L
    return go(S, [])

score -1 · Answer 4 · answered Oct 27 '19 at 15:18

-1

    L = [i for i in S[::-1]]

It should work.

answered Oct 27 '19 at 15:18

Pei Li

302
3
15

"the answer *has to use recursion*, otherwise it won't bother me" – Aryerez Oct 27 '19 at 15:27

python build a list recursively

4 Answers4