Javascript Basics Part 12

By Mark Kahn

"To understand recursion you must first understand recursion". That is my favorite quote related to programming because it so beautifully captures what recursion is. Recursion is a general programming concept, not at all restricted to JavaScript, but it is a very useful concept to understand. It involves calling a function from within that same function. Why would you want to do this? Well let's say you have an array of arrays. Each of those arrays can have arrays in them which can have arrays, which can have...well you get the idea. You have lots of arrays in other arrays. How do you perform the same operation on all elements in all of these arrays? You could attempt to use a simple for loop, but you don't know how many arrays you have and you don't know how deep the nesting of arrays goes. So we are left with a concept called recursion.

With this example we would loop through each first-level 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 non-recursive functions. If you have a function that calls itself 20 levels deep, you are using at least 20x as much memory.

A simple example would be to write a factorial function recursively. Factorial N, written as N!, is defined as the multiple of all numbers from N-->1. So 5! would be 5*4*3*2*1 = 120:
function factorial(N){
	return N<=1?1:N*factorial(N-1);
}
Demo
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 straight-forward:

Click a cell:
Color:
/*
this is pseudo-code, that is quickly written, non-functional
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,   y-1);
	floodFill(x+1, y  );
	floodFill(x,   y+1);
	floodFill(x-1, 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.

The Stack

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 flood-fill algorithms out there--this 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 scan-line 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.

Building a Custom Stack

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,   y-1)) Stack.push([x,   y-1]);
	if(!alreadyFilled(x+1, y  )) Stack.push([x+1, y  ]);
	if(!alreadyFilled(x,   y+1)) Stack.push([x,   y+1]);
	if(!alreadyFilled(x-1, y  )) Stack.push([x-1, 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 micro-management 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.

Uses for Recursion

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 high-low game. If someone asks you to guess a number from 1-100, 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 flood-fill 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 4-way algorithms, variations on what we wrote in this article, use a huge amount of stack space. The Basic 4-way 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:

rows:
cols:
block %:
block size:
Use Algorithm:
Algorithm Run Time:
Color:
Stack Depth:
Maximum Stack Depth:


Make a Comment

Loading Comments...

  • Web Development Newsletter Signup

    Invalid email
    You have successfuly registered to our newsletter.
  •  
  •