How do I reverse a list using recursion in Python?
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)
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]
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.