Recursion to the Rescue in Asynchronous JavaScript

Callbacks within Loops

While callbacks provide capability to serialize execution of code, which is sometimes required in an asynchronous framework that javascript offers (e.g. nodeJS), they can also get daunting very easily. Throw in a loop (such as for-loop or a while-loop) within the callback hell and now it’s a completely elevated level of complexity.

There are already a lot of alternatives to simplify the callback hell. One popular solution is use of Promises. There are also some good discussions on this topic on Quora.

This article is one of such attempt to simplify callbacks that are called within loops (such as for-loop or while-loop). The problem specifically in this case is that if an asynchronous function is called within the loop, each iteration is executed asynchronously. Now, if further processing is required after the entire loop is executed, it becomes difficult to track the last iteration. Why? Because, what if although the last iteration is complete and the one before the last takes longer to return? So, just tracking the last iteration is not good enough!

Before we look at how we can use recursion in this situation as one possible alternative, let’s take a quick dive into Recursion.

A little-bit about Recursion

Divide and conquer is perhaps the most common algorithm used to solve some complex programming problems with optimal efficiency. Recursion is one method under divide and conquer algorithms. Recursion really reduces down a large problem into smaller simpler problems and the idea is that solving each small unit will eventually lead to have solved the larger original problem. Recursion is achieved by writing recursive functions, which we will take a look at in a minute.

Recursive Functions (quick refresher)

To put it simply, a recursive function is one that calls itself and looks for whether a base condition has been reached or not. If not, the problem is chopped down further by calling itself again. Let’s look at an example. In this example, we are going to add numbers between 1 and 10.
Hint: Recursion involves a base case which is the last case in recursive function after which the recursion is complete and the problem has been solved.


var add = function(n, sum) {
if(n<1) {
return sum;
}// base case
else {
sum = sum + n;
n--;
return add(n, sum); // recursive call
} // chop down problem further
}

// calling recursive function
var result = 0; // this is where the final result will be stored
result = add(10,result); // call recursive function

Just take a few minutes to look at where we applied the “Divide” from the Divide & Conquer.

What we did here is that we divided the larger problem of adding all numbers between 1 and 10 into smaller problem of performing only one ‘addition’ operation per function call, meanwhile decrementing the number to be added by 1 before it was passed as a parameter to the subsequent function call.

similarly, at the start of each function call, we determined whether the exit condition was reached, i.e. whether the number in question to be added was less than 1 or not. When the exit condition was reached, we simply returned the result, i.e. sum, back to the main program.

Now, let’s get back to the Solution of the Asynchronous Loop Problem

The Solution via Recursion

Assume a requirement similar to pricing a shopping cart. When a product is added to the shopping cart, we need to do the following for each product in the cart:

  1. Check if the product and quantity is eligible for a promotion. If eligible, price it accordingly, else price as usual.
  2. When all products are priced, calculate the total.
  3. Calculate the tax based on the total.
  4. Finally, calculate the total cost of the shopping cart.

Below is the high level code for achieving the above steps using recursion and callbacks. As mentioned earlier, the challenge is that steps 1 and 2 are performed for each product in the pricing cart, however steps 3 and 4 are computed on the results from steps 1 and 2.


var calculatePrice = function(productid, quantity, callback){
// ... check promotion eligibility
callback(calculated_price);
}

var calculateTotal = function(total, productid, quantity, finalcallback, callback){
// ...
calculatePrice (productid, quantity, function(price){
total = total + price;
callback(total, finalcallback);
});
}

var calculateTax = function(total, tax_rate){
return (total + (total * tax_rate));
}

// And here is the recursive function
function forEachProductInCart(cartIndex, shoppingCart, total, callback){
if(cartIndex < 0) {
callback(total);
} // base case
else {
calculateTotal(total, shoppingCart[cartIndex].productid, shoppingCart[cartIndex].quantity, callback, function(total, callback){
cartIndex--;
forEachProductInCart(cartIndex, shoppingCart, total, callback);
})
}
} // forEachProductInCart: recursive function

/* .....................................................
And we call it here
..................................................... */
// var shoppingCart = [];
// shoppingCart contains all products added to the shopping cart

var subtotal = 0; // initial total cost
var finalTotal = 0; // initial final cost
var cartIndex = shoppingCart.length - 1;

// We call the recursive function here
forEachProductInCart(cartIndex, shoppingCart, subtotal, function(total){
var final_with_tax = calculateTax(total, 0.75); // final with tax
});

Conclusion

JavaScript provides solid asynchronous framework to build highly complex web applications already. It also provides ability to create synchronous execution logic via “callbacks”. Add them up with algorithms like recursions and what you now have is ability to solve any complex computing requirement.

Please feel free to comment, provide feedback or add if anything obvious was missed or if any additional perspective needs to be covered.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s