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

Question

我想要一个函数，它将返回给出的列表的反向 - 使用递归。我怎么能这样做？

Answer 1

将列表的第一个元素附加到反向子列表：

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

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

我知道这不是一个有用的答案（虽然这个问题已经得到解答），但在任何实际代码中，请不要这样做。 Python无法优化尾调用，函数调用速度慢并且具有固定的递归深度，因此至少有3个理由可以反复进行迭代。

Answer 4

诀窍是在递归之后加入：

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

Answer 5

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]

Answer 6

使用Divide＆amp;征服战略。 D＆amp; C算法是递归算法。 要使用D＆amp; 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]

来源：Grokking算法

Answer 7

这个反转到位。 （当然迭代版本会更好，但它必须是递归的，不是吗？）

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 8

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

Answer 9

看起来更简单：

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

Answer 10

取第一个元素，递归地反转列表的其余部分，并将第一个元素追加到列表的末尾。

Answer 11

def reverseList(listName,newList = None):
if newList == None:
    newList = []
if len(listName)>0:
    newList.append((listName.pop()))
    return reverseList(listName, newList)
else:
    return newList

print reverseList（[1,2,3,4]） [4,3,2,1]

Answer 12

使用Mutable默认参数和递归：

def hello(x,d=[]):
    d.append(x[-1])
    if len(x)<=1:
        s="".join(d)
        print(s)

    else:
        return hello(x[:-1])

hello("word")

其他信息

x[-1]    # last item in the array
x[-2:]   # last two items in the array
x[:-2]   # everything except the last two items

递归部分是 hello（x [： - 1]），其中 x [： - 1]

之后再次调用hello函数

Answer 13

为什么不：

a = [1,2,3,4,5]
a = [a[i] for i in xrange(len(a)-1, -1, -1)] # now a is reversed!

Answer 14

这也将反转嵌套列表！

A = [1, 2, [31, 32], 4, [51, [521, [12, 25, [4, 78, 45], 456, [444, 111]],522], 53], 6]

def reverseList(L):

    # Empty list
    if len(L) == 0:
        return

    # List with one element
    if len(L) == 1:

        # Check if that's a list
        if isinstance(L[0], list):
            return [reverseList(L[0])]
        else:
            return L

    # List has more elements
    else:
        # Get the reversed version of first list as well as the first element
        return reverseList(L[1:]) + reverseList(L[:1])

print A
print reverseList(A)

Padmal的博客