que - Cómo convertir sincronización y función recursiva asincrónica a iteración en JavaScript

como hacer una funcion recursiva en javascript

Question

Se busca una implementación específica para las funciones recursivas sincronizadas y asíncronas que podrían usarse como punto de partida para convertir funciones recursivas futuras en iteraciones planas.

A continuación hay dos ejemplos de funciones recursivas: Sincrónico y Asíncrono .

Lo que estoy buscando es una implementación de ambos usando una pila sin recurrencia .

Por ejemplo, tal vez funcionaría así:

var output = syncStack(myRecursiveFunctionTurnedIterative, [])

O si eso no es posible, entonces solo se debe volver a implementar las dos funciones a continuación usando una pila, y ese debería ser un comienzo lo suficientemente bueno. P.ej

var stack = []

function circularReferences(object, references, stack) {
  var output = {}
  if (object.__circularid__) return true
  Object.defineProperty(object, ''__circularid__'', { value: id++ })
  for (var key in object) {
    var value = object[key]
    if (value && typeof value == ''object'') {
      console.log(value)
      stack.push(???)
      circularReferences()
      stack.pop()
      if (is) output[key] = ''[Circular]''
    } else {
      output[key] = value
    }
  }
}

El motivo de esta pregunta es: he intentado durante años aprender a hacer esto, pero nunca he encontrado un sistema que sea (a) fácil de recordar cómo hacerlo, y (b) práctico.

Sincrónico

var references = {}
var object = {
  a: {
    b: {
      c: {
        d: {
          e: 10,
          f: 11,
          g: 12
        }
      }
    }
  }
}
object.a.b.c.d.x = object
object.a.b.c.d.y = object.a.b

var id = 1

var x = circularReferences(object, references)
console.log(x)

function circularReferences(object, references) {
  var output = {}
  if (object.__circularid__) return true
  Object.defineProperty(object, ''__circularid__'', { value: id++ })
  for (var key in object) {
    var value = object[key]
    if (value && typeof value == ''object'') {
      console.log(value)
      var is = circularReferences(value, references)
      if (is) output[key] = ''[Circular]''
    } else {
      output[key] = value
    }
  }
}

Asychronous

var items = [
  async1a,
  async1b,
  async1c
  // ...
]

asynca(items, function(){
  console.log(''done'')
})

function asynca(items, callback) {
  var i = 0

  function next() {
    var item = items[i++]
    if (!item) return callback()

    item(next)
  }
}

function async1a(callback) {
  // Some stuff...
  setTimeout(function(){
    if (true) {
      var items = [
        async2a,
        // ...
      ]

      asynca(items, callback)
    } else {
      callback(null, true)
    }
  }, 200)
}

function async1b(callback) {
  // Some stuff...
  setTimeout(function(){
    if (true) {
      var items = [
        async2a,
        // ...
      ]

      asynca(items, callback)
    } else {
      callback(null, true)
    }
  }, 200)
}

function async1c(callback) {
  // Some stuff...
  setTimeout(function(){
    if (true) {
      var items = [
        async2a,
        // ...
      ]

      asynca(items, callback)
    } else {
      callback(null, true)
    }
  }, 200)
}

function async2a(callback) {
  return callback()
}

Por ejemplo, eso puede comenzar a verse algo así como:

var items = [
  async1a,
  async1b,
  async1c
  // ...
]

asynca(items, function(){
  console.log(''done'')
}, [])

function asynca(items, callback, stack) {
  var i = 0

  function next() {
    var item = items[i++]
    if (!item) return callback()
    stack.push(item)
  }
}

Pero ahí es donde me pierdo. No estoy seguro de cómo pasar la pila y cómo deben configurarse las funciones en general .

Preguntarse cómo en la práctica escribir esos como funciones no recursivas. He visto a Way pasar de la recursión a la iteración, pero todas son muy teóricas.

Answer 1

Creo que es una mala idea Veo el beneficio en esto como un ejercicio puramente intelectual, pero estás forzando una respuesta muy desordenada y complicada a un problema de recursos simple que podría resolverse por otros medios.

Cuando se ejecuta una función en Javascript, inserta una dirección de retorno, parámetros de función y variables locales en una pila. Es virtualmente imposible obtener muchos ahorros con un problema naturalmente recursivo de profundidad indefinida forzándolo a un ciclo. Una respuesta anterior (cuyo nombre no puedo escribir o incluso copiar y pegar bien porque está en un código RTL) discutió la recursividad de cola, y si puede ajustarse al patrón, puede obtener algunos ahorros menores al no insertar la dirección de retorno en la pila, pero De todos modos, los motores de Javascript podrían ocuparse de eso.

Una diferencia y una carga de rendimiento adicional en comparación con otros lenguajes, por ejemplo PHP, sería que Javascript también crea un cierre para cada invocación de la función. Esto podría ser un costo de recursos trivial o sustancial en conjuntos de datos muy profundos y muy amplios, del tipo que probablemente cause un problema donde uno podría pensar que la no repetición resolvería ese problema. Sin embargo, hay un medio para invocar una función sin cierre utilizando el constructor de Función. Nos rehuimos de estos porque eval-is-evil y dan un paso más para compilar, pero una vez creado, esto podría reducir cualquier sobrecarga adicional de cierres en recursión profunda. El golpe de rendimiento de compilación en vivo debería ser más que compensado por una sobrecarga reducida en las llamadas de recursión profunda.

Otros drags de rendimiento pueden estar creando un objeto de argumentos y un contexto de ejecución (esto). Ahora también tenemos funciones de flecha que simplemente heredarán las instancias del alcance externo. Entonces la porción recursiva real debería ser una función de flecha. Si necesita un this , páselo por el cierre de la Function externa o páselo como parámetro.

Aquí hay un mapa general:

const outerFunction=new Function(
    ''arg1,arg2,arg3'',
    `
        // Initialize and create items that simply must be transferred by closure
        ...
        const recursiveFunction=(param1,param2,param3)=>{
            ...
            const value=recursiveFunction(newParam1,newParam2,newParam3)
            ...
        }
        return recursiveFunction(firstParam1,firstParam2,firstParam3)
    `
)

Una vez dentro del patrón general, optimice el circuito interno tanto como sea posible. No construya y recombine objetos y matrices si los originales se pueden pasar como referencias. No haga ningún chequeo de duck o procesamiento extraño en la parte recursiva. A los programadores de Javascript no se les enseña mucho sobre pérdidas de memoria, ya que tradicionalmente se trata de fragmentos cortos que se borran cuando se actualiza la página, así que aprenda a detectar instancias donde los elementos que ya no se necesitan no pueden ser basura, y para eso reduzca artículos que deben ser recogidos basura si el problema es la velocidad en lugar de la memoria. Recuerde que todas las primitivas son inmutables, y los valores antiguos estarán sujetos a GC cuando se les asignen nuevos valores. Considere el uso de Arrays tipificados donde sea razonable, para evitar esto.

Incluso si esto no resuelve las preocupaciones del OP, espero que este enfoque pueda ser útil para otros que encuentren esta pregunta en Google.

Answer 2

En su lugar, hay una forma general de traducir la función recursiva para usar una pila explícita: simular la forma en que un compilador puede manejar las llamadas recursivas. Guarde todos los estados locales en una pila, cambie los valores de los argumentos a lo que se hubiera pasado a la llamada recursiva y salte a la parte superior de la función. Luego, donde la función retorna, en lugar de simplemente regresar, revisa la pila. Si no está vacío, pop state y salta al lugar donde la llamada recursiva habría regresado. Dado que javascript no permite saltos ( goto ), entonces es necesario hacer álgebra en el código para transformarlos en bucles.

Comience con un código recursivo que será un poco más fácil de manejar que su original. Esto es solo un DFS recursivo clásico con marcas "visitadas" para objetos (nodos de gráficos) que ya hemos buscado y marcas "actuales" para objetos en la ruta desde el objeto superior (raíz) al actual. Descubriremos todos los ciclos si para cada referencia de objeto (borde del gráfico), verificamos si el destino está marcado como "actual".

Las marcas actuales se eliminan en el camino. Las marcas visitadas permanecen después de que se haya buscado el gráfico.

function get_back_refs(obj, back_refs) {
  if (obj && typeof obj == ''object'' && !(''__visited__'' in obj)) {
    mark(obj, ''__visited__'')
    mark(obj, ''__current__'')
    var iter = getKeyIterator(obj)
    while (iter.hasNext()) {
      var key = iter.next()
      if (''__current__'' in obj[key]) {
        back_refs.push([obj, obj[key]])
      } else {
        get_back_refs(obj[key], back_refs)
      }
    }
    unmark(obj, ''__current__'')
  }
}

var object = {
  a: {
    b: {
      c: {
        d: {
          e: 10,
          f: 11,
          g: 12
        }
      }
    }
  }
}
object.a.b.c.d.x = object
object.a.b.c.d.y = object.a.b

var id = 0

function mark(obj, name) {
  Object.defineProperty(obj, name, { value: ++id, configurable: true })
}

function unmark(obj, name) {
  delete obj[name]
}

function getKeyIterator(obj) {
  return {
    obj: obj,
    keys: Object.keys(obj).filter(k => obj[k] && typeof obj[k] == ''object''),
    i: 0,
    hasNext: function() { return this.i < this.keys.length },
    next: function() { return this.keys[this.i++] }
  }
}

var back_refs = []
get_back_refs(object, back_refs)
for (var i = 0; i < back_refs.length; ++i) {
  var pair = back_refs[i]
  console.log(pair[0].__visited__ + '', '' + pair[1].__visited__)
}

Tenga en cuenta que creo que esto corrige errores en su código. Como la jerarquía es un gráfico dirigido general, debe evitar buscar objetos dos veces. Omitir esto puede conducir fácilmente al tiempo de ejecución exponencial en el tamaño del gráfico. Sin embargo, la estructura compartida en el gráfico no necesariamente significa que hay un ciclo. El gráfico podría ser un DAG - dirigido y acíclico.

En este caso, el estado local está contenido muy bien en el iterador, así que eso es todo lo que necesitamos en la pila:

function get_back_refs2(obj, back_refs) {
  var stk = []
  var iter = null
 start:
  if (obj && typeof obj == ''object'' && !(''__visited__'' in obj)) {
    mark(obj, ''__visited__'')
    mark(obj, ''__current__'')
    iter = getKeyIterator(obj)
    while (iter.hasNext()) {
      var key = iter.next()
      if (''__current__'' in obj[key]) {
        back_refs.push([obj, obj[key]])
      } else {
        stk.push(iter) // Save state on stack.
        obj = obj[key] // Update parameter value.
        goto start     // Eliminated recursive call.          
       rtn:            // Where call would have returned.
      }
    }
    unmark(obj, ''__current__'')
  }
  if (stk.length == 0) return
  iter = stk.pop()  // Restore iterator from stack.
  obj = iter.obj    // Restore parameter value.
  goto rtn
}

Ahora para eliminar los goto s. Este artículo describe una transformación muy similar para buscar un árbol en lugar de un gráfico general, por lo que no lo voy a detallar aquí. Terminamos con este resultado intermedio:

function get_back_refs2(obj, back_refs) {
  var stk = []
  var iter = null
  for (;;) {
    if (obj && typeof obj == ''object'' && !(''__visited__'' in obj)) {
      mark(obj, ''__visited__'')
      mark(obj, ''__current__'')
      iter = getKeyIterator(obj)
      var key = null
      while (iter.hasNext()) {
        key = iter.next()
        if (''__current__'' in obj[key]) back_refs.push([obj, obj[key]])
        else break
      }
      if (key) {
        stk.push(iter)
        obj = obj[key]
        continue           
      }
      unmark(obj, ''__current__'')
    }
    for(;;) {
      if (stk.length == 0) return
      iter = stk.pop()
      obj = iter.obj
      var key = null
      while (iter.hasNext()) {
        key = iter.next()
        if (''__current__'' in obj[key]) back_refs.push([obj, obj[key]])
        else break
      }
      if (key) {
        stk.push(iter)
        obj = obj[key]
        break
      }           
      unmark(obj, ''__current__'')
    }
  }
}

Reemplazar goto s con el código que causan para ejecutar los resultados en la repetición. Pero podemos SECAR eso con una función local compartida:

function get_back_refs2(obj, back_refs) {
  var stk = []
  var iter = null
  var descend_to_next_child = function() {
    var key = null
    while (iter.hasNext()) {
      key = iter.next()
      if (''__current__'' in obj[key]) back_refs.push([obj, obj[key]])
      else break
    }
    if (key) {
      stk.push(iter)
      obj = obj[key]
      return true           
    }
    unmark(obj, ''__current__'')
    return false
  }
  for (;;) {
    while (obj && typeof obj == ''object'' && !(''__visited__'' in obj)) {
      mark(obj, ''__visited__'')
      mark(obj, ''__current__'')
      iter = getKeyIterator(obj)
      if (!descend_to_next_child()) break
    }
    for(;;) {
      if (stk.length == 0) return
      iter = stk.pop()
      obj = iter.obj
      if (descend_to_next_child()) break
    }
  }
}

Unless I made an algebra mistake, which is certainly possible, this is a drop-in replacement for the original recursive version.

Though the method doesn''t involve reasoning beyond the code algebra, now that we''re done it''s pretty clear that the first loop descends into the graph, always to the first child it finds that isn''t a back-reference, pushing iterators onto the stack as it goes. The second loop pops the stack looking for an iterator with work left to do: at least one child to search. When it finds one, it returns control to the first loop. This is exactly what the recursive version does, expressed in a different manner.

It would be fun to build a tool to do these transformations automatically.

Answer 3

Para que nosotros podamos convertir un procedimiento con una función que llame a otra función (ya sea que se trate de la misma función o no, también conocida como ''recursiva''), necesitaremos separarla en el procedimiento que ocurre antes de dicha función. llamada y cualquier procedimiento posterior a la llamada. Si no hay procedimientos después del out-call y el out-call es para la misma función, podemos describirlo como "tail recursive", que puede hacer que la conversión a iterativo sea mucho más simple, simplemente presionando los parámetros de llamada a la pila ( Example ). De hecho, convertir la recursividad de cola en un proceso de pila iterativo me ha ayudado a superar los límites de profundidad de recursividad de los navegadores en más de una instancia real.

Conversión a recursivo de cola

Para convertir una recursividad en recursiva de cola, debemos considerar cómo se procesa la información entregada desde la llamada recursiva y si podemos transformar este proceso para utilizar parámetros en la recursividad misma. Dado que en su ejemplo particular, lo único que sucede con el resultado de la llamada saliente es la configuración de la variable local, output y output es un objeto, que en JavaScript se pasa por referencia, estamos en condiciones de realizar esta transformación . Así que aquí hay un refactor simple que nos permitirá usar una pila sucinta (salté el código recursivo de cola a la implementación de la pila, dejé como un ejercicio para el lector):

var references = {}
var object = {
  a: {
    b: {
      c: {
        d: {
          e: 10,
          f: 11,
          g: 12
        }
      }
    }
  }
}
object.a.b.c.d.x = object
object.a.b.c.d.y = object.a.b

var id = 1

//var x = circularReferences(object, references)
//console.log(x)

//function circularReferences(object, references) {
// => add parameters, ''output'' and ''key''
var stack = [[object, references, null, null]];

while (stack.length){
  [_object, _references, _callerOutput, _key] = stack.pop()

  var output = {}
  
  if (_object.__circularid__){
    _callerOutput[_key] = ''[Circular]''
    
    // Log our example
    console.log(''OUTPUT VALUE: '' + JSON.stringify(_callerOutput))
    
    // Exit
    continue;
  }
  
  Object.defineProperty(_object, ''__circularid__'', { value: id++ })
  
  for (var key in _object) {
    var value = _object[key]
    
    if (value && typeof value == ''object'') {
      console.log(value)
      
      //var is = circularReferences(value, references)
      // if (is) output[key] = ''[Circular]''
      stack.push([value, _references, output, key])
        
    } else {
      output[key] = value
    }
  }
}

Generalizando la pila y ordenando operaciones

Dado que puede no ser siempre fácil y sencillo transformar una recursividad en recursiva de cola, consideremos cómo podemos utilizar la pila para ordenar operaciones de forma iterativa de forma similar a la recursión original. También generalizaremos un poco nuestra pila, lo que nos ayudará con su segundo ejemplo "Asíncrono". En lugar de solo los parámetros de llamada, almacenamos tanto la función a llamar como los parámetros. Algo como:

(stack) [
  [function A, parameters for this call of A, additional refs for this call of A],
  [function B, parameters for this call of B, additional refs for this call of B]
]

Como sabemos, una pila opera "último en entrar, primero en salir", lo que significa que si tenemos una función con operaciones posteriores a una llamada a otra función, esas operaciones subsecuentes necesitarán ser empujadas a la pila antes de la llamada para que el orden de procesamiento de la pila sea algo así como:

(stack) [first_call]
pop stack
  => first_call:
       process procedure before out_call
       push procedure after out_call
         => (stack) [procedure after out_call]
       push out_call
         => (stack) [procedure after out_call,
                     out_call]
pop stack
  => out_call
     (maybe followed by a whole other series of stack interactions)
pop stack
  => procedure after out_call (maybe use stored result)

(Todo esto es una especie de truco para utilizar el concepto de pila para ordenar nuestras operaciones. Si desea obtener una fantasía real (y aún más complicada), codifique cada instrucción como una función y simule una pila de llamadas real con la capacidad de pause la siguiente instrucción en el programa principal a medida que se le envían llamadas a otras funciones).

Ahora apliquemos esta idea a sus ejemplos:

Ejemplo sincrónico

No solo tenemos procedimientos de llamada de salida aquí, sino que tenemos un bucle completo con dichas llamadas. (Tenga en cuenta que los registros de la consola vistos directamente en el visor de fragmentos están incompletos. Observe la consola JS de su navegador para ver los registros completos).

var references = {};
var object = {
  a: {
    b: {
      c: {
        d: {
          e: 10,
          f: 11,
          g: 12
        }
      }
    }
  }
};

object.a.b.c.d.x = object;
object.a.b.c.d.y = object.a.b;

var id = 1;


let iterativeProcess = {
  stack: [],
  currentResult: undefined,
  start: function(){
    // Garbage collector :)
    iterativeProcess.currentResult = undefined

    console.log(''Starting stack process'')
    
    // Used for debugging, to avoid an infinite loop
    let keep_going = 100;
    
    while (iterativeProcess.stack.length && keep_going--){
        let [func_name, func, params, refs] = iterativeProcess.stack.pop();

        console.log(''/npopped: ['' + func_name + '', '' + params + '', '' + JSON.stringify(refs) + '']'');
        
        params.unshift(refs);
        
        func.apply(func, params);
    }
    
    return ''Stack process done/n/n'';
  }
};


let circularReferences = {
  preOutCall: function(refs, _object, _references){
    var output = {};
    
    if (_object.__circularid__){
      console.log(''preOutCall: _object has __circularid__ setting currentResult true'')
      iterativeProcess.currentResult = true;
      
      // Exit
      return;
    }
    
    Object.defineProperty(_object, ''__circularid__'', { value: id++ })
    
    // Push post-out-call-procedure to stack
    console.log(''Pushing to stack postOutCall '' + Object.keys(_object)[0])
    iterativeProcess.stack.push([''postOutCall'', circularReferences.postOutCall, [], output]);
    
    // Call for-loop in reverse
    let keys = Object.keys(_object);

    for (let i=keys.length-1; i >=0; i--)
      circularReferences.subroutineA(output, _object, keys[i], _references);
  },
  
  subroutineA: function(refs, _object, key, _references){
    var value = _object[key];
      
    if (value && typeof value == ''object''){
      console.log(''subroutineA: key: '' + key + ''; value is an object: '' + value);
      
      console.log(''Pushing to stack postSubroutineA '' + key)
      iterativeProcess.stack.push([''postSubroutineA'', circularReferences.postSubroutineA, [key], refs]);
      
      // Push out-call to stack
      console.log(''Pushing to stack preOutCall-'' + key)
      iterativeProcess.stack.push([''preOutCall-'' + key, circularReferences.preOutCall, [value, _references], refs]);
  
    } else {
      console.log(''subroutineA: key: '' + key + ''; value is not an object: '' + value);
      console.log(''Pushing to stack subroutineA1 '' + key)
      iterativeProcess.stack.push([''subroutineA1'', circularReferences.subroutineA1, [key, value], refs]);
    }
  },
  
  subroutineA1: function(refs, key, value){
    console.log(''subroutineA1: setting key '' + key + '' to '' + value);
    
    refs[key] = value;
  },
  
  postSubroutineA: function(refs, key){
    let is = iterativeProcess.currentResult; //circularReferences(value, _references)
        
    if (is){
      refs[key] = ''[Circular]'';
      
      console.log(''postSubroutineA: Object key: '' + key + '' is circular; output: '' + JSON.stringify(refs));
      
    } else {
      console.log(''postSubroutineA: key: '' + key + ''; currentResult: '' + iterativeProcess.currentResult + ''; output: '' + JSON.stringify(refs));
    }
  },
  
  postOutCall: function(){
    // There is no return statement in the original function
    // so we''ll set current result to undefined
    iterativeProcess.currentResult = undefined;
  }
};

// Convert the recursive call to iterative

//var x = circularReferences(object, references)
//console.log(x)
console.log(''Pushing to stack'')
iterativeProcess.stack.push([''preOutCall'', circularReferences.preOutCall, [object, references]]);
console.log(iterativeProcess.start());

Ejemplo asíncrono

(Me tomé la libertad de agregar una llamada a next() al final de asynca , que creo que olvidó).

Aquí, además de múltiples llamadas de función entrelazadas, tenemos la complicación de que las llamadas son asincrónicas, lo que básicamente significa que habrá más de un proceso de pila. Dado que en este ejemplo particular los procesos de pila no se superpondrán en el tiempo, solo usaremos una pila, llamada secuencialmente. (Tenga en cuenta que los registros de la consola vistos directamente en el visor de fragmentos están incompletos. Observe la consola JS de su navegador para ver los registros completos).

let async = {
  asynca: function(refs, items, callback){
    let i = 0;
    
    function next(refs){
      console.log(''next: i: '' + i);
      
      let item = items[i++];
      
      if (!item){
        console.log(''Item undefined, pushing to stack: callback'');
        iterativeProcess.stack.push([''callback'', callback, [], refs]);
        
      } else {
        console.log(''Item defined, pushing to stack: item'');
        iterativeProcess.stack.push([''item'', item, [next], refs]);
      }
    }
      
    console.log(''asynca: pushing to stack: next'');
    iterativeProcess.stack.push([''next'', next, [], refs]);
  },

  async1a: function(refs, callback) {
    // Some stuff...
    setTimeout(function(){
      if (true) {
        var items = [
          async.async2a,
          // ...
        ]
  
        console.log(''async1a: pushing to stack: asynca'');
        iterativeProcess.stack.push([''asynca'', async.asynca, [items, callback], refs]);
        
      } else {
        console.log(''async1a: pushing to stack: callback'');
        iterativeProcess.stack.push([''callback'', callback, [null, true], refs]);
      }
      
      // Since there was a timeout, we have to restart the stack process to simulate
      // another thread
      iterativeProcess.start();
    }, 200)
  },

  async1b: function(refs, callback) {
    // Some stuff...
    setTimeout(function(){
      if (true) {
        var items = [
          async.async2a,
          // ...
        ]
  
        console.log(''async1b: pushing to stack: asynca'');
        iterativeProcess.stack.push([''asynca'', async.asynca, [items, callback], refs]);
  
      } else {
        console.log(''async1b: pushing to stack: callback'');
        iterativeProcess.stack.push([''callback'', callback, [null, true], refs])
      }
      
      // Since there was a timeout, we have to restart the stack process to simulate
      // another thread
      console.log(iterativeProcess.start());
    }, 200)
  },

  async1c: function(refs, callback) {
    // Some stuff...
    setTimeout(function(){
      if (true) {
        var items = [
          async.async2a,
          // ...
        ]
  
        console.log(''async1c: pushing to stack: asynca'');
        iterativeProcess.stack.push([''asynca'', async.asynca, [items, callback], refs]);
        
      } else {
        console.log(''async1c: pushing to stack: callback'');
        iterativeProcess.stack.push([''callback'', callback, [null, true], refs]);
      }
      
      // Since there was a timeout, we have to restart the stack process to simulate
      // another thread
      console.log(iterativeProcess.start());
    }, 200)
  },

  async2a: function(refs, callback) {
    console.log(''async2a: pushing to stack: callback'');
    iterativeProcess.stack.push([''callback'', callback, [], refs]);
  }
}

let iterativeProcess = {
  stack: [],
  currentResult: undefined,
  start: function(){
    // Garbage collector :)
    iterativeProcess.currentResult = undefined

    console.log(''Starting stack process'')
    
    // Used for debugging, to avoid an infinite loop
    let keep_going = 100;
    
    while (iterativeProcess.stack.length && keep_going--){
        let [func_name, func, params, refs] = iterativeProcess.stack.pop();

        console.log(''/npopped: ['' + func_name + '', ['' + params.map(x => typeof x)  + ''], '' + JSON.stringify(refs) + '']'');
        
        params.unshift(refs);
        
        func.apply(func, params);
    }
    
    return ''Stack process done/n/n'';
  }
};

let _items = [
  async.async1a,
  async.async1b,
  async.async1c
  // ...
];

console.log(''Pushing to stack: asynca'');
iterativeProcess.stack.push([''asynca'', async.asynca, [_items, function(){console.log(''/ndone'')}]]);
console.log(iterativeProcess.start());

Emulación de pila de llamadas

No estoy seguro de si tendré tiempo para llegar a esto, pero aquí hay algunas ideas para una plantilla general. Funciones separadas que llaman a otras funciones en funciones más pequeñas relevantes para permitir una pausa en la ejecución, tal vez codificarlas como un objeto con una matriz de operaciones y claves para simular variables locales.

Luego escriba un controlador y una interfaz que puedan distinguir una llamada a otra función (codificada de manera similar si también tiene salidas), coloque el objeto de esa "función" (o marco de pila) en la pila, recordando el lugar de la siguiente instrucción en línea Hay muchas maneras creativas de lograr esto con JavaScript, usando claves de objeto para la "dirección de retorno" de la función llamada, por ejemplo, que el controlador puede conocer.

Como otros han notado aquí, cada función con una llamada a otra función presenta su propio desafío para convertirla en una secuencia iterativa. Pero puede haber muchas funciones que podrían ser susceptibles de dicho esquema, y ​​nos permiten beneficiarnos del control adicional de los límites de ejecución y la secuencia.

Answer 4

Vamos a definir una función simple, junto con nuestros parámetros.

function syncLoop(iterations, process, exit){
    // Body of the function
}

Solo para hablar sobre los params muy rápido;

iterations = the number of iterations to carry out
process    = the code/function we''re running for every iteration
exit       = an optional callback to carry out once the loop has completed

Así que tenemos nuestro shell de función, ahora necesitamos crear una instancia de un índice, y un booleano para realizar un seguimiento de si hemos terminado de bucle o no.

function syncLoop(iterations, process, exit){
    var index = 0,
        done = false;
    // Body of function
}

Ahora podemos hacer un seguimiento de dónde estamos, y si hemos terminado o no (ambos son loops importantes). El booleano done va a ser nuestra forma de comprobar si realmente queremos volver a ejecutar cuando se nos llame.

Correcto, aquí es donde se vuelve un poco más complicado. Vamos a crear un bucle de objeto que en realidad es nuestro objeto de bucle, y vamos a devolverlo para que podamos controlar el bucle desde fuera de la función.

function syncLoop(iterations, process, exit){
    var index = 0,
        done = false;
    var loop = {
        // Loop structure
    };
    return loop;
}

Volveré a esto hace un tiempo. Ok, entonces tenemos nuestro ciclo. ¿Qué es importante tener en un bucle? Bueno, necesitamos una forma de acceder al índice, avanzar en el ciclo y una forma de acabar con el ciclo, así que implementemos estos métodos.

function syncLoop(iterations, process, exit){
    var index = 0,
        done = false,
        shouldExit = false;
    var loop = {
        next:function(){
            if(done){
                if(shouldExit && exit){
                    return exit(); // Exit if we''re done
                }
            }
            // If we''re not finished
            if(index < iterations){
                index++; // Increment our index
                process(loop); // Run our process, pass in the loop
            // Otherwise we''re done
            } else {
                done = true; // Make sure we say we''re done
                if(exit) exit(); // Call the callback on exit
            }
        },
        iteration:function(){
            return index - 1; // Return the loop number we''re on
        },
        break:function(end){
            done = true; // End the loop
            shouldExit = end; // Passing end as true means we still call the exit callback
        }
    };
    return loop;
}

Ok, para hablar de esto un poco;

El loop.next() es nuestro controlador de bucle. Nuestro proceso debe llamar a loop.next() cuando desea completar una iteración y pasar a la siguiente. Básicamente, todo lo que loop.next() hace es volver a llamar a nuestro proceso deseado, a menos que hayamos terminado, en cuyo caso llama a la devolución de llamada final.

La función loop.iteration() simplemente devuelve el índice en el que estamos. La primera inicialización significa que siempre seremos un índice antes de la iteración actual, por lo que devolveremos el índice - 1.

El loop.break() simplemente le dice al ciclo que termine en la iteración actual. Puede pasar un valor opcional para indicar al bucle que finalice de la forma habitual y llamar a la devolución de llamada exit() si lo desea. Esto es útil para bucles que necesitan limpieza después de ellos mismos.

Bien, tenemos la mayoría del cuerpo aquí. Así que comencemos, llamando a loop.next() justo antes de regresar a nuestro ciclo.

function syncLoop(iterations, process, exit){
    var index = 0,
        done = false,
        shouldExit = false;
    var loop = {
        next:function(){
            if(done){
                if(shouldExit && exit){
                    return exit(); // Exit if we''re done
                }
            }
            // If we''re not finished
            if(index < iterations){
                index++; // Increment our index
                process(loop); // Run our process, pass in the loop
            // Otherwise we''re done
            } else {
                done = true; // Make sure we say we''re done
                if(exit) exit(); // Call the callback on exit
            }
        },
        iteration:function(){
            return index - 1; // Return the loop number we''re on
        },
        break:function(end){
            done = true; // End the loop
            shouldExit = end; // Passing end as true means we still call the exit callback
        }
    };
    loop.next();
    return loop;
}

¡Y terminamos! Todo lo que importa ahora es implementar nuestro ciclo y ejecutarlo, así que veamos un ejemplo;

syncLoop(5, function(loop){
    setTimeout(function(){
        var i = loop.iteration();
        console.log(i);
        loop.next();
    }, 5000);
}, function(){
    console.log(''done'');
});

El código anterior simplemente imprime la iteración actual que tenemos con 5 segundos entre cada impresión, luego los registros terminan cuando se completa. Adelante, inténtalo dentro de la consola de tu navegador. También verifiquemos que nuestro loop.break () funcione como se espera.

var myLoop = syncLoop(5, function(loop){
    setTimeout(function(){
        var i = loop.iteration();
        console.log(i);
        loop.next();
    }, 5000);
}, function(){
    console.log(''done'');
});

setTimeout(myLoop.break, 10000);

En este escenario, deberíamos ver solo las primeras dos iteraciones impresas antes de que termine el ciclo. Como no estamos pasando un valor booleano a myLoop.break (), no se está cerrando. Podríamos cambiar esto usando lo siguiente:

setTimeout(function(){
    myLoop.break(true);
}, 10000);

Una cosa importante a tener en cuenta es que no se puede matar un bucle (limpiamente) mientras que en la ejecución media, esperará hasta que se complete la iteración actual (lo que en realidad tiene mucho sentido). Solo pondrá en cola la ruptura para el inicio de la siguiente iteración, que está marcada en loop.next ().