计算任意嵌套列表列表中的所有元素,不进行递归

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

如何使用迭代编写？

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]]]]]]]])

代码维护着要查看的事物队列.每当循环遇到子列表时,它就会将其内容添加到队列中.

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