Asynchronous Recursion in Node.js

Question

I have the following recursive function in node.js that works properly to search and return all the child, grandchild, etc. nodes of a parent node. However, when the function to get children does not return immediately, the recursion breaks and returns an empty list. How can I modify the following function to properly work in an asynchronous environment?

Functioning Properly:

// My "database"
var nodes_collection = [
  {id:"id1",name:"name1",parentid:"."},
  {id:"id2",name:"name2",parentid:"id1"},
  {id:"id3",name:"name3",parentid:"id1"},
  {id:"id4",name:"name4",parentid:"id2"},
  {id:"id5",name:"name5",parentid:"id3"},
  {id:"id6",name:"name6",parentid:"id3"},
  {id:"id7",name:"name7",parentid:"id5"},
  {id:"id8",name:"name8",parentid:"id7"},
  {id:"id9",name:"name9",parentid:"id7"},
  {id:"id10",name:"name10",parentid:"id9"},
  ];

// This is NOT a real function, but rather simulates retrieving the data from my database.
function getChildren(parentid, callback){
 
  var children = [];
  for(var i=0; i < nodes_collection.length; i++){
   if(nodes_collection[i].parentid == parentid){
    children.push(nodes_collection[i].id);
   }
  }
  callback(children);
 
}



function allDescendants(parentid, callback) {
  let result = [];
  
  let go = function(children){
    for (child of children){
      result.push(child);
      getChildren(child, go)
    }
  }
  
  getChildren(parentid, go);
  
  callback(result);
}


allDescendants("id3", function(result){
  console.log('result: ' + JSON.stringify(result));
});

NOT Functioning Properly process.NextTick added to not return immediately

// My "database"
var nodes_collection = [
  {id:"id1",name:"name1",parentid:"."},
  {id:"id2",name:"name2",parentid:"id1"},
  {id:"id3",name:"name3",parentid:"id1"},
  {id:"id4",name:"name4",parentid:"id2"},
  {id:"id5",name:"name5",parentid:"id3"},
  {id:"id6",name:"name6",parentid:"id3"},
  {id:"id7",name:"name7",parentid:"id5"},
  {id:"id8",name:"name8",parentid:"id7"},
  {id:"id9",name:"name9",parentid:"id7"},
  {id:"id10",name:"name10",parentid:"id9"},
  ];

// This is NOT a real function, but rather simulates retrieving the data from my database asynchronously.
function getChildren(parentid, callback){
 
 process.nextTick(function(){
  var children = [];
  for(var i=0; i < nodes_collection.length; i++){
   if(nodes_collection[i].parentid == parentid){
    children.push(nodes_collection[i].id);
   }
  }
  callback(children);
 })
 
}



function allDescendants(parentid, callback) {
  let result = [];
  
  let go = function(children){
    for (child of children){
      result.push(child);
      getChildren(child, go)
    }
  }
  
  getChildren(parentid, go);
  
  callback(result);
}


allDescendants("id3", function(result){
  console.log('result: ' + JSON.stringify(result));
});

Answer 1

recursion is a functional heritage

Recursion is a concept that comes from functional style. Mixing it with imperative style is a source of much pain and confusion for new programmers.

Here's a tail-recursive way to do it. Note, setTimeout and process.nextTick are not necessary for asynchronous recursion – read more here

By implementing our function this way, all pain and suffering are removed from the program. We do not have to concern ourselves with intermediate assignments, manually incrementing array iterators or checking array length, or even localized side effects like for or .push.

const Empty =
  Symbol ()

const identity = x =>
  x

const allDescendants = (match = '.', list = [], callback = identity) =>
{
  const loop = (match, [ first = Empty, ...rest], k) =>
  {  
    // no first item
    if (first === Empty)
      return k ([])
    
    // first item is a match
    else if (first.parentid === match)
      return loop (match, rest, children =>
               loop (first.id, list, grandChildren =>
                 k ([ first, ...children, ...grandChildren ])))
                 
    // default: first item does not match
    else
      return loop (match, rest, k)
  }        
  return loop (match, list, callback)
}

const data =
  [ { id : "id1", name : "name1", parentid : "." }
  , { id : "id2", name : "name2", parentid : "id1" }
  , { id : "id3", name : "name3", parentid : "id1" }
  , { id : "id4", name : "name4", parentid : "id2" }
  , { id : "id5", name : "name5", parentid : "id3" }
  , { id : "id6", name : "name6", parentid : "id3" }
  , { id : "id7", name : "name7", parentid : "id5" }
  , { id : "id8", name : "name8", parentid : "id7" }
  , { id : "id9", name : "name9", parentid : "id7" }
  , { id : "id10", name : "name10", parentid : "id9" }
  ]

allDescendants ('id3', data, console.log)
// [ { id: 'id5', name: 'name5', parentid: 'id3' }
// , { id: 'id6', name: 'name6', parentid: 'id3' }
// , { id: 'id7', name: 'name7', parentid: 'id5' }
// , { id: 'id8', name: 'name8', parentid: 'id7' }
// , { id: 'id9', name: 'name9', parentid: 'id7' }
// , { id: 'id10', name: 'name10', parentid: 'id9' }
// ]

Instead of making getChildren and allDescendants two separate functions, why not just make one function getDescendants and give it a depth parameter? Alternative syntax styles can greatly improve readability of functional programs in JavaScript. Note, even return can be removed if you're only using the value in the callback; optionally keep return if you want getDescendants to have a return value too

const getDescendants = (depth = 1, match = '.', list = [], callback = identity) =>
{
  const loop = (depth, match, [ first = Empty, ...rest ], k) =>
  { 
    // no first item
    if (first === Empty)
      k ([])

    // first item is a match
    else if (first.parentid === match)
      loop ( depth
           , match
           , rest
           , children =>
               depth <= 1
                 ? k ([ first, ...children ])
                 : loop ( depth - 1
                        , first.id
                        , list
                        , grandChildren =>
                            k ([ first, ...children, ...grandChildren ])
                        )
           )

    // default: first item does not match 
    else
      loop ( depth
           , match
           , rest
           , k
           )
  }
  // begin the loop
  loop ( depth
       , match
       , list
       , callback
       )
}

Now use it by specifying the depth first

getDescendants (1, 'id3', data, console.log)
// [ { id: 'id5', name: 'name5', parentid: 'id3' }
// , { id: 'id6', name: 'name6', parentid: 'id3' }
// ]

getDescendants (2, 'id3', data, console.log)
// [ { id: 'id5', name: 'name5', parentid: 'id3' }
// , { id: 'id6', name: 'name6', parentid: 'id3' }
// , { id: 'id7', name: 'name7', parentid: 'id5' }
// ]

getDescendants (Infinity, 'id3', data, console.log)
// [ { id: 'id5', name: 'name5', parentid: 'id3' }
// , { id: 'id6', name: 'name6', parentid: 'id3' }
// , { id: 'id7', name: 'name7', parentid: 'id5' }
// , { id: 'id8', name: 'name8', parentid: 'id7' }
// , { id: 'id9', name: 'name9', parentid: 'id7' }
// , { id: 'id10', name: 'name10', parentid: 'id9' }
// ]

Or if you still like the two separate functions, implement them as a specializations of the generic form

const getChildren = (match, items, callback) =>
  getDescendants (1, match, items, callback)

const allDescendants = (match, items, callback) =>
  getDescendants (Infinity, match, items, callback)

Answer 2

Use promises. Configure your getChildren function so that it returns a promise. Promises allow you to handle non-blocking results of an asynchronous function. In the success block of the promise, known as "then", you can place another recursive call.

Example

function getChildren(){
    var promise = new Promise((resolve,reject)=>{
         domakeDatabaseCall(function(){

           //Handle logic processing database result           
           resolve(getChildren()) // call again when done
         })
    })

    return promise
}

More info -> https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Using_promises