Блог

Для понимания рекурсии и ее производительности в Python я написал рекурсивную функцию, которая возвращает максимальное значение в списке:

 def max_list(A):
    print(id(A)) # debugging purposes
    if len(A) > 1:
        max_list_tail = max_list(A[:-1])
    else:
        max_list_tail = A[0]
    if A[-1] > max_list_tail:
        return A[-1]
    else:
        return max_list_tail
 

Идея этой функции заключается в том, что если последний элемент текущего списка больше максимума среди «хвоста» списка, то есть всех элементов, кроме последнего, последний является максимальным, в противном случае максимум хвоста является максимальным.

Как вы можете видеть, я передаю нарезанный список A[:-1] в качестве параметра.

Вопросы:

1. Правильно ли я говорю следующее: каждый раз, когда я передаю A[:-1] , создается новый список, который является копией моего старого списка, за исключением последнего элемента? В целях отладки я печатаю идентификатор каждого нарезанного списка, и идентификаторы разные, что наводит меня на мысль, что я прав, но мне нужно подтверждение от экспертного сообщества.
2. Если 1. да, это правда, какова временная сложность моей функции? Могу ли я сказать O(n^2) , что это связано с тем, что требуется O(n) найти максимум в исходном списке и O(n) создавать копию текущего списка каждый раз, когда я рекурсивно вызываю функцию?