Count all elements in list of arbitrary nested list without recursion

Question

I have just learned about recursion in Python and have completed assignments, one of which was to count all the elements within a list of arbitrarily nested lists. I have searched this site and the answers found all seem to use recursive calls. Since it has been taught that anything which could be expressed recursively could be expressed iteratively, and iteration is preferred in Python, how would this be accomplished without recursion or imported modules in Python 2.6 (as a learning exercise)? (A nested list itself would be counted as an element, as would its contents.) For example:

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

How would this be written using iteration?

Answer 1

Here is one way to do it:

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

The code maintains a queue of things to be looked at. Whenever the loop encounters a sub-list, it adds its contents to the queue.

Answer 2

Usually each recursive problem can be converted to an iterative somehow by using a stack, in this case a 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