当预期递归深度应远小于 999 时，为什么会出现递归错误？

Question

我不明白这段代码是什么让它递归了这么多次。我将不胜感激任何避免这样做的提示。

我预计迭代次数远低于 999。

我尝试在 StackOverflow 和其他地方查找这个问题，但没有一个真正帮助我修复我的代码。我尝试对值列表进行硬编码（这就是您在我给出的版本中看到的）并减少列表中元素的数量：使用单个元素，代码运行得很好，但是上面的任何内容都会引发下面看到的错误.

def main():
    list_to_sort: list[int] = [50, 3, 500, 90, 1, 1]

    def sort(param_to_sort: list[int]) -> list[int]:
        param_len = len(param_to_sort)
        if param_len == 1:
            return param_to_sort
        else:
            half_len: int = param_len // 2
            list1: list[int] = sort(param_to_sort[0:half_len])
            list2: list[int] = sort(param_to_sort[half_len:-1])
            if list1[-1] <= list2[0]:
                return [*list1, *list2]
            else:
                return [*list2, *list1]

    sorted_list: list[int] = sort(list_to_sort)

    print(f"The sorted list is as follows:\n{sorted_list}")


if __name__ == '__main__':
    main()

返回的错误如下：

Traceback (most recent call last):
  File "/home/aengusb/Desktop/PyCharmProjects/recursiveSort/recursiveSort.py", line 31, in <module>
    main()
  File "/home/aengusb/Desktop/PyCharmProjects/recursiveSort/recursiveSort.py", line 22, in main
    sorted_list: list[int] = sort(list_to_sort)
                             ^^^^^^^^^^^^^^^^^^
  File "/home/aengusb/Desktop/PyCharmProjects/recursiveSort/recursiveSort.py", line 15, in sort
    list2: list[int] = sort(param_to_sort[half_len:-1])
                       ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/aengusb/Desktop/PyCharmProjects/recursiveSort/recursiveSort.py", line 15, in sort
    list2: list[int] = sort(param_to_sort[half_len:-1])
                       ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/aengusb/Desktop/PyCharmProjects/recursiveSort/recursiveSort.py", line 14, in sort
    list1: list[int] = sort(param_to_sort[0:half_len])
                       ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/aengusb/Desktop/PyCharmProjects/recursiveSort/recursiveSort.py", line 14, in sort
    list1: list[int] = sort(param_to_sort[0:half_len])
                       ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/aengusb/Desktop/PyCharmProjects/recursiveSort/recursiveSort.py", line 14, in sort
    list1: list[int] = sort(param_to_sort[0:half_len])
                       ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  [Previous line repeated 992 more times]
  File "/home/aengusb/Desktop/PyCharmProjects/recursiveSort/recursiveSort.py", line 13, in sort
    half_len: int = (param_len / 2).__floor__()
                    ^^^^^^^^^^^^^^^^^^^^^^^^^^^
RecursionError: maximum recursion depth exceeded while calling a Python object

行号可能不完全匹配，因为我自己尝试解决这个问题时有一些注释掉的行。对此感到抱歉。

Answer 1

所以只需快速测试一下，如果您将

-1

从

list2: list[int] = sort(param_to_sort[half_len:-1])

然后它修复了错误。

所以：

list2: list[int] = sort(param_to_sort[half_len:])

问题是，对于

list[a:b]

，a 是包含的，b 是排除的，这意味着不包含 b 索引，因此当输入 -1 时，你会继续删除最后一个元素。

但是这不会使排序工作，因此可能会出现一些逻辑错误。

如果我错了，请注意:)