为什么这个函数被认为是队列的实现？
为什么这个函数被认为是队列的实现？
提问于 2018-12-04 13:30:08
这些例子来自Mark的“学习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]等等。
为什么这叫排队？什么对象是‘先进来’，然后‘先出’？
回答 1
Stack Overflow用户
回答已采纳
发布于 2018-12-05 18:55:59
递归版本是深度优先搜索.非递归版本是广度优先搜索。在非递归版本中，items列表被视为队列.每当从items中弹出一个列表时，该列表中的各个元素就会添加到items的末尾。
这是队列的简单定义:元素被添加到后面并从前面移除。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/53614086
复制相关文章
相似问题
腾讯云开发者
