Рекурсия с помощью setImmediate()

Question

У меня есть следующая рекурсивная функция:

 function explore(v, componentN) {
    return function () {
        nodes[v].visited = true;
        nodes[v].componentNumber = componentN;
        preVisit(v);
        adjList[v].forEach((item) => {
            if (!nodes[item].visited){
                ex(item, componentN)
            }
        });
        postVisit(v);
        return nodes;
    }
}
function ex(item, com){
    trampoline(function () {
        return explore(item, com)
    })
}
function trampoline(fn) {
    while(fn && typeof fn === 'function') {
        fn = fn()
    }
}

Я хочу использовать setImmediate() во избежание проблем переполнения стека (это должно быть реализовано таким образом, а не в итеративном подходе). Однако, когда я выполняю эту функцию, я получаю массив res только с первым элементом, в то время как я заполняю его всеми элементами, если не использую setImmediate() и такая же ситуация возникает, когда я использую nextTick() (Я заранее знаю, сколько там должно быть элементов). Что я делаю не так и как я могу правильно реализовать эту функцию (или аналог) здесь?

Это explore() функционировать перед применением батута

function explore(v, componentN) {
    nodes[v].visited = true;
    nodes[v].componentNumber = componentN;
    preVisit(v);
    adjList[v].forEach((item) => {
        if (!nodes[item].visited){
            explore(item, componentN)
        }
    });
    postVisit(v);
    return nodes;
}

Он принимает два аргумента: v это индекс в nodes массив, какой элемент должен быть исследован и componentN который просто счетчик компонентов в графе. explore() ничего не возвращает, просто меняет состояние объекта в массиве nodes под v ключ от неизведанного к исследованному. Основная проблема в том, что две функции preVisit(v) а также postVisit(v) также измените состояние этого объекта - порядок записи, в котором он был посещен в первый и второй раз (при отображении стека из предыдущих вызовов) соответственно. Когда я обратился explore() с батута они начали писать неожиданные и неправильные результаты.

Функция вызывается в другой функции следующим образом:

for (let i = 0; i < vNum; i++) {
        if (nodes[i].visited) continue;
        explore(i, cN);
        cN++;
    }

И две функции postVisit а также preVisit

function preVisit(v){
    nodes[v].preVisit = visitCounter;
    visitCounter++;
}
function postVisit(v) {
    nodes[v].postVisit = visitCounter;
    visitCounter++;
}

Answer 1

Допустим, у нас есть обычная рекурсивная функция, подобная этой, - проблема в том, что мы имеем forEach цикл, где каждый вызов explore может выдать 0, 1 или более дополнительных звонков explore - Чтобы это исправить, нам понадобится какой-то способ упорядочить все узлы так, чтобы мы могли обрабатывать их один за другим, не разрушая стек

const explore = node =>
  {
    node.visited = true
    preVisit (node)
    Array.from (node.adjacencies)
      .filter (n => n.visited === false)
      .forEach (n => explore (n))
    postVisit (node)
  }

Мы вводим основной цикл внутри explore функция, которая обрабатывает массив узлов, а не только один узел. Цикл будет продолжать работать, пока в массиве есть узлы. Рекурсивные вызовы будут выполняться для функции внутреннего цикла вместо внешнего explore функция. Этот подход с массивами работает хорошо, потому что каждый узел имеет неоднозначное количество смежностей - когда можно легко добавить 0, 1 или более смежных узлов в этот список - также обратите внимание на продолжение k добавлено, поэтому у нас есть способ упорядочить вызовы postVisit в правильном порядке

Наиболее важным является рекурсивный вызов loop находится в хвостовой позиции - что готовит нас к следующей трансформации

const explore = node =>
  {
    const loop = ([x, ...xs], k) =>
      {
        if (x === undefined)
          k ()
        else {
          x.visited = true
          preVisit (x)
          loop (
            Array.from (x.adjacencies)
              .filter (n => n.visited === false)
              .concat (xs),
            () => (postVisit (x), k ())
          )
        }
      }
    return loop ([node], x => x)
  }

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

const recur = (...values) =>
  ({ type: recur, values })

const loop = f =>
  {
    let acc = f ()
    while (acc && acc.type === recur)
      acc = f (...acc.values)
    return acc
  }

const explore = $node =>
  loop (([x,...xs] = [$node], k = x => x) => {
    if (x === undefined)
      return k ()
    else {
      x.visited = true
      preVisit (x)
      return recur (
        Array.from (x.adjacencies)
          .filter (n => n.visited === false)
          .concat (xs),
        () => (postVisit (x), k ())
      )
    }
  })

// for completion's sake
let visitCounter = 0

const preVisit = node =>
  node.preVisit = visitCounter++

const postVisit = node =>
  node.postVisit = visitCounter++