Using Inner Recursion
Unbalanced Trees
One of the more common complex structures found in a variety of applications is that of the unbalanced tree. Because we are MultiValue professionals, we tend to take complexity in stride, but recursion can still be a stumbling point.
An unbalanced tree structure could be used, for example, to represent a bill of materials. The tree would illustrate the relationship between a parent part number and any number of child part numbers, and the relationship between each of those child part numbers and their children, ad infinitum. Such a structure might appear in Figure 1.
In MultiValue, this can be represented very simply by having items in a file, with a multi-valued list of components stored in one of the record attributes in each record. The structure would appear somewhat like Figure 2.
In this file, attribute 20 nominates the components (shown above as Component #1 through Component #3) which are used in the construction or definition of this item. Each of these items would then in turn have components defining the individual subassemblies.
Obviously, by implementing this structure using MultiValue technology, any number of levels can be defined for the structure without going outside the boundary of a single file. As long as a component has components of its own, this structure can implicitly link the records together without indices or a multidimensional inverted list. Each parent keeps track of their children, allowing the whole structure to remain intact. (This, incidentally, applies just as easily to a supermarket as it does programming.)
Storing the structure is only half the battle, however. Eventually someone will want to retrieve the information on a report or inquiry. If the information is stored in a tree structure, we are obligated to follow the tree when printing the report. While this is a reasonable expectation, I'm often amazed at the heinous array of code fragments littering the path to this sort of objective.
Traditional Recursion
Probably the most obvious technique for tree traversal is simple recursion. With this technique, a routine is written for handling a single item. Once the item has been processed, the routine extracts any descendant data and calls itself for each descendant. Such a routine might appear something like Figure 3.
In this example, the ID of the primary inventory record is passed as the parameter. Once that item has been processed, the children are extracted, and each child ID is passed to the PROCESS.ITEM routine. This will cause the entire tree to be traversed, as the routine will repeatedly call itself for all descendant data.
Having said this, and having shown it to be so simple, it should be noted that this particular technique is not generally a good idea for MultiValue systems. Instead of taking the space to fully explain the reasons behind every one of the problems, I'll point out two major ones: (A) Inordinate quantities of memory are required simply to support the recursion, and (B) it's dog slow. Apologies to the dogs.
Inner Recursion
To overcome these problems, a technique called inner recursion can be used. Like traditional recursion, inner recursion is a technique by which a routine calls itself for processing descendant data. Unlike the traditional method, however, this technique does not have hefty resource requirements or speed problems. In fact, this technique uses very little additional memory to support the recursion, and traverses a tree remarkably quickly.
The trick - if I can call it that - is that the routine uses GOSUB to call itself instead of CALL . The astute among us will instantly see that there is a serious problem with this approach: Internal subroutines do not have private variables. In other words, if a subroutine calls itself, the called instance does not have its own copy of the variables, and any variables changed by that instance will remain changed after that instance RETURN s to its caller. Consider the example in Figure 4.
This code fragment will work fine if there's only one level of components. However, if there's an additional level of components - as shown in the subassembly example earlier (Figure 2) - the CHILDREN , CHILDREN.LOOP , and CHILDREN.CNT variables for the first level of components will be changed when the routine calls itself, thus destroying their original contents and causing the end result to be incorrect.
Fortunately, this problem is easily remedied. We simply need to identify those variables whose values are unique to each given instance, and convert them to arrays as in Figure 5.
Note the DIM for the dimensioned arrays at the top of this fragment. If the maximum size of the structure is known, and the structure is not too big, dimensioned arrays are always the best performance option. If the maximum size of the structure is unknown, or the structure could grow to an inordinate size, dynamic arrays could be used instead, though notably with a performance penalty.
For each iteration of the 1000 subroutine, note how the stack pointer, SPTR , is incremented at the top and decremented at the bottom. This is used to maintain autonomy for each instance of the CHILDREN , CHILDREN.CNT and CHILDREN.LOOP variables. The first time through, SPTR is incremented to 1. As 1000 calls itself, SPTR is incremented to 2, 3, etc. As each level is completed, SPTR is decremented to its previous value, so when all is said and done, SPTR is returned to the calling routine with its original value of zero.
Also note that the FOR/NEXT loop from Figure #4 has been replaced by a LOOP/WHILE . While a FOR/NEXT may very well work, thanks to a bad syntax experience on an old ADDS Mentor, I've used LOOP/UNTIL or LOOP/WHILE ever since, and have never encountered any portability issues. And in this age of mergers and acquisitions, one should never discount the value of portability.
My point in writing this is simple: To those who have written heinous code to achieve tree traversal (you know who you are), hopefully this has impressed upon you that there is a different way. To those who need to do this kind of a thing, and just didn't know where to start, perhaps this gives you some food for thought. And to those for whom this is old hat, I just wanted to let y'all know I'm still alive and well.
