If you’re churnin’ out a web app cause your sales guy said you would,

And the PM he’s a pushin’ cause he knows you’re just that good;

But the requirements call for nav that stretches to infinity,

Then it may be time to think about recursive hierarchy….

Oh, recursion is a big word to describe a special function

That can chase its tail and catch it if it’s written with some gumption!

You could rightly call it Schizo, as to why, here’s the scoop:

It will call itself AND ANSWER in a never ending loop!

The secret to its mental state that makes it strange, yet stable

Is the special way it uses scope to give its vars a label.

If a variable is private then it’s labeled V-A-R,

While the public ones are public with no label needed thar!

And so, oh best Beloved, this function’s prelude now is ended;

But I must insist that you press on to find it and befriend it!

For no programmer’s app is done, regardless of the version,

Unless it boasts, at least a mite, the power of Recursion!

A few quick comments about the fields. ParentID contains the id of the record that the item is a child of. Records with a parentID of zero are top level; they have no parents.

Okay, so storing the hierarchical data is no problem and the way we chose to do it is both elegant and makes perfect sense! The CHALLENGE, however, (there are no problems, only challenges) is how to retrieve and properly display this data while maintaining its hierarchical relationship. For our example, the requirement will be to retrieve the navigational data and output it using html Unordered Lists, maintaining the data’s hierarchy. Here is where the power of the recursive function is a perfect fit.

Recursion can be a difficult thing to visualize in action, so let’s first go through how one could retrieve and display this data if recursion did not exist.

First of all, we must know up front how many levels deep our data goes so that we know how many nestings to use in our code. In this case, none of the data goes more than 4 levels deep. Assuming our data has been retrieved into a query named qryNavigation, the following ColdFusion code will display our information as a properly nested unordered list:

Walking through this code, the first thing we have is a query containing all of the nav items. Step 1 is to create the opening UL tag for our unordered list. Next, we retrieve all of our top level (parentID = 0) nav items and loop through them. For each one, we check to see via a Query of Queries if that particular nav item has children. If so, we retrieve that items children and loop through those. For each of the children, we check to see if THEY have children. If so, we loop through them, repeating the process one more time. Opening and closing UL and LI tags are added appropriately to form a string containing a properly formatted html unordered list which is then output to the browser.

That is a lot of code, and as you can tell, it limits the data to 4 levels deep while our requirement called for infinite levels. Not the solution we’re looking for. We need one with a little more imagination, grace, elegance, and usability.

I’m just going to lay it on you; here is the equivalent recursive function that accomplishes the same thing, but without limitations and with less code:

Let’s walk through this recursive process. Step 1 really comes last, and that is our initial call to this function that kicks the whole process off like the first domino falling. From here on out, we will cease to use the actual value of the parent ID and simply refer to it as ‘X’; this will make it easier to walk through the code. We call the function passing a value of zero to the level argument (which lets us keep track of where we are in our recursive calls) and a value of X to the parentID argument (used when retrieving navigation subsets via query of queries). Our first call to the function sets up the two private (VAR scoped) variables for use by this instance of the function. Since we are at level zero, it then initializes the values of two public variables: navigation and menustring. Menustring is our cumulative variable, meaning that with every call to GenerateNav, we will be appending more and more items to it.

Our next step is to execute the query objNav which retrieves all items from the complete set of nav items that have a parentID of X. Once retrieved, we have our X level items and begin looping through them. For each item returned, we check to see if there are any children. If there are (drumroll please…), then we make a recursive call to GenerateNav, passing it a parentID equivalent to the current item’s ID, and a level equal to the current level plus one.

The recursive call to GenerateNav sets up its two private instances of checkForKids and objNav, skips the initialization of the public variables, then selects all nav items for the parentID that was just passed in. Those children are retrieved, we step through them, and for each of them that are found to have children themselves, we again call GenerateNav passing in the appropriate values for that particular instance of the function.

When we’ve gotten through every item in our first initial objNav query (which would have been all items with a parentID of zero), we add the closing UL tag to our public variable Menustring and then return it. Notice we enclose the code to add the closing UL tag and to return Menustring within a CFIF that looks at the level. This prevents Menustring from getting returned prematurely by any of our recursive calls.

When a recursive function calls another instance of itself, you can rightly picture that it just managed to perform mitosis and now has an identical brother performing the exact same work, only with its own private variables. Whatever variables were declared public are shared between the first and its brother, and any subsequent brothers that are spawned. As each clone completes its task, it disappears back into the ether until finally there is only the original instance left, and when it has completed its task, it returns the final value and itself disappears, completing the entire process. This is recursiveness in a nutshell. Beautiful, isn’t it?

You may also be wondering how useful it is to output your navigation in an unordered list. Bear in mind that I kept it as simple as possible and did not include fields to hold URLs and other linking information that would normally be present in a navigation table. Those can be added later and included within the information being appended to your Menustring variable, along with CSS class names based on level. Upon output, it is a relatively simple thing to create a Stylesheet to format your unordered list as a flyout menu (no javascript required), such as is shown here:

I hope you found this information both useful and inspiring, and will be looking for places to leverage it within your own application development. As the late great Buckminster Fuller once said, “…if the solution is not beautiful, then it is wrong.”, so let's keep it beautiful folks.