How do I reverse a list using recursion in Python?

Question

I want to have a function that will return the reverse of a list that it is given -- using recursion. How can I do that?

Answer 1

Take the first element, reverse the rest of the list recursively, and append the first element at the end of the list.

Answer 2

The trick is to join after recursing:

def backwards(l):
  if not l:
    return
  x, y = l[0], l[1:]
  return backwards(y) + [x]

Answer 3

Append the first element of the list to a reversed sublist:

mylist = [1, 2, 3, 4, 5]
backwards = lambda l: (backwards (l[1:]) + l[:1] if l else []) 
print backwards (mylist)

Answer 4

A bit more explicit:

def rev(l):
    if len(l) == 0: return []
    return [l[-1]] + rev(l[:-1])

---

This turns into:

def rev(l):
    if not l: return []
    return [l[-1]] + rev(l[:-1])

Which turns into:

def rev(l):
    return [l[-1]] + rev(l[:-1]) if l else []

Which is the same as another answer.

---

Tail recursive / CPS style (which python doesn't optimize for anyway):

def rev(l, k):
    if len(l) == 0: return k([])
    def b(res):
        return k([l[-1]] + res)
    return rev(l[:-1],b)


>>> rev([1, 2, 3, 4, 5], lambda x: x)
[5, 4, 3, 2, 1]

Answer 5

I know it's not a helpful answer (though this question has been already answered), but in any real code, please don't do that. Python cannot optimize tail-calls, has slow function calls and has a fixed recursion depth, so there are at least 3 reasons why to do it iteratively instead.

Answer 6

This one reverses in place. (Of course an iterative version would be better, but it has to be recursive, hasn't it?)

def reverse(l, first=0, last=-1):
    if first >= len(l)/2: return
    l[first], l[last] = l[last], l[first]
    reverse(l, first+1, last-1)

mylist = [1,2,3,4,5]
print mylist
reverse(mylist)
print mylist

Answer 7

def reverse(q): if len(q) != 0: temp = q.pop(0) reverse(q) q.append(temp) return q