In my experience, recursion is a topic that some developers fear and I have no idea why. It’s not that complicated……really. I’ve seen otherwise competent developers look like a deer in headlights when asked to solve something recursively. I’m going to hopefully shed some light on this topic, and give a simple real world example of something that might be done recursively.

The most simple definition of a recursive function is that it’s a function that calls itself. See, that wasn’t so hard! The most important thing to remember when writing a recursive function is to clearly define a base case. When you don’t have a clearly defined base case specified you can run into the dreaded infinite loop problem, which isn’t a good thing. After you have a base case, your function just needs to get you closer to the base case every time you call it.

The easiest way to figure out what I’m talking about is through example. I chose an example for this article that everyone can relate to. We’ve all been to a website that gives you a “breadcrumb” view of where you are in the site…this is especially true in sites where you are buying something. You might see a set of links on the page that looks something like this:

Home -> Category1 -> Sub Category1 – > Sub Category2

Lets say our site has a database on the back end, and this database has a Category table. This table has a few fields, CategoryID, ParentCategoryID, and CategoryName. A top level category in our database will have a ParentCategoryID of 0. Are you with me so far? Good. The base case in our example is clear. We start from the category that the user is at, and we keep adding categories to our list until we find one that doesn’t have a parent category above it. Every time we call this function we will be closer to the top of the tree, so this looks like a good candidate for recursion.

I’m going to tackle this example in PHP, it’s a solid language used often in website development. FYI: I’m skipping any sort of error checking in the example code for the sake of keeping the things simple.

<?php
// This string will eventually contain our list of categories.
//I’m going to return a string delimited with a | in this example.
$navString = “”;

// This is our recursive function definition.
//The $id parameter refers to the categoryID in our database table.
//The $data parameter is our current category list.
function loadNavTrail($id, $data)
{
  // I’m assuming that we have our database info set up somewhere else.
// A global variable probably isn’t the best idea but that’s not the point
// of this example.
  global $DB;
 
// We are going to query our database to get the name of our category.
// This example assumes we are using a MySQL database.
  $sql = “SELECT CategoryName FROM Category WHERE CategoryID = $id”;
  if (!$result = mysql_query($sql, $DB))
    die(“Database error!!”);
 
$row = mysql_fetch_array($result);
  mysql_free_result($result);
 
// Add the category name to our string.
// Don’t add a | to the result on the first pass.
  if (strlen(trim($data)) > 0)
    $data = $data . “|”;
  $data = $data . $row['CategoryName'];
 
// Figure out if our category has a parent category or not.
// This is our base case.
  $sql = “SELECT ParentCategoryID FROM Category WHERE CategoryID = $id”;
  if (!$result = mysql_query($sql, $DB))
    die(“Database error!!”);
 
$row = mysql_fetch_array($result);
  mysql_free_result($result);
 
// If this value is 0, we are at the top of the tree…otherwise call the function again.
  $parentCat = $row['CategoryID'];
 
if ($parentCat == 0)
  {
    // This is our base case, there is no parent category.
    return $data;
  }
  else
  {
    // This is our recursive function call.
    return loadNavTrail($parentCat, $data);
  }
}

// This is our function call.
// $currentID here represents the ID of the current category.
$navString = loadNavTrail($currentID, $navString);

// At this point, you could split the $navString variable
// on the ‘|’ character we chose as a delimiter.
// Realize that we got them from the bottom to the top, so you would have to
// reverse the order of the elements to get a “breadcrumb” view.
?>


See, I told you recursion wasn’t bad! Recursion is a very powerful technique to have in your bag of tricks as a developer, I recommend that if you don’t already have experience with it that you come up with an example and give it a shot!