halO

I've heard from several sources, on the web that is, that you should stay away from recursion if you need someone else to maintain your code. The argument is that recursion is hard and some people just don't understand it. Well boo hoo. Start understand it or maintain some easier code. I mean, we covered recursions during the first year of uni! (I might be easier to deal with and agree to stay away from recursions if you're paying me lotsah' monies , but I'm happy where I am right now.)

Generate a thought map in your head. Divide problems into smaller ones and then conquer them. Let's have a look at scanning a tree. We want to see if a tree contains the number 42.

We know for certain we have to look at the root node if it contains the number 42. If it does, we return true and everyone is happy. If not, we should start looking at child nodes. For every child node, we should see if it contains the number 42. It it does, we return true and everyone is happy. If not, we should start looking at child nodes.

Hang on now! During my thought map above, I just repeated the exact same thought sequence. It is as if *gasp* it is a loop!

It is.

The function is just calling itself just as how it would call any other function. I think the word just scares people. Of course, recursions are more prone to infinite loops compared to calling other functions, but for loops are also more prone to infinity than copy&pasting a lot of code! You just have to know how to use the tool.

Here's the code to scan a tree where every node has an int value and an array children.

// scan a node and it's children
function scan(node){
   if(node.value==42){
      return true; // Everyone is happy
   } else {
      // Look at child nodes
      for(var i=0,child; child=node.children[ i]; i++){
         // scan a node and it's children
         if(scan(child))return true;
      }
   }
}

This should demonstrate it is not specifically hard writing recursions. I wrote the above code and it worked the first time I tested it [1]. There is no alterations in the above code after I tested it the first time. I did forget to add return false after the for construct, but looking at the mental spec above, there is no mention of returning false at any point ;-) And besides, undefined is evaluated as false in a boolean context.

// Testing code
alert( scan({value:30,children:[{value:35,children:[]},{value:412,children:[]}]}) ); // undefined
alert( scan({value:30,children:[{value:35,children:[]},{value:42,children:[]}]}) ); // true

[1] Not exactly true, I had to edit it later today. The My Opera editor thought I meant italic text where it now says child=node.children[ i]