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-27 15:36:14Z

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.

Aryerez · Accepted Answer · 2019-10-27 15:25:08Z

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, 2019 at 15:25

Aryerez

3,5032 gold badges12 silver badges18 bronze badges

Comments

Emily · Accepted Answer · 2019-10-27 15:23:48Z

0

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, [])

answered Oct 27, 2019 at 15:23

Emily

1,0961 gold badge12 silver badges21 bronze badges

Comments

Pei Li · Accepted Answer · 2019-10-27 15:18:01Z

-1

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

It should work.

answered Oct 27, 2019 at 15:18

Pei Li

3203 silver badges17 bronze badges

1 Comment

Aryerez Over a year ago

"the answer has to use recursion, otherwise it won't bother me"

Collectives™ on Stack Overflow

python build a list recursively

4 Answers 4

Comments

Comments

Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related