Cuenta todos los elementos en la lista de lista anidada arbitraria sin recursión

Question

Acabo de enterarme de la recursión en Python y he completado las asignaciones, una de las cuales era contar todos los elementos dentro de una lista de listas anidadas arbitrariamente. He buscado este sitio y las respuestas encontradas parecen usar llamadas recursivas. Dado que se ha enseñado que todo lo que podría expresarse recursivamente podría expresarse de forma iterativa, y se prefiere la iteración en Python, ¿cómo se lograría esto sin recursión o módulos importados en Python 2.6 (como ejercicio de aprendizaje)? (Una lista anidada en sí sería considerado como un elemento, al igual que su contenido.) Por ejemplo:

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

¿Cómo se escriba esto usando iteración?

Answer 1

Aquí es una manera de hacerlo:

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

El código mantiene una cola de cosas para ser mirado. Cada vez que el bucle encuentra una sublista, agrega su contenido a la cola.

Answer 2

Por lo general, cada problema recursivo se puede convertir en un proceso iterativo de alguna manera mediante el uso de una pila, en este caso un 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 

Answer 3

Usted puede encontrar esta versión de element_count a ser algo más poderoso que los otros. Puede manejar todos los contenedores que admiten iteración e identifica correctamente contenedores recursivos que tienen un número infinito de elementos.

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