Почему этот код ведет себя как хвостовая рекурсия?

Question

Я писал этот код для создания двоичного дерева из обходов по порядку и по порядку и наткнулся на рекурсивное решение, которое сбивало с толку, потому что программа велась как хвостово-рекурсивный вызов вместо стандартной рекурсии.

Я превратил код во что-то общее, чтобы всем было легче понять

class Test:
    def func(self, array):      
        if not array:
            return 0
        print(array)
        array.pop(0)
        temp1 = self.func(array)
        temp2 = self.func(array)

x = [1,2,3,4,5,6]
temp = Test()
temp.func(x)    

Я ожидаю, что вызовы двух функций будут иметь одинаковый вывод дважды.То есть первый вызов должен привести к [2,3,4,5,6], [3,4,5,6] ... [6].Второй вызов функции должен сделать то же самое.Вместо этого второй вызов ничего не происходит.Не должен ли стек рекурсии содержать текущее состояние массива, почему он обновляется?

Answer 1

Списки изменчивы.В вашем рекурсивном вызове вы передаете список, в теле функции вы изменяете список.Каждый звонок изменяет список.Стек рекурсии не должен «держать текущее состояние массива»

Answer 2

array - список, изменяемый объект. Таким образом, func работает с прямой ссылкой на оригинал, а не на локальную копию. Изменения, сделанные в func, внесены в этот оригинал.

Answer 3

Причина, по которой второй вызов не выдает никаких результатов, связана с рекурсивным вызовом в строке выше.Значение массива [] к тому времени, когда вызывается temp2, потому что списки изменчивы в этом контексте.

temp1 = self.func(array) даст следующий вывод:

>>> temp.func(x)
[1, 2, 3, 4, 5, 6]
[2, 3, 4, 5, 6]
[3, 4, 5, 6]
[4, 5, 6]
[5, 6]
[6]

Послеэта функция завершается, список был изменен, и значение array теперь равно [].Возможно, вы захотите создать глубокую копию вашего списка перед выполнением каких-либо мутаций в нем.