Roundabout presents a set of patterns for writing recursive programs. A recursive program is one that:
The practical effect of the second part of this definition is that a recursive program is defined, in part, in terms of itself. In practice, we create a procedure that calls itself from within its body.
Many programmers learned to dislike or fear recursion early in their careers based on factors that were largely extraneous to the technique itself:
These days, nearly all programming languages support recursion, and compilers can optimize recursive code in a way that eliminates most or all of the performance penalty. For example, Bentley (1998) describes several experiments that show how programmer and compiler optimizations can result in recursive code that is as efficient as iteration for many problems. As a general rule, we can follow the advice of Wirth (1976) and rule out recursion as potential solution only in cases where there is an obvious iterative solution. This principle leaves unanswered the question of when and how best to implement a recursive solution.
Recursion is especially useful in contexts involving inductively-defined data structures. Inductive definition is a powerful form of shorthand for defining an infinite set of objects with a finite set of statements. An inductive definition consists of two kinds of statement:
Some sets are most naturally defined inductively, while others can be described with equal ease either inductively or deductively. In either case, inductive definition promotes formal reasoning about the set, including proofs about many characteristics of the set.
By following the data's structure, recursion directly supports inductive reasoning about the program's behavior and correctness. Perhaps more importantly, it often provides the simplest or clearest way to express a computation. Thus, recursion can lead to code that is straightforward to write, modify, and read.
Roundabout helps programmers develop recursive code that follows the structure of the data that it processes. The ideas contained in these patterns apply to the use of recursion in many programming languages and styles. However, I have written them from the perspective of a functional programming style, using the Scheme. This pattern language assumes that the reader is familiar with BNF notation.
Roundabout consists of seven patterns:
Pattern 1 is the entry point to the language. Patterns 2-4 expand on the first and document the primary techniques used to structure recursive programs. Patterns 5-7 describe common ways to improve programs through the judicious use of helper procedures. These patterns apply in contexts more general than recursive programming, but they prove especially useful for improving code generated by the first four patterns in the face of forces such as run-time efficiency or name-space clutter.
Roundabout also refers to a number of patterns documented elsewhere. Thumbnail sketches of these patterns appear in the External Patterns section at the end of the paper.
Finally, the patterns that constitute Roundabout relate in various ways to other techniques and ideas outside the realm of functional programming. The Related Ideas section discusses of some of the more interesting relationships.
You are writing Simply Understood Code(Gabriel).
How do you write a procedure that operates on a data element whose structure is specified inductively?
Sometimes, what seems simplest at first is to write a loop to process the components of the data. Most languages provide loop constructs, and iteration often matches how you have been taught to think about programs. But two problems can arise. First, your language may not support looping, conveniently or at all. Second, formal reasoning about a loop's behavior is often unintuitive. You prefer to reason inductively about inductively-specified data structures, such as a binary tree, and you would like to be able to reason in a similar way about your programs. Furthermore, whenever the structure of the data changes, you would like to be able to quickly map those changes onto the structure of your code.
Therefore, write a recursive procedure. Give the procedure an Intention Revealing Name (Beck). Have one case for each arm of the data specification. Use a Syntax Procedure (5) to access each part of the data. For each inductive case, write an expression that solves each part of the data and assembles an answer from the answers for the parts. Make the procedure a Composed Procedure (Beck) if any of these cases is complex.
For example, suppose that you would like to write a procedure to compute the length of a list of symbols, specified inductively as:
<list-of-symbols> ::= () | (<symbol> . <list-of-symbols>)
You note that empty lists have length 0 and that a non-empty list is one longer than the rest of the list. So you would write:
(define list-length (lambda (list-of-symbols) (if (null? list-of-symbols) 0 ;; base case (+ 1 (list-length (cdr list-of-symbols))) ;; recursive case ) ))
This procedure resembles the counting loop that you would have used in an iterative solution. If your problem is no more complex than this one and your language supports iteration, then you should consider using an iterative solution instead.
If a recursive case requires an extra argument, turn your procedure into an Interface Procedure (2). If one of your cases operates on another inductively-defined data element, you may need to use Mutual Recursion (3). If several procedures collaborate to produce the answer, or if you want to enhance the compiler's ability to optimize your solution, consider using an Accumulator Variable (4).
You are using Structural Recursion (1). Perhaps you are using an Accumulator Variable (4) to collect your answer.
What should you do when a recursive call requires an extra argument?
Sometimes, in order to handle a recursive case, you need to pass an extra argument to the procedure. Consider the procedure annotate, which takes a list of symbols as an argument, for instance,
(a b c)
and returns a list with each symbol annotated with its position in the list:
((a 1) (b 2) (c 3))
Following Structural Recursion (1), your first version of annotate might look something like this:
(define annotate (lambda (list-of-symbols) (if (null? list-of-symbols) '() (cons (list (car list-of-symbols) position) (annotate (cdr list-of-symbols))) ) ))
But where does the position of the next item in the list come from? You could pass the current position down to each recursive call:
(define annotate (lambda (list-of-symbols position) (if (null? list-of-symbols) '() (cons (list (car list-of-symbols) position) (annotate (cdr list-of-symbols) (+ position 1))) ) ))
Our procedure requires this extra argument in order to do its job. However, adding the argument modifies the procedure's interface. If our programming language allows default parameters, we could insulate users of annotate from having to pass an argument for position on the initial call. Two potential difficulties can arise. First, some languages do not support default parameters. Second, the presence of the default parameter in the code may expose an implementation detail that you would prefer to hide.
Therefore, create two procedures. The first serves as the public interface to the computation and require only arguments necessary to "ask the question". It immediately passes these arguments plus any other required arguments to the second, a helper procedure that actually performs the computation. Give the helper an Intention Revealing Name(Beck). I like to append a phrase such as -helper to the public procedure's name.
Using this pattern, annotate becomes:
(define annotate (lambda (list-of-symbols) ;; the second parameter (annotate-helper list-of-symbols 1) ;; gives the current )) ;; position, initially 1 (define annotate-helper (lambda (list-of-symbols position) (if (null? list-of-symbols) '() (cons (list (car list-of-symbols) position) (annotate-helper (cdr list-of-symbols) (+ position 1))) ) ))
These procedures simulate counted loops in iterative solutions, where the current count is available as an explicit value on each pass through the loop. But this pattern works equally well even when the hidden argument is not a count.
If use of the helper procedure creates a potential name clash or adds unnecessary clutter to your set of procedure definitions, try using a Local Procedure (6) to eliminate it.
You are using Structural Recursion (1).
What should you do when the data element that you are processing is defined in terms of another inductively-specified data type?
Consider the s-list data structure, which is a list that can contain both symbols and lists of symbols. We define an s-list defined inductively as:
<s-list> ::= () | (<symbol-expression> . <s-list>)
Symbol expressions are defined as:
<symbol-expression> ::= <symbol> | <s-list>
Suppose that we would like to write a procedure named replace to replace all occurrences of one symbol in an s-list with another symbol. replace takes three arguments: an object symbol, a target symbol, and an s-list. It returns an s-list identical in all respects to the original except that every occurrence of the target symbol has been replaced with the object symbol. For example,
: (replace 'a 'b '((a b) (((b g r) (f r)) c (d e)) b)) ((a a) (((a g r) (f r)) c (d e)) a))
Using Structural Recursion (1), you might produce:
(define replace (lambda (new-symbol old-symbol s-list) (if (null? s-list) '() (if (symbol? (car s-list)) (if (eq? (car s-list) old-symbol) (cons new-symbol (replace new-symbol old-symbol (cdr s-list))) (cons (car s-list) (replace new-symbol old-symbol (cdr s-list)))) (cons (replace new-symbol old-symbol (car s-list)) (replace new-symbol old-symbol (cdr s-list))) )) ))
Your procedure works, but it has two glaring weaknesses. First, you notice that the recursive call (replace new-symbol old-symbol (cdr s-list)) occurs in three different places in the procedure. This repetition results from that fact that all recursive cases must solve the problem for the rest of the s-list, and we have three such cases. Second, the procedure is not true to the structure suggested by the BNF. replace uses the BNF to organize the computation, but the structure of the resulting program doesn't mimic the structure of the BNF. The data definition has two components, one for s-lists and one for symbol expressions. These components are mutually inductive, that is, defined in terms of one another. Should your code have this structure, too?
You would like to make your code as straightforward as possible, with as few side trips as possible. Creating a single procedure to compute the result achieves this goal, since it focuses the reader's attention on a single piece of code. But you also want to be faithful to the structure of your data, since doing so results in simpler pieces of code and makes later changes to data definitions easier to incorporate. Having multiple procedures that interrelate must be handled with care, however, since you want your reader to be comfortable following the computation.
Therefore, use Structural Recursion (1) on both data definitions. Each procedure will invoke the other at the corresponding point in the code. Give the helper procedure a name that indicates the data type on which it operates.
To apply this pattern to replace, write two procedures. The first operates on s-lists and is named replace. To write the arm of replace that handles symbol expressions, assume that the second -- named replace-symbol-expression -- already exists.
(define replace (lambda (new-symbol old-symbol s-list) (if (null? s-list) '() (cons (replace-symbol-expression new-symbol old-symbol (car s-list)) (replace new-symbol old-symbol (cdr s-list))) ) ))
Now, write replace-symbol-expression, using replace in the arm that handles s-lists:
(define replace-symbol-expression (lambda (new-symbol old-symbol symbol-expression) (if (symbol? symbol-expression) (if (eq? symbol-expression old-symbol) new-symbol symbol-expression) (replace new-symbol old-symbol symbol-expression) ) ))
If use of the helper procedure creates a potential name clash or adds unnecessary clutter to your set of procedure definitions, use a Local Procedure (6) to eliminate it. Mutual Recursion can impose a hefty cost in the number of extra procedure calls needed to handle deeply nested lists. You can use Program Derivation (7) to reduce this cost.
You are using Structural Recursion (1). Perhaps you are using Mutual Recursion (3) to deal with mutually-inductive data types.
How do you handle a situation in which collaborating procedures impose unacceptable computational costs?
You want your code's structure to reflect the structure of the data it is processing. But following the data's structure slavishly may cause some undesired effects. Consider the procedure flatten, which takes an s-list as an argument and returns a list of all symbols in the argument, in the order that they occur in the s-list. For example,
: (flatten '((a b) (((b g r) (f r)) c (d e)) b)) (a b b g r f r c d e b)
Using Mutual Recursion (3), you might produce:
(define flatten (lambda (s-list) (if (null? s-list) '() (append (flatten-symbol-expression (car s-list)) (flatten (cdr s-list))) ) )) (define flatten-symbol-expression (lambda (symbol-expression) (if (symbol? symbol-expression) (list symbol-expression) (flatten symbol-expression) ) ))
Since the recursive case in flatten-symbol-expression returns a list of symbols in an s-list, you return a list containing the symbol from the base case. This means that the recursive case in flatten must assemble its answer from two lists and so must use append. Unfortunately, append is an expensive operation. Each call to append requires an O(n) traversal to find the end of the first list, and flatten makes O(n) calls. The result is O(n2) run-time performance for flatten.
Thus, the straightforwardness and readability of your program structure carry a significant performance cost. You would like to preserve the basic structure of the procedure, and yet retain greater control over how the answer is assembled.
Therefore, use an accumulator variable to build your solution. Give this variable a Role Suggesting Temporary Variable Name (Beck). Make it a parameter on every procedure that plays a role in creating the answer. When a procedure is computing its answer, it can "add" to the accumulator variable in some fashion and return the result. Make the top-level procedure an Interface Procedure (2) that calls a helper with the initial value for the accumulator.
To apply this pattern to flatten, start by creating an Interface Procedure (2) that passes an empty accumulator to its helper:
(define flatten (lambda (s-list) (flatten-helper s-list '()) ))
Then define the helper procedure that operates on the s-list and the accumulator:
(define flatten-helper (lambda (s-list symbols-so-far) (if (null? s-list) symbols-so-far (flatten-symbol-expression-helper (car s-list) (flatten-helper (cdr s-list) symbols-so-far)) ) ))
Notice how you use the answer from flatten-helper, which is a list of all the symbols in the cdr of the s-list>: You pass it as the second argument to flatten-symbol-expression-helper, which processes the symbol expression at the front of the s-list. This is where the accumulation takes place. First, flatten-helper solves the problem for the cdr of the s-list. Its answer is passed as the accumulator to flatten-symbol-expression-helper, which then conses symbols from the car into its accumulator. The cons operation is O(1), much more efficient than the append used in your first solution.
The definition of flatten-symbol-expression-helper follows the mutual recursion pattern, with the addition of the accumulator:
(define flatten-symbol-expression-helper (lambda (symbol-expression symbols-so-far) (if (symbol? symbol-expression) (cons symbol-expression symbols-so-far) ;; accumulate! (flatten-helper symbol-expression symbols-so-far) ) ))
If use of the helper procedure creates a potential name clash or adds unnecessary clutter to your set of procedure definitions, use a Local Procedure (6) to eliminate it. Mutual Recursion can impose a hefty cost in the number of extra procedure calls to flatten-symbol-expression-helper needed to handle deeply nested lists. You can use Program Derivation (7) to reduce this cost.
You are using writing code to process a compound data structure, such as an inductively-defined type.
How do you write the code that accesses the components of the data structure?
Consider the procedure path, which operates on binary search trees of the form
<bst> ::= () | (<number> <bst> <bst>)
path takes a target number and a binary search tree as arguments. It returns a list of directions (either left or right) for finding the number in the tree. For example,
: (define my-tree '(14 (7 () (12 () ())) (26 (20 (17 () ()) ()) (31 () ()))) my-tree : (path 17 my-tree) (right left left)
Using Structural Recursion (1), you might produce:
(define path (lambda (n bst) (cond ((null? bst) (error "path: number not found!")) ((< n (car bst)) (cons 'left (path n (car (cdr bst))))) ((> n (car bst)) (cons 'right (path n (car (cdr (cdr bst)))))) (else '()) ;; n is here! ) ))
This procedure requires a number of calls to car and cdr as the tree structure is traversed. These calls obscure the abstract structure of the tree, in which internal nodes consist of a number, a left subtree, and a right subtree.
Access code written directly in the vocabulary of the programming language often makes a procedure hard to read and hides the abstract structure of the data. But using helper procedures to access the structure requires an extra level of procedure calls, resulting in less efficient run-time performance. However, the helper procedures communicate the structure of the data more clearly and isolate details of the structure implementation away from the client code.
Therefore, create one syntax procedure for each component in the structure. Give each an Intention Revealing Name (Beck) to indicate that the procedure retrieves the component from the structure. In Scheme, a common form is Structure->Component. Whenever you need a data component in your code, call the appropriate syntax procedure.
To apply this pattern to path, start by defining several syntax procedures over the binary search tree data type:
(define empty-tree? (define node (lambda (bst) (lambda (bst) (null? bst))) (car bst))) (define left-subtree (define right-subtree (lambda (bst) (lambda (bst) (car (cdr bst)))) (car (cdr (cdr bst)))))
Then write path in terms of the syntax procedures:
(define path (lambda (n bst) (cond ((empty-tree? bst) (error "path: number not found!")) ((< n (node bst)) (cons 'left (path n (left-subtree bst)))) ((> n (node bst)) (cons 'right (path n (right-subtree bst)))) (else '() ) ;; n is here! ) ))
Syntax procedures operate in a broader context than Structural Recursion (1), but they play an important role in the implementation of recursive programs. When a computation is spread across a number of different procedures, as is often the case when following these recursion patterns, the reader can become disoriented rather quickly. Judicious use of syntax procedures to denote the abstract structure of data offers the reader a common focus across cooperating procedures.
If you need to make several calls to the same accessor within a single procedure, use a Caching Temporary Variable (Beck) to hold the result from the first call and then use that variable in place of future calls to the procedure.
If use of syntax procedures creates a potential name clash or adds unnecessary clutter to your set of procedure definitions, use a Local Procedure(6) in place of each global procedure.
Do not use Program Derivation (7) to eliminate syntax procedures, since their sole benefit lies in naming pieces of data structure. If you need to reduce the run-time cost of unnecessary procedure calls, use some other technique. For example, use function in-lining if your compiler supports it.
Your program contains one or more helper procedures. Perhaps you are using an Interface Procedure (2), Mutual Recursion (3), an Accumulator Variable (5), or a Syntax Procedure (5).
How do you eliminate a helper whose only useful purpose is to assist another procedure, yet still benefit from the abstraction that it provides?
Oftentimes, the helper procedures produced by Interface Procedure (2) and Accumulator Variable (4), in particular, are ones that no other piece of code can use. They are specialists created to support the recursive technique being applied. No other procedure is likely to use them in any context. Consider, for example, annotate-helper in Interface Procedure (2) above.
On the one hand, the procedure is necessary in order to realize the abstraction benefits of the recursive technique. You cannot make the code more efficient in terms of procedure calls without eliminating the helper entirely. Plus, since the helper has an Intention Revealing Name (Beck), its presence may help the reader follow your code better. But if the helper is never used by any other it procedure clutters the global name space and adds overhead to system execution.
Therefore, make the procedure local to its client. Remove any of its parameters that are not modified by the procedure on its recursive calls, instead referring directly to the argument passed by the enclosing context.
Applied to annotate, this pattern results in a single procedure:
(define annotate (letrec ((annotate-helper ;; the helper is local (lambda (list-of-symbols position) (if (null? list-of-symbols) '() (cons (list (car list-of-symbols) position) (annotate-helper (cdr list-of-symbols) (+ position 1)))) ))) (lambda (los) (annotate-helper list-of-symbols 1) )))
The main question to ask yourself before applying this pattern is, "Will any other procedure need this helper?" If the answer is no, then using a Local Procedure may improve your code.
Your program contains one or more helper procedures. Perhaps you are using Mutual Recursion (3).
How do you eliminate calls to a helper procedure that was useful in the course of developing the code but which imposes undesirable costs on the solution?
Your replace procedure, produced by Mutual Recursion(3), was easy to create because you followed the structure of the two inductive data definitions directly. It should be easy for readers of your code to understand for the same reason. But that you pay for this straightforwardness and readability at run-time in the form of many extra procedure calls. replace now makes two calls for each list nested inside an s-list, instead of just one.
On the one hand, using two procedures enhances the ease of developing and reading the code. On the other hand, you can make your code more efficient by eliminating unnecessary calls between the two procedures. The increase in performance can be considerable. Eliminating the helper also unclutters the global name space.
Therefore, replace the procedure call with an application of its body to the arguments. Simplify the expression by substituting the arguments for parameters throughout the procedure body.
To apply this pattern to replace, start by substituting an application of replace-symbol-expression's lambda for the procedure call:
(define replace (lambda (new-symbol old-symbol s-list) (if (null? s-list) '() (cons ((lambda (new-symbol old-symbol symbol-expression) (if (symbol? symbol-expression) (if (eq? symbol-expression old-symbol) new-symbol symbol-expression) (replace new-symbol old-symbol symbol-expression))) new-symbol old-symbol (car s-list)) (replace new-symbol old-symbol (cdr s-list))) ) ))
Then replace the application of the lambda with the body of the lambda, substituting new-symbol for new-symbol, old-symbol for old-symbol, and (car s-list) for symbol-expression:
(define replace (lambda (new-symbol old-symbol s-list) (if (null? s-list) '() (cons (if (symbol? (car s-list)) (if (eq? (car s-list) old-symbol) new-symbol (car s-list)) (replace new-symbol old-symbol (car s-list))) (replace new-symbol old-symbol (cdr s-list)))) ))
The result is a single procedure that behaves exactly the same as the original two procedures together. Note that the derived procedure is not the same as your first version of replace, written without the benefit of Mutual Recursion (3). That procedure was hard to read and modify in part because the expression (replace new-symbol old-symbol (cdr s-list)) was repeated three times in the procedure's body. The derived procedure is nearly as readable as the two-procedure version, since you have collected the repeated subterm into a single occurrence. Of course, you cannot apply this pattern quite as easily in a language whose if construct is a statement and not an expression that returns a value.
This pattern can be applied to any program in which the helper procedures' primary benefit comes from following data structure and not from name abstraction. The main question to ask yourself before applying this pattern is, "Does the increased efficiency achieved more than offset the benefits of following the inductive data definition, chiefly, readability and ease of modification?"
The following patterns are not a part of Roundabout but are referred to by one or more of its patterns. Links to on-line versions of the patterns are provided where available.
Similar concepts in other programming styles
Roundabout comprises techniques founds in all styles of programming. The idea of structural recursion itself is universal. Woolf (1998) describes recursion in object-oriented programming, wherein an object computes an answer to a message by delegating the same message to its instance variables and then combining their answers. The Gang-of-Four's Interpreter pattern documents a proven technique for writing object-oriented code that is driven by a language grammar.
An Interface Procedure acts as an adapter between client code and the recursive procedure that solves a problem. An Accumulator Variable acts as a Collecting Parameter (Beck). A Syntax Procedure is an access method or Getting Method (Beck). Using a Local Procedure is like creating a private method in a class or ADT. Finally, Program Derivation is a form of inlining done by the programmer. This technique can also be used by compilers and interpreters to optimize recursive code.
Teaching recursion to undergraduates using Roundabout
Roundabout documents patterns of good recursive programs, the patterns that I would like to see in the programs my students write. I have used Roundabout as a vehicle to teach undergraduate students recursive programming in two different courses, with promising results. In my freshman-level data structures course, I introduce the Structural Recursion, Interface Procedure, and Syntax Procedure patterns. At this level, I do not give them the patterns in this form but rather use the context and forces of the patterns to make the techniques seem more compelling. In my junior-level programming languages course, I use Roundabout in a form nearly identical to this paper as a part of a major unit on functional programming in Scheme. Student assessments of the course indicate that students find this unit to be the most instructive in the course and a major contributor to their greater facility with recursion.
I thank all those who helped me to improve Roundabout at the 1997 Pattern Languages of Programming conference, including shepherd Ian Chai and workshop members Ken Auer, Jim Doble, Neil Harrison, and Stuart Yeates. Stuart also provided valuable feedback in later e-mail correspondence. I thank Phillip J. Windley, of Brigham Young University, whose lecture notes were the source of many of the code examples that I use in Roundabout.