Last week, I showed two different functions to reverse an immutable list. More accurately, each of these functions returns a new immutable list that contains the elements of a given immutable list in reverse order. The first of these functions was iterative, and violated the assumption that all data structures would be immutable. The second was recursive, and was essentially a rewrite of the first.

Both of these functions require a leap of insight that is difficult to explain to novices: Each of them creates a value out of nothing, and then manipulates that value in various ways. What is hard to explain is

• How many values do we need to create and manipulate?
• How do we know what those values should be?
• What do we need to do with those values?

Answering questions such as these is a fundamental part of teaching people to program.

To simplify the discussion, let's consider a function that takes a list, assumes that its elements are numbers, and computes their sum. If we were allowed to change the value of a variable, we would be inclined to solve this problem along the following lines:

 
     sum(x) {
           result = 0;
           while (x != nil) {
                result = result + first(x);
                x = second(x);
           }
           return result;
     }
 

This function wastes an addition whenever the list is not empty, because it starts result out at nil and then adds each of the list elements to it in turn. Accordingly, some programmers might be inclined to write the function this way:

               sum(x) {
                              if (x == nil)
                                             return 0;
                              result = first(x);
                              while ((x = second(x)) != nil) {
                                             result += first(x);
                              }
                              return result;
               }

The philosophical difference between these two versions is that the first one assumes that a "zero" value exists—that is, that there exists a value that when added to first(x) yields first(x). This assumption is obviously true in the case of computations on numbers, but if we were to generalize our sum function to other kinds of values, the assumption might not hold.

What both of these versions have in common is that they use a variable to hold an intermediate state. They use the variable to record the information that is associated with a partly completed computation. Each step in the computation updates that intermediate state to account for the additional element that that step processes.

We decide on what that intermediate state should be by imagining that the computation is partly complete, and asking what information we need to store in order to capture the results of that partial computation. In case of computing the sum of a list's elements, it seems reasonable to assume that we look at the elements in a given order, which means that at any point in the computation, there are some elements at which we have looked and others at which we haven't. Having divided the elements in this way, we have little difficulty realizing that the state should be the sum of the elements at which we have already looked.

Therefore, when we set out to write code to solve this particular problem, we figure that we have looked at some of the elements, that we have a variable that holds the sum of those elements, and that each step of the computation involves

• Examining an element for the first time
• Updating our sum to include that element

Of course, the iterative version of our function does exactly that: first(x) is an element of x that we have not yet seen, so the two statements in our loop add that element to result and (effectively) remove it from x.

To use this analysis to solve the problem recursively, we can usually use one simple technique:

Write a function that includes the intermediate state among its parameters..

For this particular problem, the function might have x and result as its parameters. We might think of this function as follows:

• We have partially computed the sum of the elements of (the original value of) x.
• The result of this partial computation is in the parameter sum.
• Our parameter x represents the elements of the original x that we have not yet seen.

When we think about the computation this way, the function is easy to write:

 
     sum_aux(x, result) {
           
           if (x == nil)
                return result;
           return sum_aux(second(x), result + first(x));
     }
 

We can describe this function by observing that if x is nil, then the function's result is result (i.e., the final state is the intermediate state). Otherwise, we call sum_aux recursively after removing the first element from x and adding that element to the intermediate state.

We conclude by writing the sum function itself. We can do so in two different ways, each of which is related to one of the iterative versions that we saw earlier:

 
               sum(x) { return sum_aux(x, 0); }
 

works the same way as the first of the iterative versions, and

 
               sum(x) {
                              if (x == nil)
                                             return 0;
                              return sum_aux(second(x), first(x));
               }
 

works the same way as the second iterative version.

We have seen that for both iterative and recursive functions, a key programming strategy is to ask a single question: What information do we need to store while a computation is in progress? Once we have answered this question, the actual coding job is relatively simple, and proceeds along similar lines both for recursive and iterative functions. The main difference is that for the recursive version, that intermediate state is explicit, in the sense that it is the parameter of a function. This explicitness has profound effects on how we design software systems.

Before looking at such design issues, we will take a look next week at how to sort immutable lists.