Javascript Recursion, Variable Scope and Hoisting

One of my most popular posts involved javascript function declarations vs function expressions. On the post, I mentioned something but never went into detail how it works properly. In this post, I’ll try to address it by using an example I encountered recently.

While going through an online javascript quiz, I couldn’t figure out why my code wasn’t passing. The task was returning the sum of all integers when given an array. The array could contain any data, including other arrays. By any means, my solution should have been returning the correct result but it still wasn’t responding the correct way. I had to do some line by line debugging and considering it was a recursion function, things can get tricky. At the end, I was certain the recursion function was the culprit.

My initial solution looked like this:

function arraySum(i) {
 sum = 0;
 for(var x = 0; x<i.length;x++){
  if(typeof i[x] == 'number'){
   sum += i[x];
  }
  else if(i[x] instanceof Array){
   arraySum(i[x]);
  }
 }
 return sum;
}

This one obviously failed and would return the sum of the innermost array. If you tried to run arraySum([1, 2, 3, [4, 5]]), it would return 9 instead of 15. This is seemed obvious due to the return line operating in the recursion function breaking off.

The next solution was the trickiest one to figure what was going wrong:

function arraySum(i) {
 var sum = 0;
 for(var x = 0; x<i.length;x++){
   if(typeof i[x] == 'number'){
   sum += i[x];
  }
  else if(i[x] instanceof Array){
   arraySum(i[x]);
  }
 }
 return sum;
}

This function would only return the sum of the outermost numbers and never include the sum of the inner arrays. If it isn’t obvious yet (it wasn’t obvious to me for about 30 minutes), variable scope was at play. In the original function, due to the order of the conditionals, it would return the correct result if, and only if, the array passed had the innermost array as the first element. If you had 3 or more nested arrays, then the deepest array should always be the first element of the parent array. If you passed arraySum([[4, 5], 1, 2, 3]) in the initial function, it would return 15 which happens to be the expected result.

In the second solution, only the sum of the outermost array would be returned. Both arraySum([1, 2, 3, [4, 5]]) and arraySum([[4, 5], 1, 2, 3]) would return 6. This ruled out the order of the elements and highlighted the variable scope complications present.

Variable scope refers to the extent of the availability of a variable in code. In javascript, variable scope is prominently present in functions. If you declare a variable using var x in some function y(), x will only be available inside the y().

Applying this logic in the second function, it becomes obvious why only the sum of the outermost numbers were the only ones returned. Precisely, refer to the second line in the second function (i.e. var sum = 0). Every recursion function had its own scope of the sum variable. Hence every returned sum value by the inner functions wasn’t available to the outermost function

Taking this into consideration, the final solution looked like this:


function arraySum(i) {
 var sum = 0;
 function sumArr(i){
  for(var x = 0; x<i.length;x++){
   if(typeof i[x] == 'number'){
    sum += i[x];
   }
   else if(i[x] instanceof Array){
    sumArr(i[x]);
   }
  }
 }
 sumArr(i);
 return sum;
}

To avoid the variable scope issues, I opted to employ a closure. It ensured neither the order nor the scope was going to change the final returned value. There are other impressive hacks that avoid using recursion altogether but I opted using a closure to illustrate the problems one might run into when faced with recursion functions.

On a funny somewhat unrelated note, try this in your browser console:


var definitelyNotANumber;
definitelyNotANumber += 2; //NaN
typeof definitelyNotANumber; //wat?

Advertisements