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

Question

我想要一个函数，它可以使用递归返回给定列表的反转结果。我该如何实现？

- Alistair

Answer 1

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

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

- John Millikin

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]

- Claudiu

Answer 3

我知道这不是一个有用的答案（尽管这个问题已经得到了回答），但在任何真正的代码中，请不要那样做。Python无法优化尾调用，函数调用速度慢，并且具有固定的递归深度，因此至少有三个原因要改为迭代实现。

- J S

---

请勿就实际代码而言反对您的观点。在这种情况下，Python不会优化尾调用并不重要，因为列表反转没有使用CPS的尾递归。 - ddaa

Answer 4

技巧是在递归之后合并：

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

注：该代码段是一个Python函数，用于将列表中的元素顺序颠倒。

- Ignacio Vazquez-Abrams

Answer 5

使用分治策略。D&C算法是递归算法。 使用D&C解决这个问题，需要两个步骤：

1. 找出基本情况。这应该是最简单的情况。
2. 将问题分解或减少，直到它变成基本情况。

步骤1：找出基本情况。你能得到什么最简单的列表？如果你得到一个有0或1个元素的列表，那就很容易求和了。

if len(l) == 0:  #base case
    return []

步骤2：每次递归调用时，您需要更接近一个空列表。

recursive(l)    #recursion case

例如

l = [1,2,4,6]
def recursive(l):
    if len(l) == 0:
        return []  # base case
    else:
        return [l.pop()] + recursive(l)  # recusrive case


print recursive(l)

>[6,4,2,1]

来源：算法图解

- Aran

Answer 6

这个函数在原地反转。当然，迭代版本会更好，但必须使用递归，不是吗？

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

- Federico Ramponi

Answer 7

def revList(alist):
    if len(alist) == 1:       
        return alist #base case
    else:
        return revList(alist[1:]) + [alist[0]]

print revList([1,2,3,4])
#prints [4,3,2,1]

- Francis Phiri

Answer 8

一个递归函数来反转列表。

def reverseList(lst):
    #your code here
    if not lst:
        return []
    return [lst[-1]] + reverseList(lst[:-1])


print(reverseList([1, 2, 3, 4, 5]))

- Kenneth Chang

Answer 9

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

- steve

Answer 10

看起来更简单：

    def reverse (n):
        if not n: return []
        return [n.pop()]+reverse(n)

- Giwi