¿Detecta recursión infinita?

Question

supongamos que tengo una función que se arrastra sobre una gran variedad ...

flatten([a, b, c, d, [e, f, g, [h, i, j, k], l], m, n, o, p]) 
>> [a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p] 

Aplanar se arrastraría sobre el código y para cada matriz se encuentran de forma recursiva entrar en esa matriz y devolver los valores tales que usted tiene un piso formación.

Esto funciona hasta que tengamos una matriz tales como:

a = []; 
a[0] = a; 

Obviamente, esto crea una recursión infinita:

Array[1] 
0: Array[1] 
0: Array[1] 
    0: Array[1] 
    0: Array[1] 
    0: Array[1] 
    0: Array[1] 
     ... 

¿Cómo puedo detectar este comportamiento sin modifiying la matriz de modo que la función se puede tratar ¿con este?

Answer 1

Deberá mantener una serie de arreglos visitados dentro de la función flatten() y verificar su existencia antes de que vuelva a insultarlo. Sin embargo, tendría que pasar la lista de elementos visitados como un segundo parámetro al recurse.

function recurse(ar, visited) { 
    visited = visited || []; 

    function isVisited(obj) { 
     for (var i=0;i<visited.length;i++) { 
      if (visited[i] == obj) { 
       return true; 
      } 
     } 

     visted.push(obj); // but we've visited it now 
     return false; 
    } 

    // blah blah blah, do your thing... check isVisted[i] 
} 

Esto resultará costoso para comprobar si la matriz es profunda, por lo que podría engañar y establecer un atributo de cada matriz se visita, y comprobar por ella (pero entonces, por supuesto, que se está modificando la matriz (pero no dramáticamente)).

function recurse(ar) { 
    function isVisited(obj) { 
     var key = 'visited'; 
     var visited = obj.hasOwnProperty(key); 

     obj[key] = true; // but we've visited it now 

     return visited; 
    } 

    // blah blah blah, do your thing... check isVisted[i] 
} 

Answer 2

Si la detección de la recursividad es un requisito, vas a tener que negociar el espacio de memoria para ello: crear una matriz de objetos que Analizada (los parámetros se envían de forma recursiva) y comprobar cada nuevo parámetro en contra de ella. Si ya lo analizó, regrese inmediatamente.

Answer 3

Una manera conveniente de rastrear arreglos ya visitados sería agregar una propiedad "plana" a cada uno, tal vez estableciendo un valor único para cada operación. No tiene sentido jugar con un mapa por separado cuando cada matriz ya es un objeto perfectamente bueno.

Answer 4

En el mundo real, el paso 1 es encontrar al desarrollador ofensor que le entregó un objeto que se refería a sí mismo y golpearlo con un palo.

El problema se resuelve, sin embargo, eliminándolos como autorreferencias en su lugar. Conviértelos en copias. Array.slice devuelve partes de las matrices (incluidas las copias completas) sin alterar el original.

if(thisElement.constructor.prototype.slice){ //is it an array 
    thisElement = thisElement.slice(0); //now it's a new but identical array 
} 

Tenga en cuenta que esto es solo en la referencia de matriz principal. Las referencias de matrices interiores aún deberán modificarse, ya que una referencia copiada aún apunta a la misma cosa.

Además, si puede hacer suposiciones sobre los personajes que definitivamente no estarán presentes, puede encontrar que cortar/unir es muy útil.

Answer 5

Otra forma más sucia (pero bueno para el mínimo esfuerzo) es apenas utilizar el codificador JSON:

var is_recursive = false; 

try { 
    JSON.stringify(my_recursive_object); 
} catch (e) { 
    if (e.name = 'TypeError') 
     is_recursive = true; 
    else 
     throw e; 
} 

he encontrado esta pregunta en busca de una mejor respuesta, aunque, - aunque esto puede ayudar a alguien que quiera un buen truco ;-)