Ask Ben: Simple Recursion Example

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.

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.

Hi Ben,

Your are dam good man in explaining things.

Love your posts.

Many thanks for such a great hard work.

Regards

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

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/

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!

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

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

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...

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...

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?

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?

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

@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.

@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) />

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

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.

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) />

@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>

@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.

@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'))#">

WOW! So simple. Thanks for the help Ben. I really appreciate it.

Josh

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

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

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,