Wednesday 1 November 2017

Async Recursion

For no particular reason the other day it came to my mind how recursion and asynchrony played together. I've played with some examples and I'm putting them here.

Let's just start with the synchronous, recursive version:

function syncOperation(item){
 return item * item;
}

function recursiveCalculation(items){
 if (items.length == 0){
  return 0;
 }
 
 let curItem = items.shift();
 return syncOperation(curItem) + recursiveCalculation(items);
}

let items = [5, 4, 8];
console.log("result:" + recursiveCalculation(items));

Next the function becomes asynchronous and will invoke a callback function once it's finished. This is similar to asynchronous loops where in the callback you invoke a function that will launch the next iteration of the loop. Here in the callback we invoke a function that will launch the next recursive call.

function asyncOperation(item, callback){
 console.log("asyncOperation");
 setTimeout(function(){
  let res = item * item;
  callback(res);
 }, 1000);
}




function bootStrapRecursion(items, endCallback){
 let result = 0;
 let processItems = (items, newResult) => {
  result += newResult;
  if (items.length == 0){
   endCallback(result);
  }
  else{
   let curItem = items.shift();
   asyncOperation(curItem, newResult => {
    processItems(items, newResult);
   });
    
  }
 };
 processItems(items, 0);
}

let items = [5, 4, 8];
bootStrapRecursion(items, function(result){
 console.log("async result: " + result);
});

Now We move into the modern world, the asynchronous function returns a Promise rather than invoking a callback.

function promisifiedAsyncOperation(item){
 return new Promise((resolve, reject) => asyncOperation(item, resolve));
}

I've come up with 2 ways of using it. Either we return a Promise that we will resolve from the end condition of the recursion


function bootStrapPromisifiedRecursion(items){
 return new Promise((resolve, reject) => {
  let result = 0;
  let processItems = (items, newResult) =>{
   result += newResult;
   if (items.length == 0){
    resolve(result);
   }
   else{
    let curItem = items.shift();
    promisifiedAsyncOperation(curItem).then((newResult) => processItems(items, newResult));
     
   }
  };
  processItems(items, 0);
 });
}

 let items = [5, 4, 8];
 bootStrapPromisifiedRecursion(items).then(result => console.log("promisified result: " + result));

Or we do Promises nesting


function bootStrapPromisifiedRecursion2(items){
 let result = 0;
 let processItems = (items, newResult) =>{
  result += newResult;
  if (items.length == 0){
   return Promise.resolve(result);
  }
  else{
   let curItem = items.shift();
   return promisifiedAsyncOperation(curItem).then((newResult) => processItems(items, newResult));
    
  }
 };
 return processItems(items, 0);
}
let items = [5, 4, 8];
bootStrapPromisifiedRecursion2(items).then(result => console.log("promisified result: " + result));

Finally, we move into next generation javascript using the async/await magic words. This way the code looks almost the same as in the non asynchronous initial sample


async function recursiveCalculationAsyncAwait(items){
 if (items.length == 0){
  return 0;
 }
 
 let curItem = items.shift();
 let auxRes = await promisifiedAsyncOperation(curItem);
 return (await recursiveCalculationAsyncAwait(items)) + auxRes; 
}

async function runAsyncAwait(){
 let items = [5, 4, 8];
 let result = await recursiveCalculationAsyncAwait(items);
 console.log("async/await result: " + result);
}
runAsyncAwait();

One important point to bear in mind is that with asynchronous recursive calls we won't have stack overflow issues whatever deep our recursion is. Being asynchronous we are not pushing frame after frame in the stack. The asynchronous call returns immediatelly and the stack frame is released.

No comments:

Post a Comment