Почему я получаю ошибку рекурсии, если глубина ожидаемой рекурсии должна быть меньше 999?
Что заставляет этот код повторяться так много раз? Я ожидал, что количество итераций будет намного меньше, чем 999.
Я попробовал жестко запрограммировать список значений (это то, что вы видите в приведенной мной версии) и уменьшить количество элементов в списке: с одним элементом код работает отлично, но все, что выше, вызывает ошибку, показанную ниже. .
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
Номера строк могут не совпадать в точности, потому что у меня есть несколько закомментированных строк, когда я пытался разобраться в этой проблеме самостоятельно.
L=[0,1,2,3,4]; i=2 ⇒ L[0:i] = [0,1] и L[i:-1] = [2,3], когда вы явно ожидали, что L[i:-1] будет [2,3,4]. 4 исключено из вашего алгоритма. Ошибка, которую вы бы легко заметили (вы бы заметили недостающую 4 в результате), если бы не бесконечная рекурсия. И бесконечная рекурсия вызвана побочным эффектом этой ошибки: у вас есть пустой список в процессе.
Если L=[1,2], то len(L)=2, поэтому halfLen=1, поэтому L[0:halfLen]=[1] и L[halfLen:-1] есть []. Тогда рекурсивный вызов сортировки приводит к sort([]) вызову дважды sort([])... отсюда и бесконечная рекурсия.
И да, я только что понял, что под «другой ошибкой» вы имели в виду ту, которая «не сортируется». То, что вы реализовали здесь, называется сортировкой слиянием разделов: вы делите список пополам, рекурсивно сортируете каждую половину и объединяете две половины вместе. За исключением того, что на самом деле вы их не объединяете, а объединяете (в том или ином порядке, но все равно просто объединяете).
Спасибо! Я совершенно забыл о том, что конечный индекс является эксклюзивным. Однако я не понимаю, почему это возвращает пустые списки. Кроме того, я намеренно не искал, существовала ли уже моя идея алгоритма сортировки (хотя я все время осознавал, что это слишком простая идея, чтобы не существовать), потому что это практический сценарий, и я хотел опробовать его на своем собственный в первую очередь.
-1 означает «последний элемент». Итак, если L имеет n элементов, -1 и n-1 являются синонимами. Например, для 5 элементов L=[10,20,30,40,50] индекс -1 такой же, как индекс 4: L[-1]=L[4]=50. Если L имеет только 2 элемента, то индекс -1 и индекс 1 являются синонимами. Итак, если L=[10,20], то L[-1] — это L[1], значит L[-1]=L[1]=20. L[0:1] — это [10], а L[1:-1] — то же самое, что и L[1:1], которое пусто.
«У меня есть несколько закомментированных строк, когда я пытался сам разобраться в этой проблеме». - Прежде чем задавать дополнительные вопросы, прочтите Как отлаживать небольшие программы и убедитесь, что вы понимаете, как на самом деле работает «попытка разобраться». Замена очевидного кода, такого как param_len // 2, на более непонятные эквиваленты вам ни о чем не скажет. Попытка выяснить, каковы значения переменных (например, param_len в данном случае) в различных точках программы, даст результат. Также рассмотрите возможность использования отладчика.
Ссылки: Что такое отладчик и как он может помочь мне диагностировать проблемы? ; Как выполнить код Python для устранения проблем? ; pdb — Отладчик Python (официальная документация).
Пожалуйста, вносите ясность с помощью правок, а не комментариев, а также удаляйте и отмечайте устаревшие комментарии.
Для вопросов по отладке требуется минимальный воспроизводимый пример — вырезать, вставлять и запускать код, включая инициализацию; желаемый и фактический результат (включая дословные сообщения об ошибках); теги и версии; четкая спецификация и объяснение. Для отладки, которая включает в себя наименьшее количество кода, которое вы можете предоставить, это код, который вы показываете, в порядке, расширенный кодом, который вы показываете, что это не в порядке. Как задать вопрос Справочный центр Когда вы получаете результат, которого не ожидали, найдите первую точку выполнения, где значение переменной или подвыражения не соответствует вашим ожиданиям, и скажите, что вы ожидали и почему, обосновано документально. (Основы отладки.)
Ответы 2
Просто с помощью быстрого теста: если вы удалите -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, вы продолжаете отбрасывать последний элемент.
Однако это не позволяет сортировке работать, поэтому могут возникнуть некоторые логические ошибки.
Проблема в том, что вы сталкиваетесь с бесконечной рекурсией.
Это вызвано param_to_sort[half_len:-1], который исключает значение -1, то есть последнее значение. Это вызовет бесконечную рекурсию, когда размер param_to_sort равен 2, что делает этот фрагмент пустым, и у вас нет обработки базового случая для пустых списков.
Чтобы разрезать начиная с half_len, выполните param_to_sort[half_len:]: теперь вы не пропустите последнее значение в списке.
В связи с этим: вы должны предусмотреть случай, когда список пуст. Вы можете использовать уже реализованный базовый вариант и выполнить его, когда размер списка равен 0 вместо 1.
Другая проблема заключается в том, что на этапе слияния вы просто предусматриваете два возможных варианта: либо весь list1 должен идти раньше всего list2, либо наоборот. Но возможностей больше. Например, если list1 — это [2, 4], а list2 — это [1, 3], вам не нужны ни [*list1, *list2], ни [*list2, *list1]. Вам понадобится «сплести» значения из этих списков, что часто требует, чтобы вы сделали более одного сравнения и шаг за шагом выбрали значение из любого списка. Существует несколько способов реализации этого этапа слияния.
Вот как вы можете заставить это работать:
def sort(param_to_sort: list[int]) -> list[int]:
param_len = len(param_to_sort)
if param_len <= 1: # Also when list is empty
return param_to_sort
else:
half_len: int = param_len // 2
list1: list[int] = sort(param_to_sort[:half_len])
list2: list[int] = sort(param_to_sort[half_len:]) # Fix
# Merge step needs to check how to "weave" the two lists
merged: list[int] = []
while list1 and list2:
source: list[int] = list1 if list1[-1] > list2[-1] else list2
merged.append(source.pop()) # add greatest
return list1 + list2 + merged[::-1]
А что, если len равен 0? Конечно: вы можете подумать, что этого никогда не произойдет. Но если бы вы все равно обработали этот случай, у вас был бы почти рабочий алгоритм, и реальная ошибка, которую вы допустили, была бы очевидна :D. По крайней мере, ошибка, вызывающая ошибку рекурсии. Спойлер:
L[i:-1]это не то, что вы думаете. Имхо есть еще одна ошибка, но она не связана с вопросом. Только имя вашей функции подразумевает, что вы ожидаете, что она будет сортировать список. И сортировка каждой половины списка не сортирует весь список. Это только половина сортировки слиянием разделов.