Ask Ben: Simple Recursion Example

Posted December 5, 2007 at 9:40 AM

Tags: ColdFusion, Ask Ben

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 »

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 »

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 »

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 »

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 »

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

Post Comment  |  Ask Ben  |  Permalink  |  Other Searches  |  Print Page

• Add To Del.icio.us
• Add To Digg
• Add to Spurl.net
• Add to Wists
• Add to Simpy
• Add to Newsvine
• Add to BlinkList
• Add to Furl
• Add to reddit
• Add to FARK
• Add to BlogMarks
• Add to Yahoo! My Web
• Add to smarking
• Add to Ma.gnolia
• Add to Segnalo

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.

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

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

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

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

@Frank,

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

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/

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

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!

@Stacey,

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

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

@Al,

That's what I like to hear :)

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

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

Post Comment  |  Ask Ben

Post A Comment

Please review the following issues:

Author Name:
Author Email:
Author Website:
Comment:	Formatting: <strong>bold</strong> <em>italic<em>
	Remember my information
	Subscribe to entry *
	Send me a copy of this comment (as part of the comment thread)

 

* If you subscribe, any new posts to this thread will be sent to your email address.