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.


@ThingsExpo Stories
In his Opening Keynote at 21st Cloud Expo, John Considine, General Manager of IBM Cloud Infrastructure, led attendees through the exciting evolution of the cloud. He looked at this major disruption from the perspective of technology, business models, and what this means for enterprises of all sizes. John Considine is General Manager of Cloud Infrastructure Services at IBM. In that role he is responsible for leading IBM’s public cloud infrastructure including strategy, development, and offering m...
In his session at 21st Cloud Expo, Raju Shreewastava, founder of Big Data Trunk, provided a fun and simple way to introduce Machine Leaning to anyone and everyone. He solved a machine learning problem and demonstrated an easy way to be able to do machine learning without even coding. Raju Shreewastava is the founder of Big Data Trunk (www.BigDataTrunk.com), a Big Data Training and consulting firm with offices in the United States. He previously led the data warehouse/business intelligence and B...
With tough new regulations coming to Europe on data privacy in May 2018, Calligo will explain why in reality the effect is global and transforms how you consider critical data. EU GDPR fundamentally rewrites the rules for cloud, Big Data and IoT. In his session at 21st Cloud Expo, Adam Ryan, Vice President and General Manager EMEA at Calligo, examined the regulations and provided insight on how it affects technology, challenges the established rules and will usher in new levels of diligence arou...
Nordstrom is transforming the way that they do business and the cloud is the key to enabling speed and hyper personalized customer experiences. In his session at 21st Cloud Expo, Ken Schow, VP of Engineering at Nordstrom, discussed some of the key learnings and common pitfalls of large enterprises moving to the cloud. This includes strategies around choosing a cloud provider(s), architecture, and lessons learned. In addition, he covered some of the best practices for structured team migration an...
No hype cycles or predictions of a gazillion things here. IoT is here. You get it. You know your business and have great ideas for a business transformation strategy. What comes next? Time to make it happen. In his session at @ThingsExpo, Jay Mason, an Associate Partner of Analytics, IoT & Cybersecurity at M&S Consulting, presented a step-by-step plan to develop your technology implementation strategy. He also discussed the evaluation of communication standards and IoT messaging protocols, data...
The 22nd International Cloud Expo | 1st DXWorld Expo has announced that its Call for Papers is open. Cloud Expo | DXWorld Expo, to be held June 5-7, 2018, at the Javits Center in New York, NY, brings together Cloud Computing, Digital Transformation, Big Data, Internet of Things, DevOps, Machine Learning and WebRTC to one location. With cloud computing driving a higher percentage of enterprise IT budgets every year, it becomes increasingly important to plant your flag in this fast-expanding busin...
Smart cities have the potential to change our lives at so many levels for citizens: less pollution, reduced parking obstacles, better health, education and more energy savings. Real-time data streaming and the Internet of Things (IoT) possess the power to turn this vision into a reality. However, most organizations today are building their data infrastructure to focus solely on addressing immediate business needs vs. a platform capable of quickly adapting emerging technologies to address future ...
Recently, REAN Cloud built a digital concierge for a North Carolina hospital that had observed that most patient call button questions were repetitive. In addition, the paper-based process used to measure patient health metrics was laborious, not in real-time and sometimes error-prone. In their session at 21st Cloud Expo, Sean Finnerty, Executive Director, Practice Lead, Health Care & Life Science at REAN Cloud, and Dr. S.P.T. Krishnan, Principal Architect at REAN Cloud, discussed how they built...
22nd International Cloud Expo, taking place June 5-7, 2018, at the Javits Center in New York City, NY, and co-located with the 1st DXWorld Expo will feature technical sessions from a rock star conference faculty and the leading industry players in the world. Cloud computing is now being embraced by a majority of enterprises of all sizes. Yesterday's debate about public vs. private has transformed into the reality of hybrid cloud: a recent survey shows that 74% of enterprises have a hybrid cloud ...
22nd International Cloud Expo, taking place June 5-7, 2018, at the Javits Center in New York City, NY, and co-located with the 1st DXWorld Expo will feature technical sessions from a rock star conference faculty and the leading industry players in the world. Cloud computing is now being embraced by a majority of enterprises of all sizes. Yesterday's debate about public vs. private has transformed into the reality of hybrid cloud: a recent survey shows that 74% of enterprises have a hybrid cloud ...
DevOps at Cloud Expo – being held June 5-7, 2018, at the Javits Center in New York, NY – announces that its Call for Papers is open. Born out of proven success in agile development, cloud computing, and process automation, DevOps is a macro trend you cannot afford to miss. From showcase success stories from early adopters and web-scale businesses, DevOps is expanding to organizations of all sizes, including the world's largest enterprises – and delivering real results. Among the proven benefits,...
@DevOpsSummit at Cloud Expo, taking place June 5-7, 2018, at the Javits Center in New York City, NY, is co-located with 22nd Cloud Expo | 1st DXWorld Expo and will feature technical sessions from a rock star conference faculty and the leading industry players in the world. The widespread success of cloud computing is driving the DevOps revolution in enterprise IT. Now as never before, development teams must communicate and collaborate in a dynamic, 24/7/365 environment. There is no time to wait...
Cloud Expo | DXWorld Expo have announced the conference tracks for Cloud Expo 2018. Cloud Expo will be held June 5-7, 2018, at the Javits Center in New York City, and November 6-8, 2018, at the Santa Clara Convention Center, Santa Clara, CA. Digital Transformation (DX) is a major focus with the introduction of DX Expo within the program. Successful transformation requires a laser focus on being data-driven and on using all the tools available that enable transformation if they plan to survive ov...
SYS-CON Events announced today that T-Mobile exhibited at SYS-CON's 20th International Cloud Expo®, which will take place on June 6-8, 2017, at the Javits Center in New York City, NY. As America's Un-carrier, T-Mobile US, Inc., is redefining the way consumers and businesses buy wireless services through leading product and service innovation. The Company's advanced nationwide 4G LTE network delivers outstanding wireless experiences to 67.4 million customers who are unwilling to compromise on qua...
SYS-CON Events announced today that Cedexis will exhibit at SYS-CON's 21st International Cloud Expo®, which will take place on Oct 31 - Nov 2, 2017, at the Santa Clara Convention Center in Santa Clara, CA. Cedexis is the leader in data-driven enterprise global traffic management. Whether optimizing traffic through datacenters, clouds, CDNs, or any combination, Cedexis solutions drive quality and cost-effectiveness. For more information, please visit https://www.cedexis.com.
SYS-CON Events announced today that Google Cloud has been named “Keynote Sponsor” of SYS-CON's 21st International Cloud Expo®, which will take place on Oct 31 – Nov 2, 2017, at the Santa Clara Convention Center in Santa Clara, CA. Companies come to Google Cloud to transform their businesses. Google Cloud’s comprehensive portfolio – from infrastructure to apps to devices – helps enterprises innovate faster, scale smarter, stay secure, and do more with data than ever before.
SYS-CON Events announced today that Vivint to exhibit at SYS-CON's 21st Cloud Expo, which will take place on October 31 through November 2nd 2017 at the Santa Clara Convention Center in Santa Clara, California. As a leading smart home technology provider, Vivint offers home security, energy management, home automation, local cloud storage, and high-speed Internet solutions to more than one million customers throughout the United States and Canada. The end result is a smart home solution that sav...
SYS-CON Events announced today that Opsani will exhibit at SYS-CON's 21st International Cloud Expo®, which will take place on Oct 31 – Nov 2, 2017, at the Santa Clara Convention Center in Santa Clara, CA. Opsani is the leading provider of deployment automation systems for running and scaling traditional enterprise applications on container infrastructure.
SYS-CON Events announced today that Nirmata will exhibit at SYS-CON's 21st International Cloud Expo®, which will take place on Oct 31 – Nov 2, 2017, at the Santa Clara Convention Center in Santa Clara, CA. Nirmata provides a comprehensive platform, for deploying, operating, and optimizing containerized applications across clouds, powered by Kubernetes. Nirmata empowers enterprise DevOps teams by fully automating the complex operations and management of application containers and its underlying ...
SYS-CON Events announced today that Opsani to exhibit at SYS-CON's 21st Cloud Expo, which will take place on October 31 through November 2nd 2017 at the Santa Clara Convention Center in Santa Clara, California. Opsani is creating the next generation of automated continuous deployment tools designed specifically for containers. How is continuous deployment different from continuous integration and continuous delivery? CI/CD tools provide build and test. Continuous Deployment is the means by which...