Ben Nadel
On User Experience (UX) Design, JavaScript, ColdFusion, Node.js, Life, and Love.
I am the chief technical officer at InVision App, Inc - a prototyping and collaboration platform for designers, built by designers. I also rock out in JavaScript and ColdFusion 24x7.
Meanwhile on Twitter
Loading latest tweet...
Ben Nadel at CFUNITED 2010 (Landsdown, VA) with:

Ask Ben: Simple Recursion Example

By Ben Nadel on

Not a specific question here; some people have seen me use recursion when dealing with user defined functions and ColdFusion custom tags and have asked to demonstrate a simple example of recursion to help get more comfortable with it. Recursion is a very powerful tool that is required to solving some problems, but at the same time, when wielded improperly, it can be a huge drain on system resources, and if let run uncontrolled, can eat up all memory in your RAM. As such, it is important to understand how recursion works and how to use it most effectively.

Most of you have probably already seen the dangerous side of recursion and not even realized that's what you were seeing. Have you ever tried to execute a CFDump tag only to have your server become unresponsive for a minute? If you have, it's because you've launched a recursive path that had no feasible end path scenario. When it comes to CFDump, this is due to circular references. Look at the following code:

  • <!--- Create two objects. --->
  • <cfset objBen = StructNew() />
  • <cfset objMariaBello = StructNew() />
  •  
  • <!--- Set up two-way friendship. --->
  • <cfset objBen.Friend = objMariaBello />
  • <cfset objMariaBello.Friend = objBen />
  •  
  • <!--- Dump out Ben (limit it to 9 levels deep). --->
  • <cfdump
  • var="#objBen#"
  • top="9"
  • label="Ben"
  • />

Here, we are setting up two people and then bi-directionally associating them as friends (meaning, each of the two people knows that the other one is a friend). Seems harmless right? Well, when we execute that code, we get the following CFDump output:


 
 
 

 
CFDump Recursion Problem (Infinite Nesting Via Circular References)  
 
 
 

Notice that the CFDump seems to just keep going and going. Had we not had the foresight to put a limit of 9 levels on the output, this CFDump would have timed out after 20 seconds and possibly would have made the server totally unresponsive in that time.

So now, let's step back and look at what recursion in. Recursion is simply the use of a function which, as part of it's own execution code, invokes itself (as seen in this diagram):


 
 
 

 
Recursive Execution Path Explained  
 
 
 

As you can see above, the Test() method keeps calling itself. With every Test() method invocation, a new local scope is set up for that function body and a set of parameters (arguments) is passed to it (although, no arguments are used in our example). For each currently executing Test() function, the function cannot return (finish executing) until its nested Test() method call returns.

Now, going back to the CFDump example, the pseudo code for the internal Dump() function probably looks something like this:

  • Dump( obj ){
  • If obj is simple (string, number, etc).
  • Output value
  •  
  • If obj is complex
  • Output name
  •  
  • For each attribute
  • Dump( attribute )
  •  
  • Return
  • }

Notice that when we have complex objects, the Dump() function is recursively calling itself to help output each sub-item of the complex object. Now you can see that if we have two objects that have pointers to each other (as we did in our first example), this recursion will never end:

Dump( A )
- Dump( A.B )
-- Dump( B.A )
--- Dump( A.B )
---- Dump( B.A )
----- Dump( A.B )

Don't get me wrong idea here - recursion is far from bad. In fact, it's a wonderful, essential tool for programmers. You just have to be sure that you build in features to your recursive function that allow each recursive path to eventually reach some sort of end point, at which point the function can return out (or return a value). With our CFDump example, the end point was the depth of recursion as defined by the TOP attribute (9 levels).

So, just to reiterate, cause this is a really important point, the key to building an effective recursive function is to give it logic that helps to ensure that the paths of execution cannot be infinitely long. That is, give it logic that allows for a scenario in which the recursive function can execute WITHOUT re-invoking itself.

Now that you have a basic understanding of what it means to be recursive, let's take a look at a real world example: the family tree. We're going to keep it very simple - each member of the family tree has a single parent and we want to output the family tree as a bunch of nested unordered lists (UL elements).

First, we have to create the family tree data. As usual, I will build this data in a temporary SQL data table and then select out of that table:

  • <!--- Query for family lineage. --->
  • <cfquery name="qFamily" datasource="#REQUEST.DSN.Source#">
  • <!--- Declare the temp table to hold our family data. --->
  • DECLARE @family TABLE (
  • id INT,
  • name VARCHAR( 20 ),
  • parent_id INT
  • );
  •  
  •  
  • <!--- Populate the family table. --->
  • INSERT INTO @family
  • (
  • id,
  • name,
  • parent_id
  • )(
  • <!--- Grandmother. --->
  • SELECT 1, 'Micky', 0 UNION ALL
  •  
  • <!--- Other Grandmother. --->
  • SELECT 2, 'Stella', 0 UNION ALL
  •  
  • <!--- Mother. --->
  • SELECT 3, 'Arlene', 2 UNION ALL
  •  
  • <!--- Father. --->
  • SELECT 4, 'Bruce', 1 UNION ALL
  •  
  • <!--- Brother. --->
  • SELECT 5, 'Ari', 3 UNION ALL
  •  
  • <!--- Brother. --->
  • SELECT 6, 'Erik', 3 UNION ALL
  •  
  • <!--- Sister. --->
  • SELECT 7, 'Zoe', 3 UNION ALL
  •  
  • <!--- Sister. --->
  • SELECT 8, 'Emily', 3 UNION ALL
  •  
  • <!--- Niece. --->
  • SELECT 9, 'Gabby', 6 UNION ALL
  •  
  • <!--- Nephew. --->
  • SELECT 10, 'Max', 6 UNION ALL
  •  
  • <!--- Niece. --->
  • SELECT 11, 'Sophia', 5 UNION ALL
  •  
  • <!--- Niece. --->
  • SELECT 12, 'Lulu', 5 UNION ALL
  •  
  • <!--- ME. --->
  • SELECT 13, 'Ben', 3
  • );
  •  
  •  
  • <!--- Query for family tree. --->
  • SELECT
  • f.id,
  • f.name,
  • f.parent_id
  • FROM
  • @family f
  • </cfquery>

Here, each record in our @family data table has an ID (unique identifier), a name, and a parent ID (the ID of another record in the same table). What we want to do now is output the family tree in HTML starting with the family members who don't have a parent ID (parent_id = 0) and then working our way down through the generations.

Let's jump right into the recursive ColdFusion function for this task, OutputChildren():

  • <cffunction
  • name="OutputChildren"
  • access="public"
  • returntype="void"
  • output="true"
  • hint="Outputs the children of a given parent.">
  •  
  • <!--- Define arguments. --->
  • <cfargument
  • name="Data"
  • type="query"
  • required="true"
  • hint="Family tree data query."
  • />
  •  
  • <cfargument
  • name="ParentID"
  • type="numeric"
  • required="false"
  • default="0"
  • hint="The ID of the parent who's children we want to output."
  • />
  •  
  • <!--- Define the local scope. --->
  • <cfset var LOCAL = StructNew() />
  •  
  •  
  • <!--- Query for the children of the given parent. --->
  • <cfquery name="LOCAL.Children" dbtype="query">
  • SELECT
  • id,
  • name
  • FROM
  • ARGUMENTS.Data
  • WHERE
  • parent_id = <cfqueryparam value="#ARGUMENTS.ParentID#" cfsqltype="cf_sql_integer" />
  • ORDER BY
  • name ASC
  • </cfquery>
  •  
  •  
  • <!---
  • Check to see if we found any children. This is our
  • END case scenario. If there are no children then our
  • recursion will come to a stop for this path.
  • --->
  • <cfif LOCAL.Children.RecordCount>
  •  
  • <ul>
  • <!--- Loop over children. --->
  • <cfloop query="LOCAL.Children">
  •  
  • <li>
  • #LOCAL.Children.name#
  •  
  • <!---
  • Now that we are looking at a particular
  • child, we want to recursively call this
  • function (from within itself) to see if
  • this child has, itself, some children.
  •  
  • We are passing along the same data set,
  • but instead of passing along the
  • original ParentID, we passing along THIS
  • child's ID as the next round or Parent
  • IDs.
  • --->
  • <cfset OutputChildren(
  • Data = ARGUMENTS.Data,
  • ParentID = LOCAL.Children.id
  • ) />
  • </li>
  •  
  • </cfloop>
  • </ul>
  •  
  • </cfif>
  •  
  • <!--- Return out. --->
  • <cfreturn />
  • </cffunction>

The OutputChildren() UDF can take one or two arguments. The first argument is the data query that we are working with (the family tree query from above). The second argument is the ID of the parent for whom we want to output the children. If no parent ID is passed in, we will assume that it should be zero.

To kick of the function, we immediately perform a ColdFusion query of queries to get all the children of the given parent ID. If NO children are found, then the function simply returns out. This is VERY IMPORTANT because this is our "end point"; this is the logic that prevents all recursive paths from becoming infinite, assuming valid data. Remember, in order for recursion to be leveraged effectively, you have to have some logic that allows the recursive function to execute WITHOUT re-invoking itself.

If, on the other hand, child records are found, we output each child name, and then, for each child name, we recursively call the OutputChildren() function, but this time, we pass in the ID of the current child as the ParentID value. If it's confusing, try putting yourself directly into the scenario: the function executes with your "father" as the parent. We then query for all children of your father. This returns YOU as the record. We then output your name and recursively call the OutputChildren() method, but this time, instead of your father, we are passing YOU as the father. As such, the recursively called function would be looking for YOUR children, and then your children's children, and so on.

Once we have our recursive function defined, we just need a way to kick it off. In our case, since the ParentID argument will default to zero, allowing the oldest family members to be output first, we can simply call the method and pass in the data query:

  • <!---
  • Output the family tree using the Zero ID as the
  • ulimate parent (meaning, those family memebers with
  • zero parent ID will be at the top of our tree).
  • --->
  • <cfset OutputChildren(
  • Data = qFamily
  • ) />

This executes the recursive function and outputs the family tree:

  • Micky
    • Bruce
  • Stella
    • Arlene
      • Ari
        • Lulu
        • Sophia
      • Ben
      • Emily
      • Erik
        • Gabby
        • Max
      • Zoe

Are you beginning to see the possibilities?

You might think that you can replace a recursive function with several nested FOR loops, but you would soon find out that this is not true. The beauty behind recursion is that you can search through a dynamic number of levels in your problem. FOR loops do not have this benefit. In order to mimic recursion, you'd have to have an infinite number of nested FOR loops.

Recursion is used all over the place and in tons of algorithms - everything from directory trees to artificial intelligence. I have never actually explained this to anyone, so I hope that this does more good than harm, and maybe just maybe, got you excited about the empowerment that recursion can give you.

Tweet This Interesting post by @BenNadel - Ask Ben: Simple Recursion Example Thanks my man — you rock the party that rocks the body!



Reader Comments

Thanks for this illustration Ben. I've understood the concept of recursion, but never had a need for it. Seeing this example helped me get it straight in my head. You have a knack for breaking a complex concept down and teaching others.

Reply to this Comment

@Matt,

Thanks. I try to break it down as much as I can so that I can make sure that I understand it :) What's that saying, that if you can't explain something in simple terms, you don't understand it.

Regardless, though, I think once the recursion bug bites you, will feel the power. I don't use it all that much because the needs is not great. But once you see where it can be used, you can really build some effective solutions.

Reply to this Comment

Good article, and there are tons of practical applications of recursion. Some of the most common tasks I find myself applying recursion to are multi-tiered menus and breadcrumbs.

I've seen some more novice programmers use a finite series of loops as Ben suggested and then set an "unlikely" upper bound to limit it (e.g., allow 10 repetitions when only 3 -5 are expected) but it's important to realize that this is not scalable. What happens when your boss comes with a new case where you need more levels. And why would you want to loop 10 times if you only end up needing 3? If you ever find yourself setting these kinds of upper bounds for repetitive tasks, it might be an appropriate situation for recursion.

Reply to this Comment

Hi Ben,

Your are dam good man in explaining things.

Love your posts.

Many thanks for such a great hard work.

Regards

Reply to this Comment

@William,

Thanks for those examples, I like it. Also, like you are saying, nested loops can be a valid solution on small, highly predictable nesting. However, the second anything starts to scale you are in trouble.

@Sana,

Thanks for the kind words. If you ever want me to try and explain anything specifically, just let me know :)

Reply to this Comment

Ben,

Thanks for all this. Like you and other posters' comments about the nested ifs and loops...That is exactly what I am doing and it is not so predictable. There will always be an exception, then what will I do, add another loop? No thank you. Besides when I am hours, days, months away from this application I don't want to get the call to fix it so better to do it right.

Frank

Reply to this Comment

Great explanation of recursion, Ben. A few months ago I was looking for a query sorting solution that dealt with child/parent relationships, as you used in your example. I read a post on recursion on Doug Boude's site (http://www.dougboude.com/blog/1/2006/06/Recursive-Functions-in-ColdFusion.cfm).
In the comments of that post, there was a link to an alternative method on Rick Osborne's blog, where he points out that in large or deeply nested trees, the downside to recursion in CF is in it's performance. He then presents what I thought was a pretty ingenous way of "unraveling" recursion using a more iterative method of sorting nested queries. From a coding perspective, I think recursion is much simpler than Rick's method, but it is definitely worth a read.

http://rickosborne.org/blog/index.php/2005/10/11/writing-a-parent-child-query-sorted-in-cf-part-1/

Reply to this Comment

@Tony,

Rick is a really bright guy and has taught me some awesome optimization tips, especially when it comes to leveraging ColdFusion structs for indexing, which it looks like he might be doing in his solution (which I have to go back and fully read). I am sure it is a solid solution and will take a look. Thanks for pointing this out.

Reply to this Comment

Thank you VERY much! For some reason, it hadn't occurred to me that CF could even *do* recursion - I just assumed I had to come up with some klunky work-around out of counts and loops.

Duh! This makes the dynamic tree view I've been working on MUCH simpler.

Danke, dahling!

Reply to this Comment

Ben,
The solution is real simple. I ot stuck while processing a tree data structure using recursion and after seeing your solution I was able to solve it.

Thx
AL

Reply to this Comment

Ben,
I've come across this post in the past and it helped me solve my simple parent/child output issue perfectly. Now I have a database structure that that has parent/child references but more complexly has children that have their parent as their children to allow cyclical processing. This allow me to know that they wish to repeat a previous step in the process. The idea is that the user is presented with the next steps then asked what now? This could be various children which could include itself or previous parent.

Is there any way that I could easily mark this record as already output and to ignore this child result the second time around during the loop to prevent over running the Java Heap due to improper recursion?

Hope my concept makes some sense, any ideas would be much appreciated. I like the new blog.

<pre>
example Table Data

ID ParentID ChildID
1 0 1
2 1 2
3 2 3
4 2 4
5 3 3
6 3 5
7 4 2
8 4 6

</pre>
1 leads to 2.
2 leasds to 3 or 4
3 leads to ITSELF or 5 (which is an end point)
4 leads back to 2 or to 6(which is an end point)

End point is when it is not the parent of anything....

Cheers,
Tim

Reply to this Comment

@Tim,

You could create a struct for indexing the used records:

<cfset usedIDs = {} />

Then, every time you are going to output a record, check to see if it has already been output:

<cfif !structKeyExists( usedIDs, id )>

<!--- Keep track of this ID. --->
<cfset usedIDs[ id ] = true />

</cfif>

Reply to this Comment

Thanks so much Ben. What a great code sample :)

I did this (kind of) on sql server: using trigger to control navigation menus with tree-depth and tree-lineage... Now with your code, I can do recursion in CF...

Reply to this Comment

If there is one child with ChildID = one of previous ancester ID (higher parentID), this code with go into infinite loop. I added a new column "tree-depth" and pass it on to every calls...

Reply to this Comment

@Tuyen,

Yeah, often times when you deal with recursion, you need to set some sort of depth limit.

Reply to this Comment

I posted a comment related to the topic and asking a question of my own, but it was deleted, probably for the long code block, but I really would like to know the answer.

It is possible to rewrite an infinite recursive function as a single for loop. You only have to create an array to store the recursive index values. For example:

  • var stack=ArrayNew(1);
  • for (i=1; i LTE maxval; i=i+1)
  • {
  • if (isEndConditionMet)
  • {
  • i=pop(stack);//Restore state.
  • }
  • //One place you can do something.
  • if (needToDoRecursion)
  • {
  • ArrayAppend(stack,i);//Save state.
  • i=0;//Zero because the incrementer will be called.
  • }
  • }

The question I had was when I tested it with the long code block from before (a rewrite of your recursive version), with a small number of test iterations the time difference seemed negligible, but when I increased the number of iterations, the recursive function actually seemed faster most of the time.

This is counterintuitive. Shouldn't the function call overhead of the recursive function take much longer than just poping and pushing (ArrayAppend) state information from a stack?

Reply to this Comment

I ran into another issue playing with your recursive function.

I decided to rewrite it with modifying as little as possible to make it non-recursive.
This meant that instead of converting it to cfscript, I kept it tag based.

When doing this, I could not figure out why the index would not accept the changed values. It kept incrementing each loop.

I was using a cfloop index loop. I decided to instead try cfloop condition, and add a line to initialize and a line to increment the counter myself. This suprisingly worked!

Why can I modify the loop counter in cfscript, and in a conditional cfloop, but not in an index cfloop?

Reply to this Comment

@Jdyer,

ColdFusion doesn't do it, but I have been shown that many compilers in other languages will actually turn "tail recursion" into a loop (in the same spirit as what you have done). That kind of optimization is beyond my understanding.

Reply to this Comment

Great work on explaining recursion... i always had trouble understanding quite a lot of the other tuts online on this topic.

Just a question though, how would you keep track of which level your currently in ? example would be im building a left nav menu and for the 3rd and 4th levels deep i would want to apply a specific class so i can show / hide them but im stumped as to how to keep track of where the recursion is up to... any ideas greatly appreciated

Reply to this Comment

@dimrie,

The easiest way would be to pass in the level, or use a global counter.

Method one--Passing it in.

  • <cffunction name="OutputMenu" access="public" returntype="void" output="true" hint="Outputs the child menu of a given parent.">
  •  
  • <!--- Define arguments. --->
  • <cfargument name="Data" type="query" required="true" hint="Menu tree data query." />
  •  
  • <cfargument name="ParentID" type="numeric" required="false" default="0" hint="The ID of the parent who's children we want to output." />
  •  
  • <cfargument name="RecursionLevel" type="numeric" required="false" default="0" hint="The level of recursion.">
  •  
  • <!--- Define the local scope. --->
  • <cfset var LOCAL = StructNew() />
  •  
  • <!--- Query for the children of the given parent. --->
  • <cfquery name="LOCAL.Children" dbtype="query">
  • SELECT id, name
  • FROM ARGUMENTS.Data
  • WHERE parent_id = <cfqueryparam value="#ARGUMENTS.ParentID#" cfsqltype="cf_sql_integer" />
  • ORDER BY name ASC
  • </cfquery>
  •  
  • <!---
  • Check to see if we found any children. This is our
  • END case scenario. If there are no children then our
  • recursion will come to a stop for this path.
  • --->
  • <cfif LOCAL.Children.RecordCount>
  •  
  • <ul>
  • <!--- Loop over children. --->
  • <cfloop query="LOCAL.Children">
  •  
  •  
  • <li>
  • #LOCAL.Children.name#
  •  
  • <!---
  • Now that we are looking at a particular
  • child, we want to recursively call this
  • function (from within itself) to see if
  • this child has, itself, some children.
  •  
  •  
  • We are passing along the same data set,
  • but instead of passing along the
  • original ParentID, we passing along THIS
  • child's ID as the next round or Parent
  • IDs.
  • --->
  • <cfset OutputChildren(Data = ARGUMENTS.Data, ParentID = LOCAL.Children.id, RecursionLevel=RecursionLevel+1) />
  • </li>
  •  
  •  
  • </cfloop>
  • </ul>
  •  
  • </cfif>
  •  
  • <!--- Return out. --->
  • <cfreturn />
  • </cffunction>

The code is the same as the example above, except for three things. First, I changed the name of the function, as you are displaying a menu. Second, I added an argument RecursionLevel to keep track of the level of recursion. Third, I changed the recursive call to send in the recursion level variable incremented by one.

To do what you want, you can put your class names into an array and index into the array using this variable. (Be aware that array indices start with 1.)

For the global variable method, you add only two lines to the original function. One to increment the global variable immediately before making the recursive call, and one immediately after the recursive call to decrement the global variable.

I suggest passing it in though, as if you use a global variable, your variable could become clobbered through threading.

Reply to this Comment

@dimrie,

I made one minor mistake in my post. Since I changed the function name, the name in the recursive call should have been changed as well.

  • <cfset OutputMenu(Data = ARGUMENTS.Data, ParentID = LOCAL.Children.id, RecursionLevel=RecursionLevel+1) />

Not:

  • <cfset OutputChildren(Data = ARGUMENTS.Data, ParentID = LOCAL.Children.id, RecursionLevel=RecursionLevel+1) />

Reply to this Comment

Now looping through my trees of arbitrary depth and arbitrary quantity of child nodes is a breeze.

Reply to this Comment

@Dimrie,

I agree with @Jdyer; passing the depth is a great way to not only keep track of the level you are currently at, but also to make sure you don't go too deep in any one particular direction. Imagine a scenario in which you wanted to use some sort of algorithm to attempt to select the best move in a Game. You might use recursion, but there might be millions of moves to be considered (think Chess). In such a case, you might want to limit the recursive exploration to something like 5 moves. This way, the recursive algorithm can go 5 levels deep, then back up and try another set of moves.

@Kirill,

Awesome man, glad you liked it!

Reply to this Comment

Hey Ben,

Can you help me out. I am using your recursion code to create a navigation menu (nested Ordered Lists) and I am not having any luck creating the href's.

I need the href's to follow the pattern of the OL. The problem I am having is when to add and/or remove the different folders.

(I wasnt able to post the code so here is an image of the type of structure and href's I am trying to create...http://i.imgur.com/VliO5.jpg)

Thank you for the help.

Reply to this Comment

I got it working with the following code. Not sure how elegant or robust it is but it seems to work...

  • <cfargument name="url" type="string" required="false" default="" hint="the url path">
  •  
  • <cfset thisURL = arguments.url>
  •  
  • <cfif arguments.RecursionLevel EQ 0>
  • <cfset thisURL = "/" & local.children.name>
  • <cfelseif arguments.RecursionLevel GT prevRecursionLevel>
  • <cfset thisURL = listAppend(thisURL, local.children.name, "/")>
  • <cfelseif arguments.RecursionLevel LTE prevRecursionLevel>
  • <cfloop from="#arguments.RecursionLevel#" to="#prevRecursionLevel#" index="s">
  • <cfset thisURL = listDeleteAt(thisURL, listLen(thisURL, "/"), "/")>
  • </cfloop>
  • <cfset thisURL = listAppend(thisURL, local.children.name, "/")>
  • </cfif>
  • #thisURL#
  • <cfset prevRecursionLevel = arguments.RecursionLevel>
  • <cfset OutputChildrenSEF(data = arguments.Data, parent_fkid = local.children.id, RecursionLevel=RecursionLevel+1, url=thisURL) />

Reply to this Comment

@Ben,
@Josh,

Considering you said you were using the recursive code above, and assuming your children names are the names shown, such as "Apple", or "Granny Smith", (and I also assume the typo in the example for Granny Smith as it should have an ending slash as well) then you should only need to modify four lines and add two additional lines.

Change the ul to ol, create the url for the current menu item, add this url to the display, and to add the url to the recursive call as well as the function definition.

  • <cffunction name="OutputChildren" access="public" returntype="void" output="true" hint="Outputs the children of a given parent.">
  •  
  • <!--- Define arguments. --->
  • <cfargument name="Data" type="query" required="true" hint="Family tree data query." />
  •  
  • <cfargument name="ParentID" type="numeric" required="false" default="0" hint="The ID of the parent who's children we want to output." />
  • <!--- Added next line. --->
  • <cfargument name="ParentURL" type="string required="false" default="" hint="The URL for the parent who's children URLs we want to output." />
  •  
  • <!--- Define the local scope. --->
  • <cfset var LOCAL = StructNew() />
  •  
  • <!--- Query for the children of the given parent. --->
  • <cfquery name="LOCAL.Children" dbtype="query">
  • SELECT id,
  • name
  • FROM ARGUMENTS.Data
  • WHERE parent_id = <cfqueryparam value="#ARGUMENTS.ParentID#" cfsqltype="cf_sql_integer" />
  • ORDER BY name ASC
  • </cfquery>
  •  
  • <!---
  • Check to see if we found any children. This is our
  • END case scenario. If there are no children then our
  • recursion will come to a stop for this path.
  • --->
  • <cfif LOCAL.Children.RecordCount>
  •  
  • <!--- Mod ---> <ol>
  • <!--- Loop over children. --->
  • <cfloop query="LOCAL.Children">
  •  
  • <!--- Add ---> <cfset LOCAL.currentURL = "#Arguments.ParentURL/#LCase(ReReplace(LOCAL.Children.name," ","_","all"))#">
  •  
  • <li>
  • <!--- Mod ---> #LOCAL.Children.name# (#LOCAL.currentURL#/)
  •  
  • <!---
  • Now that we are looking at a particular
  • child, we want to recursively call this
  • function (from within itself) to see if
  • this child has, itself, some children.
  •  
  •  
  • We are passing along the same data set,
  • but instead of passing along the
  • original ParentID, we passing along THIS
  • child's ID as the next round or Parent
  • IDs.
  • --->
  • <!--- Mod ---> <cfset OutputChildren(Data = ARGUMENTS.Data, ParentID = LOCAL.Children.id, ParentURL = LOCAL.currentURL) />
  • </li>
  •  
  • </cfloop>
  • <!--- Mod ---> </ol>
  •  
  • </cfif>
  •  
  • <!--- Return out. --->
  • <cfreturn />
  • </cffunction>

Reply to this Comment

@Josh

Also, note that you can do any name conversions for the url, not just space to underscore. You could also check for private urls. Say mango is only allowed to be seen if you are a certain user. Then you could add the following psuedo code:

Coldfusion 9 or above (insert right after currentURL is created):

  • <cfif currentURL EQ "/mango" AND userLevel NEQ "admin"><!--- NOTE no trailing slash. This is intentional. --->
  • <cfcontinue />
  • </cfif>

For Coldfusion versions less than 9, instead of using the (non-existent) cfcontinue tag, you would just wrap the main part of your loop (everything you didn't want to execute) within the cfif tags.

Reply to this Comment

@Josh,
@Ben,

Sorry, but I made two quickie errors in my example code. The cfset for the current URL should read:

  • <cfset LOCAL.currentURL = "#Arguments.ParentURL#/#LCase(ReReplace(LOCAL.Children.name,' ','_','all'))#">

Reply to this Comment

A great post. Great explaination of recursion.
I am looking to incorporate breadcrumbs into my site and this sheds some light on some ways of doing it using recursive functions. Kudos

Reply to this Comment

Ben:

Thanks for a really excellent piece here. With a bit of modification I have prepared a schematic representation of this, using your underlying recursion idea, that provides forward and backward search capabilities and allows the storage of any number of trees that can be joined or separated at will. I also link to property maps done in Google maps showing how property boundaries have changed with transfer or inheritance.

Still having some problems accounting for multiple spouses with different children from each union, adopted or illegitimate children and idly wondered if you had given any more thought to this?

Ted Daniels

Reply to this Comment

Hi Ben, I am one of big fan of this blog.

If I want to make json output how should I use your code?
Such as

  • { "name": "Root",
  • "children": [
  • { "name": "Micky",
  • "children": [
  • {
  • "name": "Bruce"
  • }
  • ]
  • },
  • { "name": "Stella",
  • "children": [
  • { "name": "Arlene",
  • "children": [
  • { "name": "Ari",
  • "children": [
  • {"name": "Lulu"},
  • {"name": "sophia"}
  • ]
  • },
  • {"name": "Ben"},
  • {"name": "Emily"},
  • {"name": "Erik",
  • "children": [
  • {"name": "Gabby"},
  • {"name": "Max"}
  • ]
  • },
  • {"name": "Joe"}
  • ]
  • }
  • ]
  • }
  • ]
  • }

Can you help me?

Thanks,

Reply to this Comment

Post A Comment

You — Get Out Of My Dreams, Get Into My Comments
Live in the Now
Oops!
Comment Etiquette: Please do not post spam. Please keep the comments on-topic. Please do not post unrelated questions or large chunks of code. And, above all, please be nice to each other - we're trying to have a good conversation here.