recursion with setImmediate()

Question

I have the following recursive function:

 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()
    }
}

I want to use setImmediate() in order to avoid stack overflow issues (it should be implemented in this way and not in the iterative approach). However, when I execute this function I get array res only with the first one element, while I get it full of all elements if I don't use setImmediate() and the same situation appears when I use nextTick() (I know in advance how many elements should be there). What am I doing wrong and how can I implement this function (or analog) properly here?

This is explore() function before applying trampoline

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;
}

It accepts two arguments: v is an index in nodes array which element is supposed to be explored and componentN which is just a counter of components in a graph. explore() does not return anything, it just changes the state of an object in the array nodes under the v key from unexplored to explored. The main problem is that two functions preVisit(v) and postVisit(v) also change the state of that object - write order on which it was visited for the first time and the second time (when popping up stack from the previous calls) respectively. When I converted explore() with trampoline, they began to write unexpected and wrong results.

The function is being called in another function in this way:

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

And two function postVisit and preVisit

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

Answer 1

Let's say we have an ordinary recursive function like this – the problem here is we have a forEach loop where each call to explore can yield 0, 1, or more additional calls to explore – To fix this, we'll need some way to sequence all of the nodes such that we can process them one-by-one without blowing up the stack

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

We introduce a main loop inside the explore function which processes an array of nodes, instead of just a single node. The loop will continue to run while there are nodes in the array. Recursive calls will be made to the inner loop function instead of the outer explore function. This array approach works nicely because each node has an ambiguous amount of adjacencies – when can easily add 0, 1, or more adjacent nodes to this list – also note the continuation k is added so we have a way to sequence the postVisit calls in the correct order

Of most primary importance tho is the recursive call to loop is in tail position – which prepares us for the next transformation

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)
  }

Once we have a tail-recursive loop, we can introduce loop/recur for stack-safe recursion

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++