如何在Python中用递归反转列表？

Question

我想写一个函数，它可以把给定的列表反转过来，也就是把最后一个元素放到最前面，前面的元素依次往后移。这个函数要用递归的方法来实现。请问我该怎么做呢？

Answer 1

我知道这不是一个很有帮助的回答（虽然这个问题已经有人回答过了），但在任何实际的代码中，请不要这样做。Python 不能优化尾调用，函数调用速度慢，而且递归深度是固定的，所以至少有三个理由让你选择用迭代的方式来实现。

Answer 2

稍微详细一点：

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

---

这变成了：

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

接着变成：

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

这和另一个答案是一样的。

---

尾递归 / CPS 风格（不过 Python 本身并没有优化这个）：

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 3

将列表的第一个元素添加到一个反转的子列表中：

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