Dedication

This tutorial is dedicated to megan, who made me think and stretch my mind to come up with an efficient, scalable solution to a real-world application development problem; to dduck1934, who encouraged me to make the time to finish writing this tutorial after letting it sit unfinished for 6+ months; to all EasyCFM members and visitors past, present, and future; and lastly, to the ColdFusion community as a whole, which is in my opinion the greatest group of developers known to the web.

Introduction

One day, I was reading a post on the EasyCFM forums where a member was expressing their difficulty with categories and subcategories. So, in my infinite wisdom I chimed in on the thread and gave an example of my then-preferred method of handling them. At the time, the solution seemed simple and easy to implement.

Create two tables in your database: tblCategories, and tblSubCategories. They are structured like so:

tblCategories

categoriesID (primary key)

category_name

tblSubCategories

sub_categoriesID (primary key)

category_id (foreign key, related to 'tblCategories.categoriesID')

sub_category_name

Now I had my categories and my subcategories, and they were really easy to retrieve and output to the screen. You just run a query for your categories, and then as you're outputting them, query to get the subcategories.

See Listing 1.

Thanks to another member who posted (thank you megan!), I realized that there are two major flaws with this table schema:

1. It only provided me with one level of subcategories. To add another level of sub-subcategories, an additional table was needed. What if I was working on an application that required 3, 4, 5, or even 10 levels of subcategories? That's an additional 3, 4, 5, or 10 tables. What a nightmare!
2. Each subcategory requires an additional query to be run in order to get the data and output it. When building web applications that are intended to see lots of traffic and be scalable, the last thing you want to do is have a page that requires a ton of trips to the database in order to be built. An application built on this type of schema, simply put, will cave in under the load.

So, one solution to the limitations of the two-table schema is to narrow it down to just one single table, constructed in this fashion:

tblCategories

categoriesID (primary key)

category_name

parent_id

Notice that this table is identical to my original categories table, with the exception of one additional field: parent_id. This field defaults to a zero (0), which indicates that the category is a top-level category. However, if the category is a subcategory of another category, we simply enter the categoriesID of the parent into this field. (If that is really confusing, don't leave just yet, we'll cover it in more detail in a moment.)

We have successfully reduced our table requirements from two down to one, but this schema, by itself, also only reduces our problems from two down to one. We can now go as many levels deep with our subcategories as we want to without changing our table schema, but we are still required to run another query for each subcategory. Unfortunately, we've failed to reduce the load on our database and server(s).

So then, what is the solution? Enter two things that have a tendency to scare ColdFusion developers to death:

1. Object-Oriented Programming (OOP)
2. Recursion

We're about to get down-and-dirty here, so if you need to take a quick break, now's the time to do it!

OOP

While the techniques discussed in this tutorial use OO practices and thought patterns, it is not intended to be a study on OOP. There are many great books out there that will assist you in learning and understanding OOP. There are also quite a number of online resources available to assist you. Just go to google.com and type in OOP.

For the purpose of this tutorial, all you need to understand about OOP is this:

1. We will use objects instead of UDFs,
2. Objects allow us to encapsulate our data and protect it from ourselves,
3. Objects allow us to enjoy an incredible amount of code reuse while simultaneously reducing the amount of code that we write in our templates that use the objects, and
4. Objects allow us to more effectively manage our (hopefully) ever-expanding application

Recursion

What on earth is recursion? Here's what the dictionary says:

"To cause to surge or flow back; specifically, to bring partly digested food from the stomach back to the mouth."

Ooooops! My apologies. That's the definition of regurgitate. But, as you will soon see, it is actually very similar. Here's the correct dictionary definition for recursion:

"An expression, such as a polynomial, each term of which is determined by application of a formula to preceding terms; a formula that generates successive terms of a recursion."

If you're like I was when I first read that definition, you're sitting there with a blank stare saying to yourself: "HUH!?!"

So, I set out to find out what recursion was, in terms that were understandable to those of us who are not math or computer science majors, and ran across this little tidbit at Wikipedia.com.

"Recursion is the process a procedure goes through when one of the steps of the procedure involves rerunning the entire same procedure. A procedure that goes through recursion is said to be recursive. Something is also said to be recursive when it is the result of a recursive procedure."

When I read that, it reminded me of the cow and regurgitation, and voila! What had just been completely confusing suddenly made perfect sense. So then, in the world of ColdFusion, recursion, or a recursive function, is a function that performs a particular task, but in order to complete the task it must "regurgitate", and run itself all over again. Some recursive tasks actually require the function to run itself many times over.

So then, without further ado, let's get to some practical application of our newfound regurgi... I mean recursive wisdom.

Getting Started

To get started, we first need to create our database table. Here are scripts for SQL Server and MySQL.

Next we'll populate our new categories table with some categories that we'll be using throughout the remainder of the tutorial.

See Listing 3.

After populating the table, we run a query to get all of the categories. Assuming that all went according to plan in our Listing 4 code, you should end up with something like the following on your screen.

Now that we have the basics out of the way...

Fixing Flaw #1: The tblCategories Table

For those who are still scratching their head about the whole parent_id thing, let's look at a detailed diagram of how our categories table actually works.

As you can see by the 'Rules of Conduct IV' category, we can now go as many levels deep in our categories as we need to, and they are all stored in one convenient table. Flaw #1 fixed!

Fixing Flaw #2: The Recursive Object

This tutorial assumes that you possess at least basic knowledge of ColdFusion Components (CFCs), so we won't be spending any time discussing them.

So then, let's build our recursive object! Open up a blank page in your favorite editor, and write the following code:

<cfcomponent hint="An object for recursive searching" displayname="objRecursive" output="false">

  <!--- "constructors" --->
  <cfset variables.properties = structNew() />

</cfcomponent>
	

Now save that file as 'recursiveObject.cfc' (minus the quotes, of course). Congratulations! You've just created your first recursive object! Okay, not really, but we're headed in the right direction.

The getProperty() and setProperty() Methods

You'll notice that we've created a variable inside our object named 'properties', which is a structure. This structure will be used to hold all of the properties that provide the makeup of the object. Now we need to add a couple of methods that allow us to set (define) and get (retrieve) these properties. We aren't going to discuss them; they're simple enough that you should have no trouble figuring out what they do and how they do it. Just plug them into the recursiveObject file.

See Listing 5.

The init() Method

Now that our object contains the methods that allow us interact with its properties, we need to add the method that will initialize our object. Conveniently enough, this method is named init.

<!--- begin init() method --->
<cffunction name="init" 
  hint="Initializes the object" 
    returntype="recursiveObject" output="false" access="public">
  <!--- set the method arguments --->
  <cfargument name="qry" 
    hint="The query object that the recursion is based upon" 
      required="yes" type="query" />
  <cfargument name="dspField" 
    hint="The name of the field in the provided query from which to retrieve the display text" 
      required="yes" type="string" />
  <cfargument name="parentField" 
    hint="The name of the field in the provided query that contains the parent ID; 
      this is typically the PRIMARY KEY for the table" 
    required="yes" type="string" />
  <cfargument name="childOfField" 
    hint="The name of the field in the provided query that contains the ID of the parent element; 
      this is often named 'parent_id'" 
    required="yes" type="string" />

  <cfscript>
    setProperty("qry", arguments.qry);
    setProperty("dspField", arguments.dspField);
    setProperty("parentField", arguments.parentField);
    setProperty("childOfField", arguments.childOfField);
    return this;
  </cfscript>
</cffunction>
<!--- end init() method --->
	

The init() method contains several key things that we need to make sure and be aware of:

• it requires us to pass in arguments
  1. a query
  2. the name of the display field from our query (category_name)
  3. the name of the parent field from our query (categoriesID)
  4. the name of the childOf field from our query (parent_id)
• it uses the setProperty() method to store the argument values, and
• it returns the object back to the caller using the 'this' keyword

The arguments that are passed into the init() function are stored as object properties. This allows us to use them over and over and over again inside of our object. You'll see plenty of examples of this shortly.

NOTE: You should never use the 'this' keyword inside your objects for any purpose other than the one we just reviewed; returning the object to the caller. Doing so will make your variables available outside of the object, which we do not want to do!

The getSubs() and getParent() Methods

Two more methods need to be added before we get to our first recursive method. Both of these methods are private methods that perform a Query of Queries (QofQ) and return a query object. While each is vital to the well-being of our object, they are very simple and I am assuming that they do not require explanation beyond the hints that are written into the code.

See Listing 6.

The getDepth() Method

The getDepth() method is the first of our recursive methods that we're going to add into our object. Place the code below into your recursiveObject.cfc file, and then come back and we'll break it down and discuss what the method does.

 1<!--- BEGIN getDepth() method --->
 2<cffunction name="getDepth" 
 3    hint="Returns the numeric value of how many levels deep an element resides in a recursive query 
 4          (NOTE: a return value of 1 indicates a top-level element, so depending on your purpose, 
 5            you might need to subtract 1 from the result)" 
 6    returntype="numeric" output="false" access="public">
 7  <!--- set the method arguments --->
 8  <cfargument name="childID" 
 9    hint="Provides the ID of the child whose parent is being searched for" 
10      required="yes" type="string" />
11
12  <cfscript>
13    var depth = 1;
14    var qParent = "";
15    qParent = getParent(arguments.childID);
16    if (qParent[getProperty('childOfField')][1] GT 0) {
17      depth = depth + getDepth(qParent[getProperty('childOfField')][1]);
18    }
19    return depth;
20  </cfscript>
21</cffunction>
22<!--- END getDepth() method --->
	

So then, what does the getDepth() method do? Well, the summarization of its purpose is found on lines 3 - 5 in the hint attribute of our <cffunction> tag. But let's take a look at how it accomplishes this.

The first thing we need to point out is that the childID argument is required (lines 8 - 10). In respect to our tblCategories table, this is the categoriesID of the category whose parent category we're searching for. So if we're looking for the parent of 'Rules of Conduct', we'll supply a value of 4 to this argument.

Next, on line 15 we send the provided childID off to the getParent() method (listing 6) so we can find the parent category, if there is one. On line 16, we check to see if the 'childOfField' from our qParent QofQ is greater than zero, indicating whether or not a parent was found. If one was, then the 'childOfField' (parent_id) of our returned QofQ will be greater than zero. If no parent was found, the method returns the value of 'depth', which was defaulted to 1 back on line 13.

Line 17 proecesses only if a parent was found, and this is where the magic of the method takes place.

By referring back to the query dump, we can see that 'Rules of Conduct' is two levels deep: 'Membership Information' is its parent, which is on the first level, because it has no parent. So, if our getDepth() method is working properly, it will return a 2 when we provide it with the ID (4) for 'Rules of Conduct'.

Now look closely at line 17. Can you see what makes it so special? HINT: It is the code AFTER the plus sign (+).

     getDepth(qParent[getProperty('childOfField')][1])
	

This little bit of code is what makes this a recursive method. Because we found a parent in line 16, we are going to submit the ID of that parent to the method (in this example, that would be 2). Even though the getDepth() method is what we're running, it needs to run itself again in order to finish calculating the depth. As a matter of fact, it runs itself once for every level of depth of the ID we originally provided. Stated differently, until line 16 returns false (no parent is found), line 17 will continue to process once for each level of depth.

So, knowing that 'Rules of Conduct' is two levels deep, and knowing that line 17 is run once for each level, we can see that the first time the method is run (our original call with the ID of 2), line 17 takes the value of 'depth' (which we set to 1 on line 13) and adds it to the value returned from the getDepth() method after we submit the 'Membership Information' ID (4), which is 1. So, in plain math, in our example, line 17 actually says:

     depth = 1 + 1;
	

Pretty cool stuff! Now that we have our first taste of ColdFusion recursion, let's put it to practical use.

The getRecursiveOptions() Method

The boss called and said that the client needs a new form online within the hour. This form needs to allow them to add categories to their categories table. The catch? The form needs to give them the ability to select the parent category when they enter the new one. You have two basic options:

1. make them manually enter the parent category
2. go thru the table and manually write an <option></option> tag for each category

You think about it for a moment and decide that you like your job; angering the client poses a significant risk to keeping said job, so forcing them to manually enter everything doesn't seem too logical. The second option, while it might be a serious pain in the rear to go thru the table and hard code all of the options, you feel that it is the lesser of two evils, so you go with it. Just then, that really annoying know-it-all co-worker (you know which one I'm talking about) says: "Yeah, but if you do that, won't you have to add a new option tag for each category that they add?"

As badly as you want to kick the teeth out of the mouth that just uttered that question, you realize that it's true, and you think to yourself, "Geeeeeez, there has to be a better way." And that's when you remember about this tutorial that you read one time; something about some crazy regurgitation stuff. "Hmmmmmm," you say to yourself, "maybe there's a solution in the making?!"

 1<!--- BEGIN getRecursiveOptions() method --->
 2<cffunction name="getRecursiveOptions" 
 3    hint="Returns a string containing the option tags for an option list from a recursive query search" 
 4      returntype="string" output="false" access="public">
 5  <!--- set the method arguments --->
 6  <cfargument name="parentID" 
 7    hint="Provides the ID of the parent category to search in" 
 8      required="yes" type="string" />
 9
10  <cfscript>
11    var strOut = "";
12    var qSubs = "";
13    var option = "<option value=""[id]"">[dsp]</option>";
14    var dsp = "";
15    var i = 1;
16    var depth = 0;
17    qSubs = getSubs(arguments.parentID);
18    if (qSubs.recordCount GT 0) {
19      for (; i LTE qSubs.recordCount; i=i+1) {
20        depth = getDepth(qSubs[getProperty('parentField')][i]);
21        strOut = strOut & option;
22        strOut = replace(strOut, "[id]", qSubs[getProperty('parentField')][i]);
23        dsp = repeatString(" – ", depth-1) & qSubs[getProperty('dspField')][i];
24        strOut = replace(strOut, "[dsp]", dsp);
25        strOut = strOut & getRecursiveOptions(qSubs[getProperty('parentField')][i]);
26      }
27    }
28    return strOut;
29  </cfscript>
30</cffunction>
31<!--- END getRecursiveOptions() method --->
	

For the sake of time, we're going to skip over most of the method and point out just four lines of code: 18, 19, 20, and 25.

Line 18: We simply check to see if any children (subcategories) were returned. Lines 19 - 26 will only process if they were.

Line 19: Creates a loop of lines 20 - 25 that runs as many times as there are children.

Line 20: We send the ID off to the getDepth() method to find out how many levels deep the category that is currently processing resides. If you've forgotten what getDepth() is, take a review.

Line 25: Here's where we regurgitate again, and tell the getRecursiveOptions() method to rerun itself. We pass in the current category's ID as the argument. This line ensures that the method will continue to run until we've found all children of the current category, including grandchildren, great-grandchildren, great-great grandchildren, great-great-great... you get the picture.

You're now sitting there thinking, "Okay, I kind of understand what he's talking about here, but it'd probably make more sense if I saw the results of the method." I couldn't agree more, so let's create a quick index.cfm file so that we can find out exactly what it does.

 1<cfquery name="qCats" datasource="#dsn#">
 2SELECT categoriesID, category_name, parent_id 
 3  FROM tblCategories 
 4ORDER BY parent_id, category_name;
 5</cfquery>
 6
 7<cfscript>
 8  cfcPath = "path.from.wwwroot.to.recursiveObject";
 9  objRecursion = createObject("component", cfcPath).init(qCats, "category_name", "categoriesID", "parent_id");
10</cfscript>
11
12<cfoutput>
13
14<select name="mySelect">
15  #objRecursion.getRecursiveOptions(0)#
16</select>
17
18</cfoutput>
	

IMPORTANT! Be sure to set the cfcPath variable (line 8) to the correct path on your box to where you stored your recursiveObject.cfc file. For instance, if you store the recursiveObject file in a directory named 'recursive' under the localhost root, you would set this to: "recursive.recursiveObject".

Line 9: create the object. Notice that we have concatenated the .init() method to the end of the createObject() function. Inside the init() method call is where we are passing the required arguments to the object: our query, the name of our display field, the name of our parent field, and the name of our childOf field. Once we've done this, we can now call on any of its public methods.

Line 15: By passing a zero as an argument, we'll be returned an option list containing every single category in the table. That's how incredibly easy our recursive object makes it to setup our select box on the new form for our client! If you want to list only categories that fall under the 'Member Information' category, change the zero to a 2. The number that you pass to the method can even be set dynamically, but I'll leave that part up to you to decide!

The getBreadcrumbs() Method

Another example of a real-world problem that is solved by recursion is breadcrumbs. How many times have you hard-coded your breadcrumbs into the page? Or used seemingly a million-and-one <cfif> and <cfelseif> statements to build them? Thanks to our getBreadcrumbs() method you no longer nee