不使用递归计算任意嵌套列表中所有元素的数量

Question

我刚学习了Python中的递归，并完成了一些作业，其中之一是计算任意嵌套列表中的所有元素数量。我在这个网站上搜索了一下，发现所有找到的答案都使用了递归调用。由于教授我们可以用迭代来表达递归能表达的任何事情，并且在Python中优先选择迭代，那么如何在Python 2.6中不使用递归或导入模块的情况下完成此操作（作为学习练习）？（嵌套列表本身将被计算为一个元素，其内容也将如此。） 例如：

>>> def element_count(p):
...     count = 0
...     for entry in p:
...         count += 1
...         if isinstance(entry, list):            
...             count += element_count(entry)
...     return count
>>> print element_count([1, [], 3]) 
3 
>>> print element_count([1, [1, 2, [3, 4]]])
7
>>> print element_count([[[[[[[[1, 2, 3]]]]]]]])
10

如何使用迭代来编写这个代码？

- Verbal_Kint

---

迭代适用于像简单循环这样的事情。对于固有的递归问题，如此之类的问题，递归更好。 - interjay

这更多是一个学习练习，而不是原则性的陈述。似乎用递归方式表达解决方案更容易。然而，如果需要的递归调用数量事先未知，那么这个练习是否实用和必要呢？ - Verbal_Kint

element_count([1, [1, 2, [3, 4]]]) 不应该是5吗？为什么你把子列表对象本身也算作元素呢？ - Karl Knechtel

@KarlKnechtel 那是原始练习的要求。 - Verbal_Kint

Answer 1

以下是其中一种方法：

def element_count(p):
  q = p[:]
  count = 0
  while q:
    entry = q.pop()
    if isinstance(entry, list):
      q += entry
    count += 1
  return count

print element_count([1, [], 3]) 
print element_count([1, [1, 2, [3, 4]]])
print element_count([[[[[[[[1, 2, 3]]]]]]]])

代码维护了一个待查看事项的队列。每当循环遇到子列表时，它都会将其内容添加到队列中。

- NPE

---

由于Python内置递归深度限制，实际上将递归算法实现为显式栈的迭代算法通常是一个好主意。例如，对于DFS和类似的图算法来说，即使是最小的问题也会超过递归限制。 - Fred Foo

这个函数会对传入的列表进行修改，具有破坏性。 - Noufal Ibrahim

Answer 2

通常每个递归问题都可以通过使用栈来转换为迭代问题，而在这种情况下，是通过使用一个 list 来实现的：

def element_count(p):
    elements = list(p)
    count = 0
    while elements:
        entry = elements.pop()
        count += 1
        if isinstance(entry, list):
            elements.extend(entry)
    return count

- mata

---

它基本上与@aix版本相同，但保留了原始列表。 - mata

当列表中的元素与while len(elements) > 0相同时，只要有东西可以弹出，它就为真。由于我们在循环内不断地添加和删除列表中的元素，因此在这里使用for循环是行不通的。 - mata

'for'循环会保留并使用原始列表，从而忽略更改吗？换句话说，在循环开始之前，'for'是否会缓存原始列表？ - Verbal_Kint

不会，它只是遍历列表。实际上，如果您在迭代过程中修改列表，那么可能会产生不良的副作用。 - mata

range函数在Python2中返回一个列表，这里只是举个例子。在迭代对象时，你不应该修改它，这会给你带来很多麻烦。 - mata

Answer 3

你可能会发现这个版本的element_count比其他版本更加强大。它可以处理支持迭代的所有容器，并且可以正确地识别递归容器具有无限数量的元素。

>>> def element_count(p):
    stack, pointers, count = [iter(p)], set([id(p)]), 0
    while stack:
        for item in stack.pop():
            try:
                iterator = iter(item)
            except TypeError:
                pass
            else:
                location = id(item)
                if location in pointers:
                    return float('inf')
                stack.append(iterator)
                pointers.add(location)
            count += 1
    return count

>>> element_count([1, [], 3])
3
>>> element_count([1, [1, 2, [3, 4]]])
7
>>> element_count([[[[[[[[1, 2, 3]]]]]]]])
10
>>> p = [1, 2, 3]
>>> element_count(p)
3
>>> p.append({4, 5, 6})
>>> element_count(p)
7
>>> p.append(p)
>>> element_count(p)
inf
>>> 

- Noctis Skytower

---

这不会引发 SyntaxError 错误吗：'{id(p)}'？ - Verbal_Kint

抱歉！Python 3.2.3允许文字集合表示法。上面的示例已经被更正，现在应该可以为您工作了。 - Noctis Skytower

这肯定会带来更多的输入可能性。有趣，谢谢！ - Verbal_Kint