CODEWITHSUNDEEP
pythonrecursion
whytheq
whytheq

Reputation: 35577

From iterative to recursive - reordering a list

I have a list:

L = [0,'a','b','c']

If I run the following:

sortedList = []
while len(L) > 0:
    item = L.pop()
    sortedList.append(item)
print(sortedList)

Output: 

['c', 'b', 'a', 0]

As a simple exercise in trying to understand recursion I'd like to put the above in a recursive function. I have two attempts - how do I fix one, or both of them - or is there a recursive solution?

1.

def extract(Seq):
    if Seq == [0]:
        return s.append(0)
    else:
        extract(Seq[:len(Seq)-1])

        if not s: s = []
        x=Seq.pop()
        return s.append(x)

M = [0,'a','b','c']
print(extract(M))

2.

def extract2(Seq):
    s=[]
    if Seq:
        return s.append(Seq.pop())
        extract2(Seq)

N = [0,'a','b','c']
print(extract(N))

Upvotes: 1

Views: 201

Answers (1)

Simeon Visser
Simeon Visser

Reputation: 122456

A recursive solution could be:

def extract3(seq):
    if not seq:
        return seq
    return [seq.pop()] + extract3(seq)

However this modifies the input list which may not be what you want. So it's better to slice the input list as needed:

def extract4(seq):
    if not seq:
        return seq
    return [seq[-1]] + extract4(seq[:-1])

where seq[-1] means "take the last element of seq" and seq[:-1] means "take all elements of seq except the last one". The function extract4 builds a new list by taking the elements as needed and without modifying the given sequence seq.

You can also use an accumulator which would be called with extract5(N, []):

def extract5(seq, acc):
    if not seq:
        return acc
    acc.append(seq[-1])
    return extract5(seq[:-1], acc)

Upvotes: 3

Related Questions