Categories
Contact Doug!
Learn About Doug!
View Doug Boude's online resume
updated 11/18/2009

View Doug Boude's profile on LinkedIn
Link to me!

Follow Doug Boude on Twitter
Follow me!

Be Doug's friend on Facebook
Befriend me!
(I promise not to follow you home)
OO Lexicon
Chat with Doug!
Recent Entries
You may also be interested in...
Web Hosting

<< September, 2014 >>
SMTWTFS
123456
78910111213
14151617181920
21222324252627
282930
Search Blog

Recent Comments
Re: My Top 20 Life Lessons for Boys and Young Men (by jeffrey scott berry at 9/16 2:42 PM)
Re: Equivalent of SQL "TOP X" in Oracle (by Mark Foster at 7/07 4:04 PM)
Re: SQL Forward Engineering with Visio 2003 Professional (by Thomas at 6/26 4:41 AM)
Re: One Shot Query to Recalculate Orderby Field - MySQL (by gary at 6/17 6:46 PM)
Re: DON'T GET SICK IN ARKANSAS! (by r. wood at 5/25 12:00 AM)
Re: SQL Forward Engineering with Visio 2003 Professional (by Andrew at 4/30 6:14 AM)
Re: Basic Ajax Select List Filter in PHP (by good at 2/04 5:26 AM)
Re: Family Law: The Weapon of Choice for Woman Scorned (by swalker at 2/03 2:15 AM)
Re: Approaches to Building Strings: The Imploding Array (by bantal silikon at 2/01 9:44 PM)
Re: Disappearing IE Popup Window During Save/Open Dialog (by AddisonDean at 1/15 9:59 AM)
Re: My Top 20 Life Lessons for Boys and Young Men (by Alex at 1/13 8:45 PM)
Re: Array Loop Modifications in CFSCRIPT (by Alex at 11/25 11:18 AM)
Re: Array Loop Modifications in CFSCRIPT (by Abram at 11/14 11:32 PM)
Re: Recursive Functions in ColdFusion (by Dwayne at 10/25 3:47 PM)
Re: Porting Coldfusion Code to Mura (by dh at 10/16 10:14 AM)
Re: Viewing Option Text (in IE7) that's Wider than the Select List (by Devil May Cry at 9/26 1:38 AM)
Re: Why I Hate ORMs (a solicited rant) (by guideX at 9/12 11:38 PM)
Re: Recursive Functions in ColdFusion (by KP at 8/08 7:13 PM)
Re: American Airlines, YOU SUCK! (by Alison at 7/23 4:48 PM)
Re: SQL Forward Engineering with Visio 2003 Professional (by Harshad at 7/11 9:17 AM)
Archives
Photo Albums
Funnies (5)
Family (3)
RSS

Powered by
BlogCFM v1.11

17 June 2006
Recursive Functions in ColdFusion
Navigation Methodology
Dr Doug Says:

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!

On THAT note…
Let’s say that you are designing an app and you want to give the user the ability to manage his navigational tree to an infinite level; the ability to add items under items under items under items to his or her heart’s content. From a database point of view, the simplest way to store relational data like this and meet the requirement of infinite relationship levels is a single table with a structure something like the following:
navigation structure

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:

<cfset menustring = "<ul>"><!--- Step 1 - Initial opening UL tag --->
<cfloop query="qrynavigation">
    <cfif parentid eq 0><!--- Step 2 - Loop through all top level nav items --->
        <cfset menustring = menustring & "<li>" & navdescription>
        <!--- Step 3 - see if this item has children --->
        <cfquery name="checkforKids" dbtype="query">
            select * from qrynavigation where parentid = #qrynavigation.id#
        </cfquery>
        <cfif checkforkids.recordcount gt 0><!--- Step 4 - loop through kids --->
            <cfset menustring = menustring & "<ul>">
            <cfloop query="checkforkids">
                <cfset menustring = menustring & "<li>" & navdescription>
                <!--- Step 5 - see if this item has children --->
                <cfquery name="checkforkids2" dbtype="query">
                    select * from qrynavigation where parentid = #checkforkids.id#
                </cfquery>
                <cfif checkforkids2.recordcount gt 0><!--- Step 6 - loop through kids --->
                    <cfset menustring = menustring & "<ul>">
                    <cfloop query="checkforkids2">
                        <cfset menustring = menustring & "<li>" & checkforkids2.navdescription>
                        <!--- Step 7 - see if this item has children --->
                        <cfquery name="checkforkids3" dbtype="query">
                            select * from qrynavigation where parentid = #checkforkids2.id#
                        </cfquery>
                        <cfif checkforkids3.recordcount gt 0><!--- Step 8 - loop through kids --->
                            <cfset menustring = menustring & "<ul>">
                            <cfloop query="checkforkids3">
                                <cfset menustring = menustring & "<li>" & checkforkids3.navdescription & "</li>">
                            </cfloop>
                            <cfset menustring = menustring & "</ul></li>">
                        <cfelse><!--- this level 2 item has no kiddos --->
                            <cfset menustring = menustring & "</li>">
                        </cfif>
                    </cfloop>
                    <cfset menustring = menustring & "</ul></li>">
                <cfelse><!--- this level 1 item has no kiddos --->
                    <cfset menustring = menustring  & "</li>">
                </cfif>
            </cfloop>
            <cfset menustring = menustring & "</ul></li>">
        <cfelse><!--- this level 0 item has no kiddos --->
            <cfset menustring = menustring & "</li>">
        </cfif>
    </cfif>
</cfloop>
<cfset menustring = menustring & "</ul>">
<cfoutput>#menustring#</cfoutput>

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:

<!--- Initializing our 'variables' scoped variables...public access --->
<cfset variables.menustring = "">
<cfset variables.navigation = "">
<cffunction name="GenerateNav" access="public" returntype="string">
    <CFARGUMENT name="parentID" type="numeric" required="yes" default=0 >
    <CFARGUMENT name="level" type="numeric" required="yes" default=0 >
    <!--- scoping the variables that need to have their values kept private
    to a particular instance of the function call... --->
    <CFSET var checkForKids = ""><!--- used to hold temporary check for children --->
    <CFSET var objNav = ""><!--- used to hold temporary subqueries --->
   
    <!--- On our initial call to this function, we will purge the menustring and grab our navigation source query. --->
        <CFIF arguments.level eq 0>
            <CFSET variables.navigation = qryNavigation>
            <CFSET variables.menustring = "">
        </CFIF>
       
        <!--- Retrieve all nav records from variables.navigation who are the children of our current parent --->
        <CFQUERY name="objNav" dbtype="query">
            select * from variables.navigation where parentid = <CFQUERYPARAM value="#arguments.parentid#" cfsqltype="CF_SQL_INTEGER">
            order by navorder
        </CFQUERY>
        <!--- write our current parent to the menustring... --->
        <CFSET variables.menustring = variables.menustring & "<UL>">
        <!--- loop through this parent's children... --->
        <CFLOOP query="objNav">
            <!--- check for children. If there are any, call this function recursively --->
                <CFQUERY name="checkForKids" dbtype="query">
                    select * from variables.navigation where parentid = <CFQUERYPARAM value="#objNav.id#" cfsqltype="CF_SQL_INTEGER">
                </CFQUERY>
                <CFIF checkForKids.recordcount gt 0><!--- this child has kids too! add it to the menustring, then make the recursive call... --->
                    <CFSET variables.menustring = variables.menustring & "<LI>" & objNav.NavDescription >
                        <CFSET GenerateNav(parentID = objNav.ID, level = arguments.level + 1) >
                <CFELSE><!--- this child is childless...just add it to the menustring... --->
                    <CFSET variables.menustring = variables.menustring & "<LI>" & objNav.NavDescription >
                </CFIF>
                <!--- close the list item --->
                <CFSET variables.menustring = variables.menustring & "</LI>">
        </CFLOOP>
        <!--- close the UL tag --->
        <CFSET variables.menustring = variables.menustring & "</UL>">
        <!--- return final variable to the caller... --->
        <CFIF arguments.level eq 0>
            <CFRETURN variables.menustring>
        </CFIF>
</cffunction>

<!--- THIS is the kickoff point of the whole thing! --->
<cfset recursivenav = GenerateNav(ParentID=0, level=0)>
<cfoutput>#recursivenav#</cfoutput>

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:

recursivemenu

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.




Posted by dougboude at 1:46 PM | PRINT THIS POST! |Link | 22 comments
Subscription Options

You are not logged in, so your subscription status for this entry is unknown. You can login or register here.

Re: Recursive Functions in ColdFusion
Wow. That is amazing. How did you do that?
Posted by CSS Fan on July 5, 2006 at 11:00 AM

Re: Recursive Functions in ColdFusion
That was neat!! Do you have some code that you can zip up that does the hyperlinking and layout at bottom?
Posted by Chris Tilley on July 6, 2006 at 8:51 AM

Re: Recursive Functions in ColdFusion
very cool. php code below based off same logic.

$node = 0;
$tree = "";
function treeview($branch,$node){
$chkcld = "";
$ObjNav = "";
$tree = $tree . "\r";
$qObjNav = mysql_query("SELECT * FROM architecture WHERE parent='$branch'");
while ($row = mysql_fetch_array($qObjNav)){
$ObjNavId = $row["id"];
$qObjNavX = mysql_query("SELECT * FROM architecture WHERE parent='$ObjNavId'");
if ($rowX = mysql_fetch_array($qObjNavX)){
$ObjNavIdX = $row["id"];
$tree = $tree . "" . $ObjNavId .(treeview($ObjNavIdX,$node+1,$limit)) . "\r\r";
} else {
$tree = $tree . "" . $ObjNavId . "\r";
}
}
$tree = $tree . "\r";
return $tree;
}
echo(treeview());
?>
Posted by daniel esquivias on July 14, 2006 at 1:05 AM

Re: Recursive Functions in ColdFusion
looks like html ul/li items taken out. (add 'ul' or 'li' next to '\r')..
once again, nice code..thanx.
Posted by daniel esquivias on July 14, 2006 at 1:08 AM

Re: Recursive Functions in ColdFusion
Very nice. I posted a very similar idea a couple of years ago, with source code, on the Macromedia Dev Center. See http://www.adobe.com/devnet/coldfusion/extreme/xml_menu.html.

Also, I just posted another use of recursion, one that also nests queries, but this one to build Flex Tree XML from ColdFusion queries. See http://www.forta.com/blog/index.cfm/2006/8/24/Building-Flex-Tree-MXML-From-ColdFusion-Queries.

--- Ben
Posted by Ben Forta on August 25, 2006 at 12:06 AM

Re: Recursive Functions in ColdFusion
Doug, nicely done. Now, what's the best way to handle renumbering your menu order, for a particular ParentID, whenever you add or delete an item in your menu? Say you wanted to add a menu item between ID 7 and 8 to 'Create User Roles'? Or delete nav order item 4 within a list of 8?
Posted by Cutter on August 25, 2006 at 3:17 AM

Re: Recursive Functions in ColdFusion
Hey Cutter, I posted some info on how I maintain my navigation data. You can read it at http://www.dougboude.com/blog/1/2006/08/Maintaining-Hierarchical-Navigation-Data.cfm
Posted by dougboude on August 25, 2006 at 5:53 PM

Re: Recursive Functions in ColdFusion
You should read this article that does recursion by sorting an array instead of actually recursing the function:
http://rickosborne.org/blog/?p=3
Posted by duncan on February 21, 2007 at 4:28 AM

Re: Recursive Functions in ColdFusion
Thanks for this post. I was working on a recursive function, but was having problems because I was not using the variable scope. This post told me exactly what I needed to solve the problem.
Posted by splavs on April 10, 2008 at 11:57 AM

Re: Recursive Functions in ColdFusion
Hey, glad it helped you, Scott! Recursion can be a little intimidating at first, and challenging to learn how to "think about" it. But, it's all about scope, man, all about scope.
Posted by dougboude on April 11, 2008 at 12:12 PM

Re: Recursive Functions in ColdFusion
This is exactly what i needed! I started out with code like you show in the top example and quickly realized the limitations. I could not wrap my brain around it until i read your post.

Thanks!
Posted by Chad on March 4, 2009 at 9:42 AM

Re: Recursive Functions in ColdFusion
Glad to be of help, Chad! Pay it forward. ;)
Posted by dougboude on March 4, 2009 at 10:37 AM

Re: Recursive Functions in ColdFusion
Thank you very much for the code. I would really appreciate if someone could help me here.

Let's imediately go to the problem I get.

It says to me: "Error Occurred While Processing Request, Variable QRYNAVIGATION is undefined.". It's the part where we do this .

Before running the code I wet through your code Dough and asked myself where do you take the "qryNavigation" variable from. Are you sure you didn't forget to mention something? Now I am surprised, how come no one noticed this problem. Or is just me? :) It can be that I missed something, so please, help.

I would Also like to ask you where should I place the navigation table. In which database? I am asking this because I don't see this information anywhere in your code.

This said I have to ask you, another basic thing which I still didn't learn about CF. Please be patient with me. :) Is it possible to write and use functions also in *.cfm files? I guess... my idea is that it is possible, since in Java, for instance, you can also write methods in class definitions as you can do it in *.java files. So I guess in CF it must be the same - you can write functions in *.cfm and in *.cfc files. Am I right? :)

I am not new in programming and recursive functions / methods are nothing new to me either. I've been studying some basic recursion examples in C languange, so I understand it's importance and role. I also have experience in PHP where I used a code for the same recursive problem (challenge :) ). It's just that I am new to coldfusion and I am still a bit slow. :) However I do understand the basics, because as I said, I have experience in other programming and script languages (PHP,Java,C), so I do understand the basic concepts like functions, its arguments, return values etc.

Thank you a lot in advance for your help!
Posted by alexcombo on August 4, 2009 at 7:30 PM

Re: Recursive Functions in ColdFusion
Obviously your system cuts all html tags. :) Here is what I wanted to say at the end of the third paragraph of my previous post:

"It's the part where we set the variables.navigation variable."
Posted by alexcombo on August 4, 2009 at 7:34 PM

Re: Recursive Functions in ColdFusion
About the query "qrynavigation"... now I think I understand a bit more. Do I have to define a query named "qrynavigation". How does this query have to look like? I saw you made a cfloop query="qrynavigation". But I don't quite understand how it aplies to the second code - the recursive one. Again, as I said, please be patient with me. I am still learning CF. :) Maybe I will understand more tomorrow. Now It's time to go to bed here, :)
Posted by alexcombo on August 4, 2009 at 7:46 PM

Re: Recursive Functions in ColdFusion
Heh... as I said, I had to get a good sleep. Today in the morning I only added the navigation table to the database and the needed query in the code and it's working! So to be honest I answered to my questions by myself. :) It always helps me writing about the code problems I am having. Mostly I figure them out before anyone manages to write me back. :)
Posted by alexcombo on August 5, 2009 at 5:22 AM

Re: Recursive Functions in ColdFusion
Hm... I was thinking... how much would I have to change your recursive code in order to make a navigation with a functionality like here: www.vago.si ?
Posted by alexcombo on August 5, 2009 at 7:48 AM

Re: Recursive Functions in ColdFusion
Hey Dough! Here is what I've done so far with my navigation menu with recursion. I am stuck, so I posted my problem with the code I've written here: http://www.dreamincode.net/forums/index.php?showtopic=119043.

Would be very grateful if you or anyone could help.

Thank you very much
Posted by ComboAlex on August 7, 2009 at 5:33 PM

Re: Recursive Functions in ColdFusion
Thanks... very helpful!
Posted by Jason on December 15, 2011 at 12:13 PM

Re: Recursive Functions in ColdFusion
This code works perfect. I copied it into my code, changed the query/table field names, and away we go!!! Awesome. This is very cool Saves me from writing an unforeseen quantity of sub-levels from a ColdFusion Query Object. However, it seems to run about 10-20% slower than your original code. I'm not sure this is the best way to approach ColdFusion "recursion", given that it does not "really" look at it's parent (super) class for the sub-levels of each node. At this point, this is a (cfml) function that takes parameters/arguments to dynamically loop over Query-of-Queries (Q-of-Q) advanced array searching. This actually creates 2x as many Q-of-Q query objects, each of which are process-intensive. I'm thinking there may be a very similar approach to what you're suggesting here, but perhaps with a more object-oriented approach. I'm using a simple alternative that uses "IF - ELSE IF - ELSE - END IF" statements within the 1st CFML Q-of-Query output/loop and a "TEMP" HTML string variable using CFSAVECONTENT. This approach actually USES YOUR CODE, but instead of returning UL...LI...LI a line at a time, it builds the list hierarchy before presenting it to the HTML output stage. Just thought'd I give out a hollah! Thanks again Dr. Doug for opening my mind. -- Marty McGee
Posted by Marty McGee on January 22, 2012 at 1:01 PM

Re: Recursive Functions in ColdFusion
Doug - you're a lifesaver. I was trying to work out how to output a categorisation list in a tree format to drive advanced search on a search engine I'm building and good old CFTREE just wasn't going to cut it. Your solution driving an unordered list into JSTREE is exceptionally elegant.
Posted by KP on August 8, 2013 at 7:13 PM

Re: Recursive Functions in ColdFusion
This is the only post on the WORLD WIDE WEB that explains how to handle this highly efficient data structure. I have an identical structure, but I'm trying to use cftree. Can you offer any guidance? Is it possible. Great post. It really helped me...
Posted by Dwayne on October 25, 2013 at 3:47 PM

Name:   Required
Email:   Required your email address will not be publicly displayed.

Want to receive notifications when new comments are added? Login/Register for an account.

Time to take the Turing Test!!!

Twelve plus Eight equals
Type in the answer to the question you see above:

Your comment:

Sorry, no HTML allowed!