En general, una recursión crea un árbol de llamadas, la raíz es la llamada original, y las hojas son las llamadas que no son recursivos.
Un caso degenerado es cuando cada llamada solo realiza otra llamada, en este caso el árbol degenera en una lista simple. La transformación en una iteración se logra simplemente utilizando una pila, como lo demuestra @Jeremiah.
En el caso más general, como aquí, cuando cada llamada realiza más (estrictamente) que una llamada. Obtienes un árbol real, y hay, por lo tanto, varias formas de atravesarlo.
Si utiliza una cola, en lugar de una pila, está realizando un recorrido transversal en anchura. @Jeremiash presentó un recorrido por el cual no conozco ningún nombre. El orden típico de "recursión" es normalmente un recorrido transversal en profundidad.
La principal ventaja de la recursividad típico es que la longitud de la pila no crece tanto, por lo que debe aspirar a primero en profundidad, en general, ... si la complejidad no abrumar a ti :)
Sugiero comenzar escribiendo un primer recorrido de profundidad de un árbol, una vez hecho esto, adaptarlo a su algoritmo debería ser bastante simple.
EDIT: Ya que tenía algún tiempo, me escribió el pitón del árbol de recorrido, es el ejemplo canónico:
class Node:
def __init__(self, el, children):
self.element = el
self.children = children
def __repr__(self):
return 'Node(' + str(self.element) + ', ' + str(self.children) + ')'
def depthFirstRec(node):
print node.element
for c in node.children: depthFirstRec(c)
def depthFirstIter(node):
stack = [([node,], 0), ]
while stack != []:
children, index = stack.pop()
if index >= len(children): continue
node = children[index]
print node.element
stack.append((children, index+1))
stack.append((node.children, 0))
Tenga en cuenta que la gestión de la pila es algo complicado por la necesidad de recordar el índice de la niño que estábamos visitando actualmente.
y la adaptación del algoritmo siguiendo el orden de primero en profundidad:
def generateBrackets(c):
# stack is a list of pairs children/index
stack = [([(c,c,''),], 0), ]
while stack != []:
children, index = stack.pop()
if index >= len(children): continue # no more child to visit at this level
stack.append((children, index+1)) # register next child at this level
l, r, current = children[index]
if r == 0 and l == 0: print current
# create the list of children of this node
# (bypass if we are already unbalanced)
if l > r: continue
newChildren = []
if l != 0: newChildren.append((l-1, r, current + '<'))
if r != 0: newChildren.append((l, r-1, current + '>'))
stack.append((newChildren, 0))
Me acabo de dar cuenta que el almacenamiento del índice es un poco "demasiado" complicado, ya que nunca visita de regreso. La solución simple consiste en eliminar los elementos de la lista que ya no necesito, tratando la lista como una cola (¡de hecho, una pila podría ser suficiente)!
Esto se aplica con una transformación mínima.
def generateBrackets2(c):
# stack is a list of queues of children
stack = [[(c,c,''),], ]
while stack != []:
children = stack.pop()
if children == []: continue # no more child to visit at this level
stack.append(children[1:]) # register next child at this level
l, r, current = children[0]
if r == 0 and l == 0: print current
# create the list of children of this node
# (bypass if we are already unbalanced)
if l > r: continue
newChildren = []
if l != 0: newChildren.append((l-1, r, current + '<'))
if r != 0: newChildren.append((l, r-1, current + '>'))
stack.append(newChildren)
Ackermann se puede convertir en una estructura iterativa, como cualquier otra función recursiva, suponiendo que se trabaja en un lenguaje completo de Turing. –
Puede lograr dicho algoritmo usando programación dinámica. No sabría cómo implementarlo en Python, así que si está interesado en una versión de estilo C, dígame y publicaré un código. Todas las combinaciones posibles de N par de corchetes, básicamente son todos los posibles árboles binarios con N nodos. Para construir todos esos árboles, primero debe ser capaz de construir todos los árboles posibles con 0..N-1 nodos, y luego tomar uno de esos árboles con X nodos (donde X está entre 0..N-1) y otro árbol con nodos Y (donde Y es igual a N-1-X) y añádales una raíz común. – Fede
Gracias a todos por las respuestas, todos fueron muy útiles y la parte más difícil es tener que seleccionar "una" respuesta correcta. Voy con la respuesta de @ tangentstorm ya que fue la versión "iterativa" más fácil de entender para mí. – AlgoLearner