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

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 repeat ov и снова и снова. Единственная причина, по которой он остановился на 5 глубинах, - это проверка if (iter < 5). Если предел не был там, он бы возобновил [sic?] Навсегда. Предел итерации помогает, но что, если есть критическая функция? По сути, я понятия не имею, что я должен сделать для этого предела итерации, или если он вообще должен быть.

Вместо этого я думаю, что должен быть какой-то алгоритм, который может предотвратить бесконечную рекурсию. Существует ли такой алгоритм? Или я должен изменить, как я иду обходить 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);  
} 

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

редактировать — Кроме того, еще один вопрос (присутствует в исходном коде тоже) в том, что это действительно необходимо проверить, чтобы увидеть, если значения «OBJ» действительно объекты. Если они скаляры, то нет смысла ничего делать. Вам нужно просто выполнить проверку «typeof» сразу после проверки маркера, и если вы увидите нуль, число, строку или логическое значение, просто вернитесь.

Answer 2

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

Answer 3

Сборка ответа Pointy (в идеале это будет комментарий, но, увы, код в них не работает), лучшим решением может быть просто передать объект функции рекурсии, которая будет отслеживать объектов, которые вы уже видели. Что-то вроде этого:

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 хотите увидеть унаследованные атрибуты.

Answer 4

Если я чего-то не упускаю, все, что вам нужно сделать, это пропустить строки (если вы используете современный браузер, который позволяет индексировать строки, в противном случае это не имеет значения) и функцию 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); 
    } 
}