Welcome!

You will be redirected in 30 seconds or close now.

ColdFusion Authors: Yakov Fain, Jeremy Geelan, Maureen O'Gara, Nancy Y. Nee, Tad Anderson

Related Topics: ColdFusion

ColdFusion: Article

Recursive Custom Tags

Recursive Custom Tags

I have a confession to make: I wasn't a computer science major in college - I was a philosophy major. While the two disciplines have much in common (conceptual acrobatics, a high degree of abstraction, logical and analytical rigor, obtuse and convoluted texts), I'm finding now that, as a Web applications developer, a study of the basic tenets of computer science can help me create more sophisticated applications.
Case in point: the study of data structures and algorithms.

I recently had a programming problem to solve, one that lent itself perfectly to a solution offered in any data structures textbook. My problem was this: I was working with librarians on our campus on a project, part of which entailed the creation of a subject terms list. Once compiled, this hierarchical list of subject terms would be used as a controlled vocabulary to index items in our database. Although the list of terms the librarians came up with consisted of two levels (a general term and a specific term), there was no guarantee that in the future there wouldn't be a need to further subdivide the second level into a third level, and that level into a fourth and so on. In short, the number of levels in the hierarchy could be variable. So how should the data for this project be stored, and how should I then programmatically extract it as needed?

After pondering several scenarios involving multiple tables and confusing looping mechanisms, I decided to consult a colleague for advice. He took one look at the situation and, having had solid training in computer science theory, planted two buzzwords in my head: tree and recursion. Armed with this information, I scoured the Web and the library in search of information about trees as data structures and how recursive functions can be used to navigate them.

Storing a Tree Structure
Insofar as the list of subject terms is in a hierarchy, with a term serving as root and subterms serving as branches, it is properly described as a tree data structure. My solution with respect to how it should be stored in the back-end database is to store the entire tree in a single table consisting of three fields. The first field, "SUBJECTID", serves as the primary key, uniquely identifying each row. The second field, "SUBJECT", holds the text of the subject term itself, for example, "Italian Landscapes." The third field, "PARENTID", serves as a pointer to the next item up the hierarchy from the current term. Thus the parent of the term "Italian Landscapes" might be something like "Italian Art," and the parent of the term "Italian Art" might be something like "Art History" and so forth. In this manner, each term in the table is linked to its conceptual parent all the way to the top of the tree where there are base terms that themselves don't have parents. These terms represent the starting points in the tree structure and have, by default, PARENTIDs of 0. Figure 1 represents how this tree structure is stored in a table (the "lookupSubjects" table) in the back-end database.

Recursion
But now that the data is properly stored, the question remains: How do we programmatically access it? For instance, chances are at some point we'd want to print out the entire table in outline form, with those subject terms lacking parents at the base and other items down the branches printing in indented form. How to do this? There must be some sort of loop involved here, but what is the nature of this loop? How does it know, in a structure where the length of each branch is variable, when to stop? The conceptual key to doing this is known as recursion.

A recursive function is a function (or method, custom tag or other chunk of code) that calls itself. It is essentially a loop, executing over and over again until some sort of "base condition" is met. In fact, the tasks that many recursive functions are used to accomplish can instead be carried out using various FOR and WHILE loops, but using a recursive function is often thought to be a more elegant solution.

To print out the contents of the lookupSubject table in outline form, I created a custom tag called "simpleBuildTree". This tag results in the output represented by Figure 2.

Listing 1 is the code for the cf_simpleBuildTree custom tag. It is worth going over line by line.

cf_simpleBuildTree

First, this custom tag is called in the usual way:

<cf_simpleBuildTree>

Line 1 of the tag sets a default value of 0 for a variable, #theID#, which is used to retrieve records from the database later on. If, however, #theID# is being sent as an attribute to the tag, it is rescoped in lines 3-5 so that it can simply be referred to as #theID# instead of #attributes.theID#.

Lines 7-12 represent the "getCurrentItems" query. This query selects all records from the table whose PARENTIDs match the value of the current #PARENTID# variable. This value by default is set to 0, so the first time this query is run it will return all records appearing at the very top of the tree structure, that is, all records that are themselves not children of any other parent record. Referring back to Figure 1 for a minute, only two records fit this criterion - the record for "Arts and Humanities" and the record for "General and Reference." Thus these two entries will serve as roots in the tree structure - and from these two roots all branches will grow.

Line 14 begins an unordered list, and line 16 begins a loop through the records retrieved by the getCurrentItems query (our two records).

Lines 18-20 output the current value of #getCurrentItems.subject# as a list item within the unordered list.

Line 22, however, is where the fun begins.

It's possible that the current value of #getCurrentItems.subject# does not have any children; that is, it's not the conceptual parent of any other subject term in the table. But it's also possible that it has conceptual children, in which case we need to traverse down the tree, finding and outputting them all. The "checkForChild" query on lines 22-26 lets us know whether or not the current item has children attached to it. It does this by selecting records whose PARENTIDs match the current #SUBJECTID#.

On line 28 the recordcount for the checkForChild query is compared to 0. If it's greater than 0 we know there must be children. If there are children, we need to loop back through the whole process, finding and outputting each one along the way. This is what the recursive call on lines 29-31 does: it calls the cf_simpleBuildTree tag itself, this time passing a new value for #theID# that is equal to the current value of #getCurrentItems.subjectid#. At this point execution within the tag occurs within a completely new context - the context of the next item down the hierarchy.

Within this context line 14 begins a new unordered list nested within the unordered list a level up the hierarchy. Because HTML deals with nested lists properly, we're presented with the correctly indented outline illustrated in Figure 2.

To back up for a minute to our first iteration through the getCurrentItems recordset, if the checkForChild query is run on the current value and comes up with nothing, nothing else occurs; the code simply outputs the current value of #SUBJECT# as a root entry in the tree and moves on to the next record.

In this manner recursion can be used to process data contained in a tree structure. The important thing to remember here is that (1) a recursive call is being used to create a loop, and (2) there is a base condition that can be tested against to end the loop; in this case the base condition is reached when the checkForChild query returns a recordcount of 0, indicating that traversal down that particular branch has reached an end.

cf_buildTree and cf_reverseTree
cf_simpleBuildTree works great and outputs the data in a nice outline form. But suppose we wanted to additionally output each branch as one long string? Suppose we wanted output to look like:

Arts and Humanities
Arts and Humanities - Art History
Arts and Humanities - Art History - Italian Art

The first thing we'd need to do is put some switches in to let the program know whether we're in "outline" or "string" mode, then pass in an appropriate value indicating which mode we want. So if we just copy cf_simpleBuildTree to a new file, say, cf_buildTree, and make the edits, it can be called by:

<cf_buildTree
mode="outline"
>

The output in this mode is exactly the same as that in Figure 2.

Then it's a matter of editing it and putting in the aforementioned switches. Listing 2 contains the final code for cf_buildTree, with any code referring to outline mode wrapped in the appropriate conditional code.

The major change required to output subject terms in string mode begins on line 36, within the checkForChild.recordcount conditional. Notice that, within string mode, this tag never actually outputs anything. Rather, beginning on line 37, it calls another custom tag, "cf_reverseTree", passing it a value for the #theID# variable.

Here's what's going on: to output the subject terms in a string format such as "Arts and Humanities - Art History - Italian Art," the cf_buildTree tag must somehow keep track of the entire list of these terms as it traverses the tree. But the recursive function it employs really doesn't do that; once it has traversed a branch to its end, it simply backs up one step and processes any other children left in the previous loop. If none are found, it keeps sequentially backing up the hierarchy, processing each branch, until it hits the root. Then it begins processing the next root term and all of its branches. The key thing to note here is that it's not backing all the way to the root each time - just one or two (or three or four...) levels until it finds a child in need of processing. Because this particular tree is an "unbalanced tree," that is, a tree whose respective branches may be of differing lengths, one cannot simply push and pop items onto a stack and then expect that stack to accurately represent a particular branch in string format.

The recursion employed by this tag and the cf_simpleBuildTree tag determines the end nodes or leaves of each tree - it's what's known as a "depth first" search. Once we know this, we must do a reverse lookup of the parents of the leaf all the way back to the root. This is what the cf_reverseTree tag does on lines 37-39. Code for this tag is shown in Listing 3.

First, notice that this tag can be called directly with the following call:

<cf_reverseTree
theID = 9
>

This results in the output shown on Figure 3.

How does cf_reverseTree work? Pretty much the same way that cf_buildTree does, only in reverse order. It takes as an attribute a SUBJECTID and, based on that SUBJECTID, it traverses up the tree to the root. As it does this it prepends the value of the #SUBJECT# variable to a list that is then passed to any other recursive iteration of itself. When the top of the tree is reached, it outputs the contents of the list. This output represents the entire branch in string format, from root to leaf.

One last thing to note about this tag is that, on line 25, a <CFEXIT> tag is called. This is done so that, if there is a parent to the current child, the contents of #theList# are not output; it ensures that #theList# is output only once, when the top of the tree is reached.

Returning to cf_buildTree, we see that, on lines 35-45, if checkFor Child.recordcount is not 0, and if the mode of operation is "string" the cf_reverseTree tag is called, which outputs the branch in string mode. However, if there are no children to the current node, cf_reverseTree is likewise called. This occurs on lines 45-51.

Further Modification: cf_selectboxBuildTree and cf_selectboxReverseTree
How might the string mode of this tag be used? One use for it would be to dynamically populate an HTML selectbox.

Listings 4 and 5 illustrate the edited cf_buildTree and cf_reverseTree (saved as cf_selectboxBuildTree and cf_selectboxReverseTree, respectively) needed to do this. Listing 6 illustrates how this new tag is called. Its output is represented in Figure 4.

cf_selectboxBuildTree is roughly the same as cf_buildTree; the main difference is the new attribute passed to the cf_selectboxReverseTree tag on lines 40 and 52. This attribute, named "initialID," passes in the value of the current SUBJECTID and will be used later by the cf_selectboxReverseTree tag to output an HTML <OPTION> tag with the proper SUBJECTID value.

Taking a look at the code for cf_selectboxReverseTree (see Listing 5), we see that the value of #INITIALID# is passed to every recursive iteration of the tag, on line 34, without its value ever being changed. Hence the value of the original SUBJECTID is retained and finally output as the value of the HTML <OPTION> tag on line 43.

In this manner a tree structure can be processed and output in "string" mode, and such string output can be used to dynamically populate an HTML selectbox.

A Note on Performance
It is important to note that recursive functions are extremely resource intensive. This isn't surprising; each time a recursive call is initiated, the tag itself must be reexecuted while simultaneously retaining the state of previous iterations. Further, in the examples offered in this article there is the additional overhead of having the data stored in a backend database. Processing a medium-sized tree structure with a recursive custom tag could result in literally hundreds of hits on the database server, which could be very time-consuming. Every effort should be made to speed up or eliminate these transactions. A significant performance gain can be made, in the cases illustrated above, by simply caching the queries for a brief period - especially the queries in the reverse lookup tags - so they are not duplicated. Then, if a query was previously run from within a recursive iteration, it need not be run again; rather, its results will simply and quickly be read from cache.

Even so, careful attention must be taken when deciding to use a recursive call to process data - and the decision to use a recursive call should be relative to the amount of data and the resources you have available for processing.

Conclusion
Robert Lafore, in his lucid and readable book Data Structures and Algorithms in Java, points out that it's not enough to learn the syntax of a programming language - one must also learn how best to use that language to manipulate data in an efficient manner. And the study of data structures and the algorithms appropriate for processing them is the first step in that direction, a path that results ultimately in superior application design. For someone who wasn't a computer science major in college, that's solid advice.

Acknowledgments
The author wishes to thank his colleagues for their special contributions to his understanding of data structure and algorithms: Ian Goh for pointing the way and Craig Turkington for his insightful comments on this article in draft. Both were computer science majors.

More Stories By Mark Cyzyk

Mark Cyzyk is the Web Architect at Johns Hopkins University in Baltimore,
Maryland.

Comments (0)

Share your thoughts on this story.

Add your comment
You must be signed in to add a comment. Sign-in | Register

In accordance with our Comment Policy, we encourage comments that are on topic, relevant and to-the-point. We will remove comments that include profanity, personal attacks, racial slurs, threats of violence, or other inappropriate material that violates our Terms and Conditions, and will block users who make repeated violations. We ask all readers to expect diversity of opinion and to treat one another with dignity and respect.


IoT & Smart Cities Stories
Chris Matthieu is the President & CEO of Computes, inc. He brings 30 years of experience in development and launches of disruptive technologies to create new market opportunities as well as enhance enterprise product portfolios with emerging technologies. His most recent venture was Octoblu, a cross-protocol Internet of Things (IoT) mesh network platform, acquired by Citrix. Prior to co-founding Octoblu, Chris was founder of Nodester, an open-source Node.JS PaaS which was acquired by AppFog and ...
The Founder of NostaLab and a member of the Google Health Advisory Board, John is a unique combination of strategic thinker, marketer and entrepreneur. His career was built on the "science of advertising" combining strategy, creativity and marketing for industry-leading results. Combined with his ability to communicate complicated scientific concepts in a way that consumers and scientists alike can appreciate, John is a sought-after speaker for conferences on the forefront of healthcare science,...
"The Striim platform is a full end-to-end streaming integration and analytics platform that is middleware that covers a lot of different use cases," explained Steve Wilkes, Founder and CTO at Striim, in this SYS-CON.tv interview at 20th Cloud Expo, held June 6-8, 2017, at the Javits Center in New York City, NY.
The deluge of IoT sensor data collected from connected devices and the powerful AI required to make that data actionable are giving rise to a hybrid ecosystem in which cloud, on-prem and edge processes become interweaved. Attendees will learn how emerging composable infrastructure solutions deliver the adaptive architecture needed to manage this new data reality. Machine learning algorithms can better anticipate data storms and automate resources to support surges, including fully scalable GPU-c...
Predicting the future has never been more challenging - not because of the lack of data but because of the flood of ungoverned and risk laden information. Microsoft states that 2.5 exabytes of data are created every day. Expectations and reliance on data are being pushed to the limits, as demands around hybrid options continue to grow.
Dion Hinchcliffe is an internationally recognized digital expert, bestselling book author, frequent keynote speaker, analyst, futurist, and transformation expert based in Washington, DC. He is currently Chief Strategy Officer at the industry-leading digital strategy and online community solutions firm, 7Summits.
The explosion of new web/cloud/IoT-based applications and the data they generate are transforming our world right before our eyes. In this rush to adopt these new technologies, organizations are often ignoring fundamental questions concerning who owns the data and failing to ask for permission to conduct invasive surveillance of their customers. Organizations that are not transparent about how their systems gather data telemetry without offering shared data ownership risk product rejection, regu...
Bill Schmarzo, author of "Big Data: Understanding How Data Powers Big Business" and "Big Data MBA: Driving Business Strategies with Data Science," is responsible for setting the strategy and defining the Big Data service offerings and capabilities for EMC Global Services Big Data Practice. As the CTO for the Big Data Practice, he is responsible for working with organizations to help them identify where and how to start their big data journeys. He's written several white papers, is an avid blogge...
Machine learning has taken residence at our cities' cores and now we can finally have "smart cities." Cities are a collection of buildings made to provide the structure and safety necessary for people to function, create and survive. Buildings are a pool of ever-changing performance data from large automated systems such as heating and cooling to the people that live and work within them. Through machine learning, buildings can optimize performance, reduce costs, and improve occupant comfort by ...
When talking IoT we often focus on the devices, the sensors, the hardware itself. The new smart appliances, the new smart or self-driving cars (which are amalgamations of many ‘things'). When we are looking at the world of IoT, we should take a step back, look at the big picture. What value are these devices providing. IoT is not about the devices, its about the data consumed and generated. The devices are tools, mechanisms, conduits. This paper discusses the considerations when dealing with the...