Javascript Basics Part 12
WEBINAR:
OnDemand
Full Text Search: The Key to Better Natural Language Queries for NoSQL in Node.js
With this example we would loop through each firstlevel element of our array. If any of the elements in this array were themselves arrays, we would call the function again, passing this element as the primary array. The function would then go through this array and repeat itself until no arrays were left.
Another good example of recursion would be writing a parser for an XML document. Each node of the XML document can be parsed exactly the same way so we can break the entire thing into many, many smaller identical steps.
The hardest part about recursion is wrapping your head around it. Concepts like loops come fairly naturally, while recursion does not for most people. Also, recursive functions very often take up far more memory than nonrecursive functions. If you have a function that calls itself 20 levels deep, you are using at least 20x as much memory.
function factorial(N){ return N<=1?1:N*factorial(N1); }A very elegant solution, isn't it? We end up calling the factorial function 5 times for N=5. You can actually expand out the entire recusive function and get (5*(4*(3*(2*(1))))). Each set of parenthesis represents a new call to our factorial function. You can also see how if our user enters a number <=1 they will always get 1 as a result.
Let's take a look at another example. If you've ever used any paint program such as Photoshop or even MS Paint, you've probably used the flood fill tool. The flood fill tool fills whatever color you click on with whatever color you specify. It does this recursively and the algorithm to do so is fairly straightforward:
Click a cell: 
/* this is pseudocode, that is quickly written, nonfunctional code that is meant to just give an idea of how the actual code functions */ function floodFill(x, y){ if(alreadyFilled(x, y)) return; fill(x, y); floodFill(x, y1); floodFill(x+1, y ); floodFill(x, y+1); floodFill(x1, y ); } function fill(x, y){ // this function will actually change the color of our box } function alreadyFilled(x, y){ // this functions checks to see if our square has been filled already } 
The idea behind this code is that it fills the current square, or pixel. It then attempts to fill the square above, to the right, below and to the left of itself. By doing this every square will get filled fairly quickly. We run into a small problem here, however, stack size.
Whenever you call a function, a copy of many of the variables it needs to function is kept in memory. If you call the function recursively, another copy of all these variables is stored in memory, then another, and so on. These copies of variables are stored in what we call a stack. The first copy is on the bottom, the next on top of that, and so on. Unfortunately, there is a limit to how large this stack is allowed to grow. In most browsers, the limit on how large this stack can be is around 1,000. This means that with our floodfill function, our grid could contain up to 1,000 squares. Other browsers have a smaller stack. The Safari web browser, for instance, has a maximum stack size of only 100 meaning that our little 10x10 grid has already maxed out this browser.
So we have a limit in the browser itself that says we can only go 1,000 levels deep with our recursion. Unfortunately for us, our floodFill algorithm will, in the worst case, go 1,000 levels deep on a grid with only 1,000 boxes. If you have anything larger than this there is a chance it will overflow the stack and just stop running. Obviously there are cases where you might want to flood fill an area larger than 1,000 pixels. What do you do in this case? Well we change our approach. The first thing we can look at doing is changing our algorithm. There are many different floodfill algorithms out therethis one just happens to be the simplest. It looks in every direction and then fills each square it looks at if necessary. With a very simple change we can make this algorithm drastically more efficient in terms of how much stack space it uses. Instead of just looking left and right 1 square, we can look left and right as far as we possibly can and fill each pixel in that direction. This is called a floodfill scanline algorithm and turns out to be one of the most effecient flood fill algorithms there is. Unfortunately, it still has its limits and if you get an area large enough to fill than it too will overflow the stack. When this happens, we are left with only one alternative: don't use recursion. Instead of letting JavaScript handle the stack for us, we can create our own using a simple JavaScript array. Since an array has no limit on how many items it can contain, we can have an "infinitely" large stack that we control ourself. 
In order to build our own stack we need to take the recursive part of our function away. We're still going to be calling a function again and again, we're just going to be calling it from another function instead of from itself.
var Stack = []; function floodFill(x, y){ fillPixel(x, y); while(Stack.length>0){ toFill = Stack.pop(); fillPixel(toFill[0], toFill[1]); } } function fillPixel(x, y){ if(!alreadyFilled(x, y)) fill(x, y); if(!alreadyFilled(x, y1)) Stack.push([x, y1]); if(!alreadyFilled(x+1, y )) Stack.push([x+1, y ]); if(!alreadyFilled(x, y+1)) Stack.push([x, y+1]); if(!alreadyFilled(x1, y )) Stack.push([x1, y ]); } function fill(x, y){ // this function will actually change the color of our box } function alreadyFilled(x, y){ // this functions checks to see if our square has been filled already }As you can see, the process isn't all that much more complicated, but it does take a bit more micromanagement than the recursive code we wrote earlier. Instead of calling our floodFill function recursively, we create a variable, Stack, that holds a list of the squares we want to fill. Our fillPixel function then adds to this array and the floodFill function pops the last element off and fills it. When all is said and done, this has exactly the same effect as the first function that we wrote with one exception: this one doesn't have any limits as to how big our grid can be.
Note that there are very few recursive functions that will actually overflow the JavaScript stack. Actually, that's not quite true. Almost any recursive function can overflow the stack, but most of the time the data that we give the function makes it a very, very unlikely occurance. When, for instance, will you ever encounter an XML document with a node 1,000 levels deep? Pretty much never.
You now hopefully have a grasp of what recusion is, but you may still not have many ideas, other than a flood fill, of what to do with it. One of the most common algorithms written recursively would be what we call a binary search. Think of this as a highlow game. If someone asks you to guess a number from 1100, you'd probably start by guessing 50. If the person said higher, you'd probably guess 75, and so on. You would keep doing this until you found the number.
As it turns out, this is one of the quickest ways to find data when we know all the data is already sorted. If you have a list of 1,000,000 items and you need to find one you can start at 500,000 and go through the same process as with our number guessing game.
Speaking of sorting, we have, well, sorting algorithms. Many sorting algorithms, including one of the fastest, the QuickSort, use recursion to help them along. The QuickSort algorithm spits the data into chunks and sorts each chunk seperately and recursively splits those into smaller chunks and sorts those.
Another very common use of recursion is to validate or parse some type of data. An XML file was previously mentioned as an example, but many other forms of parsing, such as counting the number of times a word or phrase occurs in a sentence or book, can be performed efficiently with recursion.
Recursion is a very, very useful concept to understand. You may not use it all that often, but when you do you will be very grateful that you don't have to do without it. To close, I'll leave you with a little flood fill script to play with. It has 5 different animated floodfill algorithms that you can see in action. Further, it gives you a bit of information as to how efficient each one is when you run it.
If you make a sufficiently large grid, say 50x50, by either changing the settings and clicking redraw or by clicking here, you can see that the 4way algorithms, variations on what we wrote in this article, use a huge amount of stack space. The Basic 4way algorithm, which is exactly what we wrote in this article, probably won't even run because it will run out of stack space! Enjoy!
click on the table:


Loading Comments...