Cómo convertir un algoritmo recursivo ascendente a una stack iterativa en JavaScript

Dado el siguiente algoritmo:

console.log(JSON.stringify(create(0), null, 2)) function create(i) { if (i == 5) return return new Klass(i, create(i + 1), create(i + 1)) } function Klass(i, l, r) { this.i = i this.l = l this.r = r } 

Crea el Klass en create(0) final , después de crear todos los hijos, recursivamente. Así que primero crea los nodos de hoja, luego los pasa al padre, etc.

Me pregunto cómo hacer esto usando una stack sin recursión. Haciéndome doler la cabeza :). Entiendo cómo usar una stack para crear desde arriba hacia abajo, pero no desde abajo hacia arriba. Para arriba hacia abajo, es esencialmente esto:

 var stack = [0] while (stack.length) { var i = stack.pop() // do work stack.push(children) } 

Desde abajo hacia arriba, no puedo ver cómo debería funcionar. Aquí es donde me quedo atascado:

 function create(i) { var stack = [] stack.push([i, 'open']) stack.push([i, 'close']) while (stack.length) { var node = stack.pop() if (node[1] == 'open') { stack.push([ node[0] + 1, 'open' ]) stack.push([ node[0] + 1, 'close' ]) } else { // ?? not sure how to get to this point var klass = new Klass(node[0], node[2], node[3]) // ?? } } } 

No es trivial transformar mecánicamente cualquier código recursivo en una máquina de stack. Las transformaciones automáticas de estado producen códigos muy complejos, solo piense en los generadores C # -s o BabelJS-s. Pero claro, se puede hacer, pero necesitará astackbles y / o registros modificables. Veamos los problemas a los que nos enfrentamos:

¿Cómo recuerda la máquina dónde continuar la ejecución de una función?

Tenemos que almacenar algunas variables de estado / puntero de instrucción en la propia stack. Esto es lo que está emulando con los marcadores "open" y "close" .

¿Dónde poner el resultado de una función?

Hay muchas maneras:

  • almacenándolo en un registro temporal
  • pasando la función una referencia a un campo (un par (objeto, nombre de campo)), emulando parámetros
  • utilizando una segunda stack como @CtheSky hizo

Usando marcos de stack mutables y un registro de resultados, el código transformado se vería así:

 console.log(JSON.stringify(create(0), null, 2)) function Klass(i, l, r) { this.i = i this.l = l this.r = r } function Frame(i) { this.ip = 0; this.i = i; this.left = null; } function create(i) { var result; var stack = [new Frame(i)]; while (stack.length > 0) { var frame = stack[stack.length - 1]; switch (frame.ip) { case 0: if (frame.i === 5) { result = undefined; stack.pop(); break; } stack.push(new Frame(frame.i + 1)); frame.ip = 1; break; case 1: frame.left = result; stack.push(new Frame(frame.i + 1)); frame.ip = 2; break; case 2: result = new Klass(frame.i, frame.left, result); stack.pop(); break; } } return result; } 

Esta es una solución que utiliza dos stacks.

Supongamos que siempre calculamos el niño derecho antes que el izquierdo, necesitamos una manera de almacenar el resultado del niño derecho. Es posible almacenarlo en la stack original, pero sería complicado ya que esa stack también se usa para calcular el hijo izquierdo. Así que uso otra stack para almacenar los resultados de los niños correctos.

Hay tres estados:

  • necesita trabajo -> necesita empujar al niño en la stack para calcular
  • necesita fusionar -> esperar a la izquierda y derecha al niño para ser computado
  • terminar el trabajo -> todo el trabajo se ha hecho

Cuando vea que un nodo con estado finish work , verificará si es need merge el estado del siguiente nodo:

  • si no lo es, el nodo finalizado actual es el hijo correcto, empújelo a la stack de caché. Y listo para computar hijo izquierdo.
  • si es así, el nodo finalizado actual es el elemento secundario izquierdo, salta de la stack y la stack de caché para obtener la raíz y el elemento secundario derecho, construye un nuevo nodo y empújalo de nuevo a la stack con el finish work estado
 console.log(JSON.stringify(create(2, 5), null, 2)) function Klass(i, l, r) { this.i = i; this.l = l; this.r = r; } function create(i, growto) { var stack = []; var cache = []; stack.push([i, 'need work']); while (stack.length && stack[0][1] !== 'finish work') { var cur = stack.pop(); var val = cur[0]; var status = cur[1]; if (status === 'need work') { if (val !== growto) { stack.push([val, 'need merge']); stack.push([val + 1, 'need work']); stack.push([val + 1, 'need work']); } else { stack.push([val, 'finish work']); } } else if (status === 'finish work') { if (stack[stack.length - 1][1] !== 'need merge') { cache.push(cur); } else { var root = stack.pop()[0]; var left = cur[0]; var right = cache.pop()[0]; stack.push([new Klass(root, left, right), 'finish work']); } } } return stack.pop()[0]; } 

¿Qué tal algo como esto?

 console.log(JSON.stringify(create(4), null, 2)) function create(depth) { let n = Math.pow(2, depth); let nodes = []; for (let i = 0; i < n; i++) nodes.push(new Klass(depth)); for (depth--; depth >= 0; depth--) { let next = []; while (nodes.length > 0) next.push(new Klass(depth, nodes.pop(), nodes.pop())); nodes = next; } return nodes[0]; } function Klass(i, l, r) { this.i = i this.l = l this.r = r } 

Vamos a empezar con sólo los i s:

 function create(i) { console.log(i) if (i == 3) return return new Klass(i, create(i+1), create(i+1)) } function Klass(i, l, r) { this.i = i this.l = l this.r = r } console.log(JSON.stringify(create(0))) console.log('\nStack version:') let stack = [0]; while (stack.length){ let i = stack.pop(); console.log(i); if (i < 3) stack.push(i + 1, i + 1); }