Tail recursion and loops

**Spring 1996**

- Tail recursion
- Converting recursive functions to tail-recursive ones
- Invariants
- Turning tail-recursive functions into loops
- if as a function

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

, we call `f`

, and return whatever `g`

did, without modification.
`g`

Consider the following code:

(The definition ofdefinefoo (lambda(x) (if(even? x) (+ 1 (foo (/ x 2))) (bar x)))) (definebar (lambda(y) (* y 3)))

`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

in Donkey, you will see that the
additions of `(foo 8)`

pile up: we keep wanting to evaluate `1`

<something>```
(+ 1
```

,
but first we must evaluate the
<something>. On the other
hand, stepping through `)`

shows that the value of the call to
`(foo 7)`

is just whatever the value of `foo`

is.
`(bar 7)`

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.

Write the function

which is similar to Scheme's built-in
`Even?`

function: given a non-negative integer, `even?`

returns true (`Even?`

) if it is even and false (`#t`

) otherwise.
`#f`

Write`=>`

`(Even? 0)`

`#t`

`=>`

`(Even? 7)`

`#f`

`=>`

`(Even? 22)`

`#t`

`Even?`

using only the following Scheme constructs:

`cond`

`define`

`else`

`Even?`

`#f`

`if`

`lambda`

`sub1`

`#t`

`and variables`

`zero?`

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:

(Another good solution isdefinenumber-function (lambda(x) (if(zero? x) ... ... (Even? ... (sub1 x) ... ) ... ))) (defineEven? (lambda(x) (if(zero? x) #t (not (Even? (sub1 x))))))

(defineEven? (lambda(x) (cond[(zero? x) #t] [(Even? (sub1 x)) #f] [else#t])))

Step through the evaluation of

. (You may want to set
Donkey's Stop-at menu to apply to make this task less
tedious.) Notice that the calls to `(Even? 5)`

keep piling up (in the
first case), or the unfinished
`not`

expressions keep piling up (in the second case). The
recursive call to `cond`

is not tail-recursive.
`Even?`

Change the definition of

to use another function
`Even?`

which is defined in much the same way.
`Odd?`

(defineEven? (lambda(x) (if(zero? x) #t (Odd? (sub1 x))))) (defineOdd? (lambda(x) (if(zero? x) #f (Even? (sub1 x)))))

Notice that the calls to

and `Odd?`

are tail calls:
nothing remains to be done after they are finished.
This is `Even?`

*not* a tail call:

(because after callingdefineEven? (lambda(x) (cond[(zero? x) #t] [(Odd? (sub1 x)) #t] [else#f])))

`Odd?`

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

Now step through evaluation of

again. Notice that the
expressions to be evaluated don't grow: `Even?`

becomes
`(Even? 5)`

, which becomes `(Odd? 4)`

, etc. Nothing remains
to be done to the results of those calls.
`(Even? 3)`

We can also turn

into a tail-recursive function:
`Even?`

(Step throughdefineEven? (lambda(x) (cond[(zero? x) #t] [(zero? (sub1 x)) #f] [else(Even? (sub1 (sub1 x)))])))

`(Even? 5)`

again.

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

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

Here is one solution:

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

Now convert

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

(definesum-of-squares-tail-recursive (local((definesos-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

.
Notice the order in which the additions are done: the original version did
`(list 1 2 3 4)`

while the accumulator-style version did`=>`

`(+ 1 (+ 4 (+ 9 (+ 16 0))))`

`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`=>`

`(+ 1 0)`

`1`

`=>`

`(+ 4 1)`

`5`

`=>`

`(+ 9 5)`

`14`

`=>`

`(+ 16 14)`

`30`

`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:

- Turn the original function into a local helper function.
- Add an accumulator argument to the helper function.
- Change the helper function's recursive call into a tail-recursive call; be sure to update the accumulator appropriately.
- 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

, when it is always added to `sum-of-squares`

), then it is generally possible to make the
function tail-recursive.
```
(* (car
num-list) (car num-list))
```

Consider again the function

:
`sum-of-squares-tail-recursive`

(definesum-of-squares-tail-recursive (local((definesos-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

is called, its first argument
`sos-helper`

is a list which is a suffix of the parameter
`remaining`

of `num-list`

, and that its
second argument `sum-of-squares-tail-recursive`

is the sum of the squares of the
elements a prefix of `sum-so-far`

; and furthermore, the noted suffix
and prefix together make up the entire list.
`num-list`

In order to prove this claim, let us examine each call to

.
First, consider the call in the body of the main function. The first
argument is `sos-helper`

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`

.
`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

and `remaining`

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 `sum-so-far`

; this is
a suffix of `(cdr remaining)`

, and since `remaining`

is itself a
suffix of `remaining`

, then `num-list`

is also a
(shorter) suffix of `(cdr remaining)`

. Now consider the other argument to
`num-list`

: `sos-helper`

.
`(+ (* ... ...) sum-so-far)`

is the sum of the squares of a prefix of
`sum-so-far`

(`num-list`

*i.e.*, all the elements not in

,
and this call to `remaining`

produces the sum of the squares of a longer
prefix: the elements not in `+`

, plus `remaining`

. So the arguments to the recursive call satisfy the property
too.
```
(car
remaining)
```

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

noting the invariant on the use of
the helper function, to aid my understanding the next time I examined the
code.
`sum-of-squares-tail-recursive`

Recall the function

from lecture:
`while-fn`

(The version presented in lecture omitted the two arguments to the recursive call ofdefinewhile-fn (lambda(test-thunk body-thunk) (if(test-thunk) (begin(body-thunk) (while-fn test-thunk body-thunk)))))

`while`

. As a side note, we could write a version in which
the recursive calls have no arguments like so:
(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.definewhile-fn (lambda(test-thunk body-thunk) (local((definewhile-helper (lambda() (if(test-thunk) (begin(body-thunk) (while-helper)))))) (while-helper))))

takes two arguments, each of which is a procedure of no
arguments. (A procedure of no arguments is commonly called a `while-fn`

*thunk*.)
You can think of

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.
`while-fn`

Rewrite

to use `sum-of-squares-tail-recursive`

.
`while-fn`

Here is a solution.

(definesum-of-squares-while-fn (lambda(num-list) (local((defineremaining num-list) (definesum-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.)

- 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.
- 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

, then add a call to`if`

.)`not`

- The body uses

to update the value of each variable; the values are the same as the arguments passed to the tail-recursive call.`set!`

- Return the value of the accumulator; this comes after the while loop.

While looks a little strange, because its arguments are wrapped in

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.
`(`

**lambda** () ...)

Suppose we wanted to define a function

which acts just like
`if-fn`

; for instance,
`if`

and likewise`=>`

`(`

if(< 2 3) 4 5)

`4`

This is not too hard to write:`=>`

`(if-fn (< 2 3) 4 5)`

`4`

(This even seems to work: try it. But there is something deeply wrong with this definition. Try stepping throughdefineif-fn (lambda(test then-exp else-exp) (cond[test then-exp] [elseelse-exp])))

`(fact 4)`

for the following
definition of `fact`

:
(No application ofdefinefact (lambda(x) (if-fn (< x 3) x (* n (fact (- n 1))))))

`fact`

ever halts--the function keeps calling
itself recursively forever.
The problem is that functions (such as

) always evaluate all
their arguments, while special forms (such as `if-fn`

and
`if`

) 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.
`cond`

That is one reason we wrapped up the arguments to

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 `while-fn`

.
`if-fn`