我现在正在CS类中学习数据结构和算法效率，并且已经创建了一种算法来返回与原始列表相反的新项目列表。我试图弄清楚如何使用递归在Python列表中做到这一点，但是解决方案使我难以理解。这是我的代码：
def reverse_list(in_list):
n = len(in_list)
print('List is: ', in_list)
if n <= 2:
in_list[0], in_list[-1] = in_list[-1], in_list[0]
return in_list
else:
first = [in_list[0]]
last = [in_list[-1]]
temp = reverse_list(in_list[1:-1])
in_list = last + temp + first
print('Now list is: ', in_list)
return in_list
if __name__ == '__main__':
list1 = list(range(1, 12))
list2 = reverse_list(list1)
print(list2)
顺便说一句，由于它是n / 2，所以在一般情况下为O（n）吗？
你的n <= 2情况很好。在两种通常意义上，它都是“就地”的。它修改与传入的列表相同的列表，并且除了传入的列表外，它仅使用固定数量的内存。
一般情况是您遇到问题。它使用了大量额外的内存（n / 2个递归级别，每个递归调用级别都包含两个列表，因此所有这些级别的列表都必须同时存在），并且它不会修改传入的列表（而是返回一个新列表）。
我不想为您做太多事情，但是解决此问题的关键是将一个（或两个，如果您愿意）额外参数传递给递归步骤。您的函数的可选参数，或定义包含它们的递归帮助器函数。使用它来指示列表中的哪个区域就地反转。
正如评论中提到的那样，CPython没有尾递归优化。这意味着，不会使用像这样的调用递归的算法真正实现“原地”，因为它将使用线性数量的堆栈。但是从“修改原始列表而不是返回新列表”的意义上讲，“就地”无疑是可行的。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句