If you can't capture the looping structure of an algorithm in control-flow statements, then capture it in a data structure.
Nested for statements occur frequently in C computer programs. Usually they are used to perform a calculation involving several "looping variables," in which the for statements cycle through all possibilities of the variables within a range:
for (i=0; i < n; i++)
for (j=0; j < m; j++)
dowork(i,j);
In most applications, the number of looping variables and corresponding for statements are known and fixed when the application is written. Knowing how many for loops are needed allows straightforward and efficient coding.
Sometimes, though, you can't know everything you'd like to in advance. I encountered this situation while implementing a certain optimization algorithm; the number of looping variables and corresponding nested for statements were indeterminate. Thus, only at run time would I know the nesting depth.
There were a couple of inelegant solutions at hand. I could have coded the largest number of nested for loops likely to be used, testing within the continuation condition whether a for statement should be executed, and then "falling through" to the next loop. But this technique is problematical, since a C for statement is not executed if the continuation condition is not satisfied after initialization. Another alternative would be to allow each such "extra" for statement to be executed one time but then filter out the unwanted looping variables in the body of the innermost for statement where the main calculation work is to be done. Such ad hoc solutions are complex and are very specific to the application at hand.
My solution was to implement the for statement as a recursive function, forfun, so that the degree of nesting may be determined at run time (see Listing 1) . The looping variables are kept in the array r, where the variable r[loop] iterates over integral values from startval[loop] to endval[loop], and where firstloopsub <= loop <= lastloopsub. For illustrative purposes, function work performs all computations done in the innermost for. The continuation condition corresponds to the middle argument of a for statement; and the statement
r[loop]++;
corresponds to the third argument of a for statement. The initialization values of the for statements are given in the array startval.
Listing 2 is a driving program illustrating the use of forfun. The program invokes explicitly nested for statements that correspond to the action of forfun. forfun produces exactly the same sequence of values of r[0], r[1], and r[2] as does the explicit nesting.
You can modify the function forfun to include more general initial and continuation conditions than illustrated in the example by writing explicit coding or by constructing arrays of functions that perform the necessary tasks. The nesting required in the application that lead to forfun was more complex than given here, in that the looping variable space was two-dimensional along with other requirements; however, the essential structure was the same. In a timing test, a program using forfun, with three looping variables of 200 values giving 2003 iterations executed in about twice the time as a program written with the explicitly nested for statements.
Using a recursive function to implement nested for loops allows clean coding of a nested construct when the depth of nesting is known only at run time. For those cases in which the running time penalty is not objectional, forfun should provide a handy item for a programmer's toolbox.
James M. Bell has a Ph.D. in mathematics from Auburn University. He was a member of the mathematics faculty at Furman University for 12 years and for the last 14 years has been a mathematician in the Operations Research Department of Miliken & Company. Part of his job is as system administrator for the department's UNIX network. James may be reached at [email protected].
