如何在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

诀窍是在递归后加入：

def 向后(l):
  如果不是我：
    返回
  x, y = l[0], l[1:]
  向后返回(y) + [x]

Answer 4

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

Answer 5

使用分而治之的策略。D&C 算法是递归算法。\n要使用 D&C 解决此问题，有两个步骤：

\n\n

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

\n\n

第 1 步：找出基本情况。您能得到的最简单的列表是什么\xe2\x80\x99？如果你得到一个包含 0 或 1 个元素的列表，那么 \xe2\x80\x99s 很容易总结。

\n\n

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

\n\n

第 2 步：每次递归调用都需要接近空列表\n

\n\n

recursive(l)    #recursion case\n

\n\n

例如

\n\n

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

\n\n

资料来源：Grokking 算法

\n