Entonces, aquí hay una solución de muestra para resolver el problema de aplanar una matriz. Mi pregunta no es 'cómo' aplanar la matriz. Más bien, estoy tratando de entender algunas funciones subyacentes que ocurren en esta recursión.

Esta solución pasa a través de cada elemento de la matriz original, desglosando los elementos que son matrices volviéndolos a poner a través de la función hasta que ya no sean matrices y puedan insertarse en la nueva matriz.

Mi pregunta es, ¿cómo realiza el ciclo 'for' un seguimiento de todas las veces que un elemento se devuelve a través de la función, y también continúa recorriendo el resto de la matriz 'original' en la que está trabajando en ese momento? Debe estar realizando un seguimiento de alguna manera; de lo contrario, cada vez que un elemento sea una matriz y se vuelva a colocar, el bucle actual se acortará. Espero que mi pregunta tenga sentido.

function steamrollArray(array) {
  var flatArray = [];

  flatten(array);

  function flatten(array) {
    for (var i = 0; i < array.length; i++) {
      if (Array.isArray(array[i])) {
        flatten(array[i]);
      } else {
        flatArray.push(array[i]);
      }
    }
  }

  return flatArray;
}
steamrollArray([1, [2], [3, [[4]]]]);
3
Alfonso Giron 9 may. 2016 a las 02:17

5 respuestas

La mejor respuesta

Creo que habrá mejores respuestas, pero aquí va ...

Como mínimo, no piense que es "romper" el ciclo, piense que continúa ejecutando código en un orden de procedimiento. Entonces, desde el contexto del bucle, se llama a sí mismo como una función, cuando esa función se ha completado, continúa en el bucle. Ejemplo

var item = [1, [2, 3], 4]

La ejecución de flatten(item) sería:

Loop 1: 
  Push 1
Loop 2: 
  Start a call to flatten with [2, 3]
  Loop 1: 
    push 2
  Loop 2: 
    push 3
  End loop
Loop 3: 
  Push 4
End Loop.

Entonces el punto es, simplemente está ejecutando un procedimiento de pasos. No es tener que "recordar" dónde estaba, cuando una función regresa, JavaScript simplemente continúa procesando desde donde se llamó a la función.

Es posible que desee revisar pilas de llamadas.

3
Dan 8 may. 2016 a las 23:34

La matriz de resultados flatArray está en el cierre léxico de la función auxiliar y, por lo tanto, el elemento que no son matrices en sí mismas se empuja a esto y el orden en que se colocan en el resultado está en el orden en que se iteran.

Cuando uno de los elementos es una matriz, llama a flatten(array[i]), que aplana los elementos de ese elemento antes de regresar. Al igual que con todas las funciones, la ejecución de una instrucción debe finalizar antes de que se pueda realizar la siguiente instrucción y llamar a una función no cancela la función actual. Se reanuda y continúa hasta el final o una declaración return.

Imagina esta función:

function test () {
  console.log("hello, ");
  console.log("world!");
}

Cuando esto se llama, espera hasta que todo console.log("hello, ") haya terminado antes de hacer la declaración dos (console.log("world!")). Si fuera una llamada recursiva, esa llamada debe finalizar antes de hacer la declaración dos. Funciona igual para todas las llamadas a funciones, no solo las recursivas.

2
Sylwester 8 may. 2016 a las 23:35

Tengo una solución más simple que funciona con cualquier nivel de anidamiento en la matriz.

function flattenArray(arr){

  for(var i=0;i<arr.length;i++){

    if(arr[i] instanceof Array){

      Array.prototype.splice.apply(arr,[i,1].concat(arr[i]))
       i--;
    }

  }

  return arr;
}
0
Pratik Barasia 20 jun. 2017 a las 22:44

En realidad, no pone elementos 'atrás' a través de la función que solo ocurre una vez. Comprueba si un elemento es una matriz y luego recorre esa matriz.

Si no es una matriz, la empuja a flatArray. La recurrencia aquí es que si algún elemento es una matriz, pasa por la función de aplanar. Entonces, si esa matriz tiene un elemento que es una matriz, ESE elemento se envía a flatten y así sucesivamente.

Tomemos el siguiente ejemplo: [1, [2], [3, [[4]]]]

Comenzamos a hacer bucles->

  • El índice 0 es 1 y no una matriz, por lo que se envía a flatArray
  • el índice 1 es una matriz y, por lo tanto, recurrimos, ya que tenemos un 2, que luego se empuja
  • El índice 2 es una matriz, por lo que repetimos, el índice 0 de esa matriz interna no es una matriz 3, por lo que se empuja. Luego tenemos ese último índice - una matriz, en la que recurrimos, para encontrar otra matriz - recurse nuevamente - finalmente llegamos al 4, que empujamos.
1
omarjmh 8 may. 2016 a las 23:27

El "seguimiento" de cada paso de recursión ocurre de la misma manera que funciona cualquier otra llamada al método; el motor de JavaScript realiza un seguimiento de las variables y los ámbitos cada vez que se llama a un nuevo método en la pila de llamadas.

Para su ejemplo específico, quizás sea más fácil ver lo que sucede cuando la función flatten ya no está anidada.

function steamrollArray(array) {
  var flatArray = [];
  flatten(array, flatArray);
  return flatArray;
}

function flatten(array, flatArray) {
  flatArray = flatArray || [];

  for (var i = 0; i < array.length; i++) {
    if (Array.isArray(array[i])) {
      flatten(array[i]);
    } else {
      flatArray.push(array[i]);
    }
  }
}

steamrollArray([1, [2], [3, [[4]]]]); # [1, 2, 3, 4]

Se requirieron algunas modificaciones leves ya que la función flatArray ya no es accesible para la función flatten. Pero los mods hacen que steamrollArray parezca superfluo ... vamos a deshacernos de él.

function flatten(array, flatArray) {
  flatArray = flatArray || [];

  for (var i = 0; i < array.length; i++) {
    if (Array.isArray(array[i])) {
      flatten(array[i], flatArray);
    } else {
      flatArray.push(array[i]);
    }
  }

  return flatArray;
}

flatten([1, [2], [3, [[4]]]]);  # [1, 2, 3, 4]

Ahora es un poco más obvio dónde y cómo está ocurriendo la recursión. Cada vez que se 'descubre' una matriz, también se aplana. Los valores se transfieren a una nueva matriz o se transfieren a la matriz aprobada como segundo parámetro. Cada vez que se llama a flatten dentro del bucle for, la matriz en la posición i se aplana y se empuja hacia flatArray. Como flatArray también se pasa a la función flatten de forma recursiva, todos los valores se recopilarán en esa matriz.

1
br3nt 9 may. 2016 a las 00:19