Обнаружить бесконечную рекурсию? - PullRequest
Новая
       9

Обнаружить бесконечную рекурсию?

7 голосов
/ 08 марта 2012

Предположим, у меня есть функция, которая сканирует массив ... 

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]

Flatten будет сканировать код и для каждого найденного массива будет рекурсивно вводить этот массив и возвращать значения, чтобы у вас был плоский массив.

Это работает, пока у нас не появится массив, такой как: 

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

Это, очевидно, создает бесконечную рекурсию: 

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

Как я могу обнаружить это поведение без модификации массива так, чтобы функция могла справиться с этим?

Ответы [ 5 ]

5 голосов
/ 08 марта 2012

Если обнаружение рекурсии является требованием, вам придется обменять на нее пространство памяти: создайте массив проанализированных вами объектов (параметры, которые вы отправляете рекурсивно) и проверьте каждый новый параметр по нему. Если вы уже проанализировали его, немедленно вернитесь.

2 голосов
/ 08 марта 2012

Удобный способ отследить уже посещенные массивы - добавить к каждому «плоское» свойство, возможно, присвоив ему уникальное значение для каждой операции.Нет смысла возиться с отдельной картой, когда каждый массив уже является совершенно хорошим объектом.

2 голосов
/ 08 марта 2012

Вам нужно будет сохранить массив посещенных массивов в функции flatten() и проверить их существование там, прежде чем вы проклянетесь в него.Вы должны будете передать список посещенных элементов в качестве второго параметра в 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]
}

Это станет дорогостоящим, чтобы проверить, является ли ваш массив глубоким, так что вы можете обмануть и установить атрибутна каждом массиве, который вы посещаете, и проверяете его (но затем, конечно, вы модифицируете массив (но не кардинально)). 

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]
}
1 голос
/ 24 апреля 2012

Другой, более грязный способ (но подходящий для минимальной суеты) - просто использовать кодировщик JSON: 

var is_recursive = false;

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

Я нашел этот вопрос в поисках лучшего ответа, хотя это может помочь кому-то, желающему хорошего взлома; -)

0 голосов
/ 08 марта 2012

В реальном мире шаг 1 состоит в том, чтобы найти разработчика-нарушителя, который вручил вам объект, ссылающийся на себя, и ударил его палкой.

Однако проблема решается путем устранения их как самостоятельных.ссылки на месте.Превратите их в копии.Array.slice возвращает части массивов (включая полные копии) без изменения оригинала. 

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

Обратите внимание, что это только для самой ссылки на основной массив.Внутренние ссылки на массивы все равно необходимо будет изменить, поскольку скопированная ссылка все еще указывает на одно и то же.

Кроме того, если вы можете делать предположения о символах, которых определенно не будет, вы можете найти срез / соединение сбыть очень полезным.

...