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

4 thoughts on “Javascript Recursion, Variable Scope and Hoisting

  1. Hi kadodamball
    Looked at the code and it looked right except that the sum wasn’t added for the inner array. I put in
    sum += arraySum(i[x]);
    and got 15. I just saying that the sum was calculated correctly but wasn’t added.
    Cheers

    • Which code are you referring to? Sorry, I named all three examples using the same name. You should note that I used the simplest example but you could try with 3 or 4 nested arrays deep to see what kind of answer you’d get.

  2. I fail to see the issue. Why not simply do 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){
    sum +=arraySum(i[x]);
    }
    }
    return sum;
    }

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