Using Recursive Techniques in Forth

The word RECURSE indicates that the colon definition in which RECURSE occurs is called recursively. The name of the definition is not used as until the definition is completed (i.e. at the terminating semicolon) that name cannot be found in the dictionary.

This allows previously defined words to be redefined, for instance to include extra code for debugging or other development purposes. One example would be to redefine : (the colon compiler), so that words defined with the new version maintain a count of how many times they are executed, for profiling purposes. How this is achieved is beyond the scope of this introduction.

Although recursion is often discouraged as being a computationally inefficient technique, this is not the case in Forth. In a Forth system in which the colon compiler creates native code RECURSE typically compiles to a JSR or its equivalent.

In fact subroutine nesting in general is very efficient in Forth, which allows definitions in Forth to be very short without significant loss of speed. The examples given in this introduction are not atypical.

In modern stack processors, which implement Forth in hardware, JSR is almost invariably a single cycle operation, and RTS can often be performed concurrently with other operations, so effectively takes zero cycles.

Finally we note that the stackflow symbol for RECURSE cannot be specified in the general case, as it has as many inputs and outputs as the word in which it is used, which varies from instance to instance.

I'm Impressed