Recursion is cool. It can be defined in a non computer science way as:
the process of repeating items in a self-similar way
You may have experienced a simple form of recursion in a clothing shop fitting room when each side of the cubicle has mirrors and you see your reflection repeated for infinity; as shown in this photo.
Recursion is also a really powerful programming technique. In computer science it’s defined as:
a method where the solution to a problem depends on solutions to smaller instances of the same problem
Before I go on a little background behind this blog post. A friend of mine (no, not me but I won’t mention who) was recently interviewing for a new job and as part of the process was presented with this problem:
The solution to the problem can be visualised in the below image.
I had a quiet Monday night a couple of weeks ago and being a bit of a nerd I thought I’d give the challenge a go. You know, for fun.
At first I thought the problem would be really easy but soon I realised it wasn’t as simple as it first seems. After staring at it for a bit I realised the solution was to use recursion!
It’s actually a really nice example of recursion and that’s why I’m posting it here as I think it could help beginners understand what recursion is and how they can use it.
So let’s look at how to solve this problem. We obviously need to loop through and see if a cell is a 0 or 1. Once we find a 1 we give it a random color then check it’s adjacent cells and if they are also 1’s give them the same color. If an adjacent cell is a 1, we should also check that cell’s adjacent cells and repeat the process until we have find a cell with no adjacent 1’s.
So let’s look at this in code but with all the non-logic stuff stripped out – e.g. I’m not going to include the code for drawing to the canvas etc, you can view the final code with all that on CodePen here.
var matrix = [[0,1,0,0,1],[1,1,0,0,1],[1,0,0,1,0],[0,0,1,1,1],[0,0,1,0,0]];
var init = function() {
// for loops to iterate through each cell
for(var row = 0; row < matrix.length; ++row) {
for(var column = 0; column < matrix[rows].length; ++column) {
// if cell is a 1
if(matrix[row][column] === 1) {
// create a random color
var color = matrix[row][column] = randomColor();
// check adjacent cells
checkNeighbours(row, column, color);
}
}
}
};
var checkNeighbours = function(rows, cols, color) {
// check cell above
if(rows-1 >= 0 && matrix[rows-1][cols] === 1) {
matrix[rows-1][cols] = color;
// call checkNeighbours function from within itself
checkNeighbours(rows-1, cols, color); // recursion!
}
// check cell below
if(rows+1 < matrix.length && matrix[rows+1][cols] === 1) {
matrix[rows+1][cols] = color;
// call checkNeighbours function from within itself
checkNeighbours(rows+1, cols, color); // recursion!
}
// check cell to the left
if(cols-1 >= 0 && matrix[rows][cols-1] === 1) {
matrix[rows][cols-1] = color;
// call checkNeighbours function from within itself
checkNeighbours(rows, cols-1, color); // recursion!
}
// check cell to the right
if(cols+1 < matrix[rows].length && matrix[rows][cols+1] === 1) {
matrix[rows][cols+1] = color;
// call checkNeighbours function from within itself
checkNeighbours(rows, cols+1, color); // recursion!
}
};
In the above example we call the checkNeighbours function from within itself and continue to do so until we find a cell that has no unset adjacent 1’s. This is recursion.
See the below image to visualise the order in which the code runs through and colors each cell.
I hope this helps anyone who was struggling to get their head around what recursion is and how to use it. If it doesn’t make sense give me a shout in the comments and I’ll try to explain it further!
Could you tweak this to store the groups into a new array? Also isn’t this checking nodes that it has already colored? Shouldn’t it not try a node if it is colored?
thanks for the demo and clarifications
13 Jun 2013Simply put with great visuals, thx!
30 May 2013This really helped. Nice visuals
30 May 2013Hey Florent. Nope it would never create an infinite loop as it checks if the cell is 1 then sets it to a color. Next time round when it checks it’ll no longer be 1.
I would definitely be interested to see how you tackle this without using recursion. Please create a CodePen and post the link here! 🙂
25 Apr 2013In this code, you’re checking each case with the first two loops, and then for each case, you’re coloring all four neighbours, you will check a case then color the upper one for example, the upper one will then call your function on the one juste below (the one that called the function in the first place). If i’m right, this code will do an infinite loop if it finds a bloc.
At the first sight, you should probably remove the “1” from any case you have ever checked so it doesn’t loop.
The recursion solution isn’t necessary anyway, you might just go through the matrix and then check if any adjacent case is colored, then use that color on the new one.
25 Apr 2013Thanks, really informative!
3 Apr 2013I used a similar approach while making minesweeper, where you have to clear all adjacent empty cells.