14

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?

Improve this question
4
  • 14
    Iteration is preferred for things like simple loops. For inherently recursive problems like this one, recursion is better. Commented May 14, 2012 at 14:05
  • This was more of a learning exercise than a statement of principle. And it seems to be easier to express a solution recursively. However, if the amount of needed recursive calls is unknown beforehand wouldn't this exercise be practical and necessary? Commented May 14, 2012 at 14:17
  • 1
    Shouldn't element_count([1, [1, 2, [3, 4]]]) be 5? Why are you counting the sublist objects themselves as elements? Commented May 14, 2012 at 14:28
  • @KarlKnechtel That was the requirement for the original exercise. Commented May 14, 2012 at 14:32

3 Answers 3

Reset to default
18

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Due to Python's built-in recursion limit, it actually is often a good idea to implement recursive algorithms as iterative ones with an explicit stack. I'm thinking about, e.g., DFS and similar graph algorithms, which will exceed the recursion limit for all but the tiniest problems.
This function is destructive. It will modify the list passed to it.
10

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
Improve this answer

7 Comments

it's basically the same as @aix version, but preserves the original list
Why would while be used instead of for in this example?
while elements on a list is the same as while len(elements) > 0, it will be true as long as there is something to pop in it. as we keep adding to and removing from the list within the loop, a for loop wouldn't work here.
no, it does not, it just iterates over the list. in fact, if you're modifying the list while iterating over it, that can have bad sideeffects.
range also gives you a list (in python2), it'S just used as an example here. you simply shouldn't modify an object you're iterating over, it will save you a lot of trouble.
|
2

You might find this version of element_count to be somewhat more powerful than the others. It can handle all containers that support iteration, and it correctly identifies recursive containers as having an infinite number of elements.

>>> 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
>>>
Improve this answer

3 Comments

Does this not raise a SyntaxError: '{id(p)}'?
Sorry about that! Python 3.2.3 allows literal set notation. The example above has been corrected so that it should work for you now.
This certainly accounts for more input possibilities. Interesting, thanks!

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.