Как предотвратить бесконечную рекурсию

Question

Я пытаюсь рекурсивно распечатать содержимое jQuery . Я планирую использовать это для анализа существующего экземпляра jQuery (загруженного на странице) по небольшой базе данных известных «сигнатур jQuery», чтобы определить, какие изменения были внесены (т.е. какие плагины были загружены, функции изменены и т. Д.). .).

Для этого у меня есть небольшая функция:

function recurse(obj, iter){
    var padding = (new Array(iter + 1)).join("  ") + ">";

    for (var i in obj){
    document.writeln(padding + i + "<br/>");

    if (iter < 5)
        recurse(obj[i], iter + 1);
    }
}

Когда я выполню это:

recurse(jQuery, 1);

Я получаю что-то вроде этого:

  >prototype
    >init
      >prototype
        >init
          >prototype
        >selector
        >jquery
          >0

.... On and on and on .....

Моя проблема в том, что в самом начале вы можете видеть, что prototype и затем init повторяются снова и снова. Единственная причина, по которой он остановился на глубине 5 - это проверка if (iter < 5). Если бы не было предела, он бы повторился [так?] Навсегда. Предел итерации помогает, но что, если есть критическая функция 6 глубоко? По сути, я понятия не имею, что я должен сделать этот предел итерации, или если он вообще должен быть.

Вместо этого я думаю, что должен быть какой-то алгоритм, который может предотвратить бесконечную рекурсию. Существует ли такой алгоритм? Или я должен изменить способ обхода jQuery? Спасибо,

Answer 1

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

function recurse(obj) {
  var marker = '__' + new Date().getTime() + '__';
  function r(obj, iter) {
    if (marker in obj) return;

    var padding = (new Array(iter + 1)).join("  ") + ">";
    obj[marker] = true;

    for (var i in obj) {
      if (!obj.hasOwnProperty(i) || i === marker) continue;

      document.writeln(padding + i + "<br/>");

      recurse(obj[i], iter + 1);
    }
  }
  r(obj, 0);      
}

Теперь у этого, конечно, есть недостаток, заключающийся в том, что ваш пройденный граф объектов засоряетсядополнительные свойства, но для некоторых приложений это не будет проблемой.Также использование часов для создания «уникального» маркера действительно хромает;Возможно, вы захотите просто использовать счетчик или просто фиксированную бессмысленную строку.

edit - Кроме того, другая проблема (также присутствующая в исходном коде) заключается в том, что это действительно следует проверятьчтобы увидеть, действительно ли значения obj являются объектами.Если они скаляры, то нет смысла что-либо делать.Вам просто нужно выполнить проверку "typeof" сразу после проверки маркера, и, если вы видите null, число, строку или логическое значение, просто верните.

Answer 2

В вашей рекурсии отсутствует базовый вариант.См. Определение Рекурсия .Вы ввели произвольный базовый случай (depth < 5).Возможно, вместо этого используйте длину массива или, как указал Пинти, проверку hasOwnProperty, чтобы пропустить рекурсивный вызов.

Answer 3

Если я что-то упускаю, все, что вам нужно сделать, это пропустить строки (если вы используете современный браузер, который позволяет индексировать строки, в противном случае это не имеет значения) и функцию init, которая является собственной ссылкой jQuery, котораяты бесконечная рекурсия

function recurse(obj, iter){
    var padding = (new Array(iter + 1)).join("  ") + ">";

    for (var i in obj){
        document.writeln(padding + i + "<br/>");
        if (i != 'init' && typeof obj[i] != 'string') 
            recurse(obj[i], iter + 1);
    }
}

Answer 4

Основываясь на ответе Пойнти (в идеале это был бы комментарий, но, увы, код не очень хорошо работает в них), лучшим решением может быть просто передать объект в функцию recurse, которая будет отслеживать объекты, которые вы уже видели. Примерно так:

var recurse = function(obj)
{
    var seen = {};
    var inner = function(obj, padding)
    {
        for (var i in obj)
        {
            if (!(obj[i] in seen))
            {
                document.writeln(padding + i + '<br />');
                seen[obj[i]] = true;
                inner(obj[i], padding + '  ');
            }
        }
    };
    return inner(obj, '');
};

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

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

Редактировать: Я хотел объяснить это, но забыл. Я не использую hasOwnProperty здесь, потому что в случае печати графа объекта вы, вероятно, do хотите увидеть унаследованные атрибуты.