Ask Ben: Simple Recursion Example : Kinky Solutions : A Student's Perspective by Ben Nadel

Ask Ben: Simple Recursion Example

Posted December 5, 2007 at 9:40 AM

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:

Launch code in new window » Download code as text file »

<cfset objBen = StructNew() />
<cfset objMariaBello = StructNew() />
<cfset objBen.Friend = objMariaBello />
<cfset objMariaBello.Friend = objBen />
<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:

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

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:

Launch code in new window » Download code as text file »

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:

Launch code in new window » Download code as text file »

<cfquery name="qFamily" datasource="#REQUEST.DSN.Source#">
DECLARE @family TABLE (
id INT,
name VARCHAR( 20 ),
parent_id INT
);
INSERT INTO @family
(
id,
name,
parent_id
)(
SELECT 1, 'Micky', 0 UNION ALL
SELECT 2, 'Stella', 0 UNION ALL
SELECT 3, 'Arlene', 2 UNION ALL
SELECT 4, 'Bruce', 1 UNION ALL
SELECT 5, 'Ari', 3 UNION ALL
SELECT 6, 'Erik', 3 UNION ALL
SELECT 7, 'Zoe', 3 UNION ALL
SELECT 8, 'Emily', 3 UNION ALL
SELECT 9, 'Gabby', 6 UNION ALL
SELECT 10, 'Max', 6 UNION ALL
SELECT 11, 'Sophia', 5 UNION ALL
SELECT 12, 'Lulu', 5 UNION ALL
SELECT 13, 'Ben', 3
);
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():

Launch code in new window » Download code as text file »

<cffunction
name="OutputChildren"
access="public"
returntype="void"
output="true"
hint="Outputs the children of a given parent.">
<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."
/>
<cfset var LOCAL = StructNew() />
<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>
<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>
<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:

Launch code in new window » Download code as text file »

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

Download Code Snippet ZIP File

Related Blog Entries

Exercise List: Where Do I Go From Here?

Creating Thread-Safe Components With OnMissingMethod()

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.

Posted by Matt Wiliams on Dec 5, 2007 at 10:20 AM

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

Posted by Ben Nadel on Dec 5, 2007 at 10:24 AM

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.

Posted by William on Dec 5, 2007 at 12:06 PM

Hi Ben,

Your are dam good man in explaining things.

Love your posts.

Many thanks for such a great hard work.

Regards

Posted by Sana on Dec 5, 2007 at 12:06 PM

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

Posted by Ben Nadel on Dec 5, 2007 at 12:12 PM

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

Posted by Frank Tudor on Dec 5, 2007 at 1:46 PM

@Frank,

Niiiice. Do it the right way now, get all the benefits later :)

Posted by Ben Nadel on Dec 5, 2007 at 2:04 PM

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/

Posted by Tony Garcia on Dec 6, 2007 at 9:13 AM

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

Posted by Ben Nadel on Dec 6, 2007 at 5:05 PM

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!

Posted by Stacey Burns on Jan 7, 2008 at 4:29 PM

@Stacey,

Glad to have cleared that up. Let me know if you have any other roadblocks.

Posted by Ben Nadel on Jan 7, 2008 at 4:35 PM

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

Posted by AL on Apr 11, 2008 at 4:52 AM

@Al,

That's what I like to hear :)

Posted by Ben Nadel on Apr 11, 2008 at 7:14 AM

Post Comment | Ask Ben

Ask Ben: Simple Recursion Example : Kinky Solutions : A Student's Perspective by Ben Nadel