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
"We've been engaging with a lot of customers including Panasonic, we've been involved with Cisco and now we're working with the U.S. government - the Department of Homeland Security," explained Peter Jung, Chief Product Officer at Pulzze Systems, in this SYS-CON.tv interview at @ThingsExpo, held June 6-8, 2017, at the Javits Center in New York City, NY.
"We provide IoT solutions. We provide the most compatible solutions for many applications. Our solutions are industry agnostic and also protocol agnostic," explained Richard Han, Head of Sales and Marketing and Engineering at Systena America, in this SYS-CON.tv interview at @ThingsExpo, held June 6-8, 2017, at the Javits Center in New York City, NY.
SYS-CON Events announced today that Calligo, an innovative cloud service provider offering mid-sized companies the highest levels of data privacy and security, has been named "Bronze 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. Calligo offers unparalleled application performance guarantees, commercial flexibility and a personalised support service from its globally located cloud plat...
Internet of @ThingsExpo, taking place October 31 - November 2, 2017, at the Santa Clara Convention Center in Santa Clara, CA, is co-located with 21st Cloud Expo and will feature technical sessions from a rock star conference faculty and the leading industry players in the world. The Internet of Things (IoT) is the most profound change in personal and enterprise IT since the creation of the Worldwide Web more than 20 years ago. All major researchers estimate there will be tens of billions devic...
"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.
SYS-CON Events announced today that DXWorldExpo has been named “Global 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. Digital Transformation is the key issue driving the global enterprise IT business. Digital Transformation is most prominent among Global 2000 enterprises and government institutions.
SYS-CON Events announced today that Datera, that offers a radically new data management architecture, has been named "Exhibitor" 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. Datera is transforming the traditional datacenter model through modern cloud simplicity. The technology industry is at another major inflection point. The rise of mobile, the Internet of Things, data storage and Big...
"We are focused on SAP running in the clouds, to make this super easy because we believe in the tremendous value of those powerful worlds - SAP and the cloud," explained Frank Stienhans, CTO of Ocean9, Inc., in this SYS-CON.tv interview at 20th Cloud Expo, held June 6-8, 2017, at the Javits Center in New York City, NY.
DX World EXPO, LLC., a Lighthouse Point, Florida-based startup trade show producer and the creator of "DXWorldEXPO® - Digital Transformation Conference & Expo" has announced its executive management team. The team is headed by Levent Selamoglu, who has been named CEO. "Now is the time for a truly global DX event, to bring together the leading minds from the technology world in a conversation about Digital Transformation," he said in making the announcement.
"MobiDev is a Ukraine-based software development company. We do mobile development, and we're specialists in that. But we do full stack software development for entrepreneurs, for emerging companies, and for enterprise ventures," explained Alan Winters, U.S. Head of Business Development at MobiDev, in this SYS-CON.tv interview at 20th Cloud Expo, held June 6-8, 2017, at the Javits Center in New York City, NY.
While the focus and objectives of IoT initiatives are many and diverse, they all share a few common attributes, and one of those is the network. Commonly, that network includes the Internet, over which there isn't any real control for performance and availability. Or is there? The current state of the art for Big Data analytics, as applied to network telemetry, offers new opportunities for improving and assuring operational integrity. In his session at @ThingsExpo, Jim Frey, Vice President of S...
SYS-CON Events announced today that DXWorldExpo has been named “Global 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. Digital Transformation is the key issue driving the global enterprise IT business. Digital Transformation is most prominent among Global 2000 enterprises and government institutions.
In his opening keynote at 20th Cloud Expo, Michael Maximilien, Research Scientist, Architect, and Engineer at IBM, discussed the full potential of the cloud and social data requires artificial intelligence. By mixing Cloud Foundry and the rich set of Watson services, IBM's Bluemix is the best cloud operating system for enterprises today, providing rapid development and deployment of applications that can take advantage of the rich catalog of Watson services to help drive insights from the vast t...
SYS-CON Events announced today that EnterpriseTech has been named “Media 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. EnterpriseTech is a professional resource for news and intelligence covering the migration of high-end technologies into the enterprise and business-IT industry, with a special focus on high-tech solutions in new product development, workload management, increased effic...
SYS-CON Events announced today that Massive Networks, that helps your business operate seamlessly with fast, reliable, and secure internet and network solutions, has been named "Exhibitor" 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. As a premier telecommunications provider, Massive Networks is headquartered out of Louisville, Colorado. With years of experience under their belt, their team of...
SYS-CON Events announced today that Cloud Academy named "Bronze Sponsor" of 21st International Cloud Expo which will take place October 31 - November 2, 2017 at the Santa Clara Convention Center in Santa Clara, CA. Cloud Academy is the industry’s most innovative, vendor-neutral cloud technology training platform. Cloud Academy provides continuous learning solutions for individuals and enterprise teams for Amazon Web Services, Microsoft Azure, Google Cloud Platform, and the most popular cloud com...
SYS-CON Events announced today that Cloudistics, an on-premises cloud computing company, has been named “Bronze 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. Cloudistics delivers a complete public cloud experience with composable on-premises infrastructures to medium and large enterprises. Its software-defined technology natively converges network, storage, compute, virtualization, and ...
SYS-CON Events announced today that CHEETAH Training & Innovation 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. CHEETAH Training & Innovation is a cloud consulting and IT training firm specializing in improving clients cloud strategies and infrastructures for medium to large companies.
SYS-CON Events announced today that Datanami has been named “Media 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. Datanami is a communication channel dedicated to providing insight, analysis and up-to-the-minute information about emerging trends and solutions in Big Data. The publication sheds light on all cutting-edge technologies including networking, storage and applications, and thei...
The current age of digital transformation means that IT organizations must adapt their toolset to cover all digital experiences, beyond just the end users’. Today’s businesses can no longer focus solely on the digital interactions they manage with employees or customers; they must now contend with non-traditional factors. Whether it's the power of brand to make or break a company, the need to monitor across all locations 24/7, or the ability to proactively resolve issues, companies must adapt to...