Returning a value from an asynchronous recursive function

Question

I have a complex recursive function in Node.js, which for the sake of this question I simplified to the following:

function sum(tree) {
    if (!tree) return 0;
    var sumLeft = sum(tree.left);
    var sumRight = sum(tree.right);
    return sumLeft + tree.val + sumRight;
}

var exampleTree = {
    val: 3,
    right: { val: 4 },
    left: { val: 5, 
        right: {val: 6},
        left: {val: 7}
    }
}

console.log(sum(exampleTree)); // returns 25 = 3+4+5+6+7

Now I want to convert the function "sum" to an asynchronous function:

function sumAsync(tree, callback) {
    // ???
}

But, since the function now doesn't return a value, I don't know how to get the values sumRight and sumLeft and combine them.

One possible option is to totally rewrite the algorithm such that it is iterative and not recursive (as suggested in this question: how to make this synchronous recursive function asynchronous). But, in many cases this might be very complicated and make the entire program unreadable. Is there a solution that keeps the simple structure of the recursive function, while making it asynchronous?

NOTE: My problem is not to sum the values in a tree... the tree-sum function is only a Minimal Working Example.

EDIT: Based on vkurchatkin's answer and comment, I decided to use async.parallel. This is the result:

var async = require("async");


function sumAsync (tree, callback) {
    if (!tree) return setImmediate(callback.bind(null, null, 0));

    async.parallel([
      sumAsync.bind(this, tree.left),
      sumAsync.bind(this, tree.right),
    ],
    function(err, results) {
        callback(err, tree.val+results[0]+results[1]);
    });
}

sumAsync(exampleTree, function(err, result) {
    console.log(result);  // prints 25
});

did you try to keep passing the the callback, and when you reach the end of the tree structure just call it. Although asynchronous behavior for parsing this tree just looks a bit too much.. — Gntem, Mar 24 '14 at 07:38

vkurchatkin · Accepted Answer · 2014-03-25T06:04:33.623

Something like this might work:

function sumAsync (tree, callback) {
    if (!tree) return setImmediate(callback.bind(null, null, 0));

    var pending = 3;
    var sum = 0;
    var done = false;

    function handleError (err) {
       if (!done) {
          callback(err);
          done = true;
        }
    }

    function _callback (err, res) {
      if (err) return handleError(err);

      sum += res;

      if (!--pending && !done) {
        done = true;
        callback(null, sum);
      }
    }

    tree.fetchLeft(function (err, left) {
      if (err) return handleError(err);

      sumAsync(left, _callback);
    });

    tree.fetchRight(function (err, right) {
      if (err) return handleError(err);

      sumAsync(right, _callback);
    });

    tree.fetchValue(_callback);
}

it might look complex, but it's actually just an ad-hoc async.parallel implementation, so you can just use it instead.

Thanks, I decided to use async.parallel. Why do you need the setImmediate at the first line? — Erel Segal-Halevi, Mar 25 '14 at 06:17
http://blog.izs.me/post/59142742143/designing-apis-for-asynchrony here is the rationale. You can also use `process.nextTick`, but it has a weird and sometimes unsafe behaviour. — vkurchatkin, Mar 25 '14 at 07:02

Gntem · Answer 2 · 2014-03-24T10:24:41.050

0

assuming that the tree structure is there from the beginning and not fetched piece by piece (which i consider a very bad practice to do this).

var exampleTree = {
    val: 3,
    right: { val: 4 },
    left: { val: 5, 
        right: {val: 6},
        left: {val: 7}
    }
}

function sum(tree,callback){
 if(!tree){ 
  if(callback!==undefined){ return callback(0); }
  return 0;
 }
 var sumLeft=sum(tree.left);
 var sumRight=sum(tree.right);
 var v = sumLeft+tree.val+sumRight;

 // callback is **not** passed so we continue
 if(callback===undefined){
  return v;
 }else{ // callback is passed meaning this is the root, end this.
  return callback(v);
 }
};

sum(null,function(result){
  console.log(result); // logs 0
});

sum(exampleTree,function(result){
    console.log(result); // logs 25
});

console.log(sum(exampleTree)); // logs 25

edited Mar 24 '14 at 10:24

answered Mar 24 '14 at 10:15

Gntem

6,949
2
35
48

Thanks. This solution has the advantage that it can run both asynchronously and synchronously. On the other hand, it has the disatvantage that it is not fully asynchronous - all work is done in a single step without yielding. So, if the tree is very large, it might halt the event queue for a long time. – Erel Segal-Halevi Mar 25 '14 at 06:26
actually i think no, it will consume the same memory but it won't wait for the function to complete, so in queue were concurrency is more than high it will run in parallel and it will process other tasks until this one returns – Gntem Mar 25 '14 at 06:55

Returning a value from an asynchronous recursive function

2 Answers2