эти примеры взяты из Learning Python Марка Лутца.Первая функция - это рекурсивная функция, используемая для обхода списка с произвольным вложением для вычисления суммы элементов:
def sumtree_rec(L):
tot = 0
for x in L:
if not isinstance(x, list):
tot += x
else:
tot += sumtree(x)
return tot
Вторая функция выполняет то же самое, но без рекурсии:
def sumtree_notrec(L):
tot = 0
items = list(L)
while items:
front = items.pop(0)
if not isinstance(front, list):
tot += front
else:
items.extend(front)
return tot
Мне кажется, я понимаю, как работают обе эти функции.Я проследил, как L изменяется в sumtree_notrec с каждой итерацией по телу кода, и это соответствует выводу из книги.Я также думаю, что понимаю, почему рекурсия считается стеком, поскольку каждый уровень помещает кадр вызова в стек времени выполнения и отбрасывается при завершении вызова.
Что я не понимаю, так это почемурекурсивная функция называется очередью FIFO?Я посмотрел вверх и чувствую, что понимаю, что представляют собой структуры данных, я просто не понимаю, как они применяются к этой функции.Я также нашел этот ресурс, который немного объяснил о стеке вызовов: https://www.cs.ucsb.edu/~pconrad/cs8/topics.beta/theStack/02/
Например, если я прослеживаю через L в нерекурсивной функции (не фактический код, просто представление):
L --> [1,[2,[3,4],5],6,[7,8]]
L --> (1) is popped [[2,[3,4],5],6,[7,8]]
L --> [2,[3,4],5] is not popped
L --> [6,[7,8],2,[3,4],5]
и т.д ...
Почему это называется очередью?Какой объект «сначала входит», а затем «сначала выходит»?