Lab 9
Tail recursion and loops

Comp 210

Spring 1996

Contents

Tail recursion

Tail recursion is the act of making a tail recursive call. We can understand that term in parts. A call is just application of a function. A recursive call occurs when a function invokes itself. A tail call occurs when a function's result is just the value of another function call. In other words, in order to determine the value of function f, we call g, and return whatever g did, without modification.

Consider the following code: 

(define foo
  (lambda (x)
    (if (even? x)
      (+ 1 (foo (/ x 2)))
      (bar x))))

(define bar
  (lambda (y)
    (* y 3)))
The definition of foo contains a recursive call to foo (it's recursive because foo is the procedure in which the call to foo appears) and a tail call to bar. The call to bar is a tail call because, if the parameter x is even, then the value of the call of foo is just whatever bar returns.

If you step through (foo 8) in Donkey, you will see that the additions of 1 pile up: we keep wanting to evaluate (+ 1 <something>), but first we must evaluate the <something>. On the other hand, stepping through (foo 7) shows that the value of the call to foo is just whatever the value of (bar 7) is.

Why tail calls?

For a non-tail call, Scheme must remember that after the current function application, it is responsible for doing something else (in this case, adding 1 to the result); and there may be many such things to do. For a tail call, Scheme doesn't have to remember anything, because there is nothing more to do: after it is done with the current function call, it is really done.

Non-tail calls force Scheme to remember future actions (that couldn't be performed before), but tail calls don't. Non-tail calls require more space (because there is more to remember), so they are not as efficient as tail calls. Tail calls also permit us to forget the values of function parameters and local variables, because we never do any more work in the calling function, but a non-tail call forces us to remember such values, which might be used when we return to the calling function.

We've noted that tail calls save space, but they also save time (are faster than non-tail calls) for much the same reasons.

More examples

Write the function Even? which is similar to Scheme's built-in even? function: given a non-negative integer, Even? returns true (#t) if it is even and false (#f) otherwise.

(Even? 0) => #t
(Even? 7) => #f
(Even? 22) => #t
Write Even? using only the following Scheme constructs:
cond define else Even? #f if lambda sub1 #t zero? and variables

Hint: write the program schema first. Think about what you know about a number's evenness, if you know whether its predecessor is even.

Here is a solution: 

(define number-function
  (lambda (x)
    (if (zero? x)
        ...
        ... (Even? ... (sub1 x) ... ) ... )))

(define Even?
  (lambda (x)
    (if (zero? x)
        #t
        (not (Even? (sub1 x))))))
Another good solution is 
(define Even?
  (lambda (x)
    (cond [(zero? x) #t]
          [(Even? (sub1 x)) #f]
          [else #t])))

Step through the evaluation of (Even? 5). (You may want to set Donkey's Stop-at menu to apply to make this task less tedious.) Notice that the calls to not keep piling up (in the first case), or the unfinished cond expressions keep piling up (in the second case). The recursive call to Even? is not tail-recursive.

Change the definition of Even? to use another function Odd? which is defined in much the same way. 

(define Even?
  (lambda (x)
    (if (zero? x)
        #t
        (Odd? (sub1 x)))))

(define Odd?
  (lambda (x)
    (if (zero? x)
        #f
        (Even? (sub1 x)))))

Notice that the calls to Odd? and Even? are tail calls: nothing remains to be done after they are finished. This is not a tail call: 

(define Even?
  (lambda (x)
    (cond [(zero? x) #t]
          [(Odd? (sub1 x)) #t]
          [else #f])))
because after calling Odd?, we examine the value and then return something else. But this version contains a tail call: 
(define Even?
  (lambda (x)
    (cond [(zero? x) #t]
          [else (Odd? (sub1 x))])))

Now step through evaluation of Even? again. Notice that the expressions to be evaluated don't grow: (Even? 5) becomes (Odd? 4), which becomes (Even? 3), etc. Nothing remains to be done to the results of those calls.

We can also turn Even? into a tail-recursive function: 

(define Even?
  (lambda (x)
    (cond [(zero? x) #t]
          [(zero? (sub1 x)) #f]
          [else (Even? (sub1 (sub1 x)))])))
Step through (Even? 5) again.

Converting recursive functions to tail-recursive ones

We will now examine how to turn recursive functions into tail-recursive ones in more detail, and will derive a recipe for doing so.

Write a function sum-of-squares which takes a list of numbers as its argument and returns the sum of the squares of the elements of the list.

Here is one solution: 

(define sum-of-squares
  (lambda (num-list)
    (if (null? num-list)
        0
        (+ (* (car num-list) (car num-list))
           (sum-of-squares (cdr num-list))))))

Now convert sum-of-squares to a tail-recursive form using accumulator-style recursion, as shown in class. The result is 

(define sum-of-squares-tail-recursive
  (local ((define sos-helper
            (lambda (remaining sum-so-far)
              (if (null? remaining)
                  0
                  (sos-helper (cdr remaining)
                              (+ (* (car remaining) (car remaining)) sum-so-far))))))
    (lambda (num-list)
      (sos-helper num-list 0))))

Use Donkey to step through the evaluation of both of these functions on (list 1 2 3 4). Notice the order in which the additions are done: the original version did

(+ 1 (+ 4 (+ 9 (+ 16 0)))) => 30
while the accumulator-style version did
(+ 1 0) => 1
(+ 4 1) => 5
(+ 9 5) => 14
(+ 16 14) => 30
The additions were done in the opposite order by the two versions. In the case of addition, that is perfectly harmless, but for operations like cons, you need to be a bit careful to get the resulting list in the right order.

You can automatically convert an ordinary recursive function into a tail-recursive one by following these steps:

  1. Turn the original function into a local helper function.
  2. Add an accumulator argument to the helper function.
  3. Change the helper function's recursive call into a tail-recursive call; be sure to update the accumulator appropriately.
  4. Make the body of the main function just a call to the helper, with appropriate initial values.

Not every recursive function can be turned into a tail-recursive function. In particular, if a function makes a recursive call, but then examines the result and does different things depending on its value, then it may not be possible to make the function tail-recursive. But if we always do the same thing to the recursive call result, no matter what it is (as in sum-of-squares, when it is always added to (* (car num-list) (car num-list))), then it is generally possible to make the function tail-recursive.

Invariants

Consider again the function sum-of-squares-tail-recursive: 

(define sum-of-squares-tail-recursive
  (local ((define sos-helper
            (lambda (remaining sum-so-far)
              (if (null? remaining)
                  0
                  (sos-helper (cdr remaining)
                              (+ (* (car remaining) (car remaining)) sum-so-far))))))
    (lambda (num-list)
      (sos-helper num-list 0))))

I claim that whenever sos-helper is called, its first argument remaining is a list which is a suffix of the parameter num-list of sum-of-squares-tail-recursive, and that its second argument sum-so-far is the sum of the squares of the elements a prefix of num-list; and furthermore, the noted suffix and prefix together make up the entire list.

In order to prove this claim, let us examine each call to sos-helper. First, consider the call in the body of the main function. The first argument is num-list itself; that is a suffix of num-list, albeit an improper one. The second argument is the sum of the squares of a suffix of num-list: the (degenerate) empty suffix. Together this prefix and suffix comprise all of num-list.

Now only the recursive call needs to be considered. Suppose that when we get to the recursive call, the current call satisfies the property, so remaining and sum-so-far account for the two parts of the list. (Induction, which you should have seen in your math classes so far and of which you will see more in Comp 280, permits this assumption.) The first argument for the recursive call is (cdr remaining); this is a suffix of remaining, and since remaining is itself a suffix of num-list, then (cdr remaining) is also a (shorter) suffix of num-list. Now consider the other argument to sos-helper: (+ (* ... ...) sum-so-far). sum-so-far is the sum of the squares of a prefix of num-list (i.e., all the elements not in remaining, and this call to + produces the sum of the squares of a longer prefix: the elements not in remaining, plus (car remaining). So the arguments to the recursive call satisfy the property too.

A property which is true of variables and data at a certain point in your code is often called an invariant. Reasoning about invariants can be invaluable in understanding your programs and proving them correct--either informally, to yourself, or mathematically. In fact, I probably would have inserted a comment in the definition of sum-of-squares-tail-recursive noting the invariant on the use of the helper function, to aid my understanding the next time I examined the code.

Turning tail-recursive functions into loops

Recall the function while-fn from lecture: 

(define while-fn
  (lambda (test-thunk body-thunk)
    (if (test-thunk)
        (begin
          (body-thunk)
          (while-fn test-thunk body-thunk)))))
The version presented in lecture omitted the two arguments to the recursive call of while. As a side note, we could write a version in which the recursive calls have no arguments like so: 
(define while-fn
  (lambda (test-thunk body-thunk)
    (local ((define while-helper
              (lambda ()
                (if (test-thunk)
                    (begin
                      (body-thunk)
                      (while-helper))))))
      (while-helper))))
It is a helpful exercise to understand why this works; if you don't understand, ask a labby or use Donkey to step through its execution.

while-fn takes two arguments, each of which is a procedure of no arguments. (A procedure of no arguments is commonly called a thunk.) You can think of while-fn as evaluating its body over and over. This repetition (looping) doesn't stop until the test is false. In other words, as long as the test evaluates to true, the body is evaluated. So the execution order is test, body, test, body, test, ..., test (until finally test evaluates to false, which is the last evaluation of test, and body is not evaluated again). The value returned by evaluation of the body is always ignored; the body is evaluated only for side effect.

Rewrite sum-of-squares-tail-recursive to use while-fn.

Here is a solution. 

(define sum-of-squares-while-fn
  (lambda (num-list)
    (local ((define remaining num-list)
            (define sum-so-far 0))
      (while-fn
        (lambda ()
          (not (null? remaining)))
        (lambda ()
          (set! sum-so-far (+ (* (car remaining) (car remaining)) sum-so-far))
          (set! remaining (cdr remaining))))
      sum-so-far)))

To transform a tail-recursive function into a while loop, follow the following steps. (There is not an automatic function for converting an arbitrary recursive function into a while loop--you have to convert it into a tail-recursive function first.)

  1. Turn the helper function parameters into local variables; their initial values are the same as the initial values for the call to the helper function from the main function.
  2. The continue test is the same as the test in the helper function, for the direction that causes a tail-recursive call to be made. (If the tail-recursive call appears in the else part of the if, then add a call to not.)
  3. The body uses set! to update the value of each variable; the values are the same as the arguments passed to the tail-recursive call.
  4. Return the value of the accumulator; this comes after the while loop.

if as a function

While looks a little strange, because its arguments are wrapped in (lambda () ...) rather than having the function bodies ``naked''. The reason for this is that we don't want to evaluate the function bodies once and for all time--rather, we want to check the test expression anew each time that the body is evaluated, and we want to run the body multiple times. We can do that via a function call.

Suppose we wanted to define a function if-fn which acts just like if; for instance,

(if (< 2 3) 4 5) => 4
and likewise
(if-fn (< 2 3) 4 5) => 4
This is not too hard to write: 
(define if-fn
  (lambda (test then-exp else-exp)
    (cond [test then-exp]
          [else else-exp])))
This even seems to work: try it. But there is something deeply wrong with this definition. Try stepping through (fact 4) for the following definition of fact: 
(define fact
  (lambda (x)
    (if-fn (< x 3)
           x
           (* n (fact (- n 1))))))
No application of fact ever halts--the function keeps calling itself recursively forever.

The problem is that functions (such as if-fn) always evaluate all their arguments, while special forms (such as if and cond) may only evaluate some of their arguments, leaving others as expressions rather than values. We can't use the ordinary part of Scheme to write new special forms, only new functions.

That is one reason we wrapped up the arguments to while-fn in thunks: so that we didn't evaluate them as soon as while-fn was called. The other reason was so that we could evaluate them repeatedly, which isn't of interest for if-fn.