2

当我编写递归函数来就地反转列表时，我遇到了以下问题。我可以更改输入参数。

def reverse_string(s):
    if len(s) <= 1:
        return
    else:
        s[0], s[-1] = s[-1], s[0]
        reverse_string(s[1:-1])


s = ['A','B','C','D','E','F']
reverse_string(s)
print(s)

输出是

['F', 'B', 'C', 'D', 'E', 'A']

看起来我在递归中所做的更改在递归调用返回后被回滚。我不明白为什么。有人可以帮忙吗？

4

4 回答 4

2

切片列表会创建一个新列表，因此修改切片列表对原始列表没有影响。相反，您可以使函数接受一个偏移量作为第二个参数，以便在原始列表上根据列表两端的偏移量交换项目：

def reverse_string(s, offset=0):
    if len(s) > offset * 2:
        s[offset], s[-offset - 1] = s[-offset - 1], s[offset]
        reverse_string(s, offset + 1)

以便：

s = ['A', 'B', 'C', 'D', 'E', 'F']
reverse_string(s)
print(s)

输出：

['F', 'E', 'D', 'C', 'B', 'A']
于 2019-11-19T23:30:20.013 回答
1

要了解您当前的代码是如何不工作的，这里有一个使用相同算法的版本。它只是添加了一些额外的步骤，以便您在每次调用时适当地处理从主列表中切出的列表：

def reverse_string(s):
    if len(s) <= 1:
        return
    else:
        s[0], s[-1] = s[-1], s[0]
        slice = s[1:-1]       # slicing a list creates a new, independent list object
        reverse_string(slice) # this call modifies the new list in place, leaving s unchanged
        s[1:-1] = slice       # so we have to assign the modified slice back to s ourselves

请注意，虽然这确实有效，但效率非常低，因为切片和切片分配都需要在每次递归调用时复制列表的大部分。其他答案提供了更有效的解决方案，包括始终修改同一个列表，仅使用特定索引而不是始终交换s[0]and s[-1]。

还值得注意的是，虽然这是对list对象进行切片时的行为方式，但 Python 中的其他对象的行为方式可能有所不同。数组中的切片numpy是另一个数组，但数组是底层数据的浅“视图”。就地修改数组的切片通常也会修改数组中的数据。这可能是好是坏，取决于您是否期望它！

于 2019-11-19T23:52:13.897 回答
0

希望这只是一个递归练习，这是一个相当低效的python内置通过使用负增量反转列表的实现

s = ['A','B','C','D','E','F']
print(s[::-1])

对于您的递归，请参阅 blhsing 的答案。

于 2019-11-19T23:42:11.143 回答
-1

由于s[::-1]是反转的建议答案，我们也需要解释，reverse因为它是反转切片的最快方法（就地）

s = ['A','B','C','D','E','F']
s.reverse()
print(s)
# ['F', 'E', 'D', 'C', 'B', 'A']
于 2019-11-20T08:51:35.287 回答