Functions For Loops

Pattern: Functions for Loops

...If the loop you need is not among those defined by the language, you need a way to define a loop so it can be understood at a glance. This pattern can help achieve the pattern MakeLoopsApparent, SimplyUnderstoodCode, AssignVariablesOnce,and LocalVariablesDefinedAndUsedOnOnePage.


A complicated loop which cannot be expressed with built-in loop constructs can lead to disorientation and confusion.

Suppose you need to write a complicated loop and the built-in loop constructs in the language you're using do not help you. You have a number of local variables which express the state being carried forward through the loop. One tendency you might have is to express the loop using lower level constructs like goto's.

This can lead to disorientation and confusion by code readers because you will most likely have local variables whose assignments are below their references or there might be enough local variables that the loop does not fit on one page or screen.

There are several choices you have at this point. One is to use the low-level construct and perhaps hide its use within a macro. This is dangerous because it is hard to write macros that work reliably especially if they are creating new local variables.

Another choice is to use the low-level construct and document carefully what the loop is doing. This is not, then, a simply understood chunk of code.

The last choice is to use a higher level mechanism.

Therefore, Consider using the programming language construct for functions or procedures to define a recursive function that defines the loop. Its parameters will be the local variables representing state, and the tail recursive call is the iteration step.


This works well if the execution engine for the language can execute a tail recursive call without running out of resources or if the maximum number of iterations is small. Perhaps you also need to worry whether the execution engine can execute function calls fast enough for the loop you are writing.

But don't forget the context. You are trying to write SimplyUnderstoodCode rather than, perhaps, the fastest possible code.


It's interesting to note that, for textbook examples such as gcd or binary search, I have not been able to find a CeeCeePlusPlus compiler that produces worse code for the recursive version (unless you turn off the optimisation). For example, see BinarySearchCodeOnly. A recursive definition of gcd tends to lead to better code than the Iterative (EuclidOfAlexandria's) algorithm. -- DaveWhipp
See also: WhileNotDoneLoop
CategoryLoops

EditText of this page (last edited November 3, 2014) or FindPage with title or text search