# Tail Recursion

Summary: In this laboratory, you will reflect on the appropriate and inappropriate uses of tail recursion.

Contents:

Related Pages:

## Exercises

### Exercise 0: Preparation

a. Review the reading on tail recursion.

b. Start DrScheme.

### Exercise 1: Identifying Tail-Recursive Procedures

Identify three (or more) tail-recursive procedures you've already written.

### Exercise 2: Watching Tail Recursion

Here's the tail-recursive version of factorial.

```;;; Procedure:
;;;   factorial
;;; Parameters:
;;;   n, a non-negative integer [unverified]
;;; Purpose:
;;;   Computes n! = 1*2*3*...*n
;;; Produces:
;;;   result, a positive integer
;;; Preconditions:
;;;   [Standard]
;;; Postconditions:
;;;   result = 1*2*3*...*n
(define factorial
(lambda (n)
(let kernel ((m n)
(acc 1))
(if (<= m 0) acc
(kernel (- m 1) (* acc m))))))
```

You can update `factorial` to show the steps by inserting the following lines before the `if`.

```       (display (list 'factorial m acc))
(newline)
```

Examine the effects of inserting these lines by computing the factorial of 10.

### Exercise 3: Selecting Values

Here's an attempt to write a tail-recursive version of the `select` procedure that selects all the values in a list for which a predicate holds.

```;;; Procedure:
;;;   select
;;; Parameters:
;;;   pred?, a unary predicate
;;;   lst, a list of values
;;; Purpose:
;;;   Selects all values in lst for which pred? holds.
;;; Produces:
;;;   selected, a list
;;; Preconditions:
;;;   pred? can be applied to any element of lst.
;;; Postconditions:
;;;   every value in selected appears in lst.
;;;   (pred? val) holds for every val in selected.
;;;   (pred? val) holds for every val in lst not in selected.
;;;   values in selected appear in the same order in which they appear in lst.
(define select
(lambda (pred? lst)
(let kernel ((lst lst)
(selected null))
(cond
; If nothing's left in the original list, use selected
((null? lst) selected)
; If the predicate holds for the first value in lst,
; select it and continue
((pred? (car lst)) (kernel (cdr lst) (cons (car lst) selected)))
; Otherwise, skip it and continue
(else (kernel (cdr lst) selected))))))
```

a. What do you expect the results of the following two expression to be?

```(select odd? (list 1 2 3 4 5 6 7))
(select even? (list 1 2 3 4 5 6 7))
```

c. Correct any errors in `select` that you observed in a or b.

### Exercise 4: Finding the Longest String on a List

Write a tail-recursive `longest-string-on-list` procedure which, given a list of strings as a parameter, returns the longest string in the list.

Note that you can use `string-length` to find the length of a string.

### Exercise 5: Finding the Index

Define a tail-recursive procedure ```(index val lst)``` that returns the index of val in lst. That is, it should return zero-based location of `val` in `lst`. If the item is not in the list, the procedure should return -1. Test your procedure on:

```(index 3 (list 1 2 3 4 5 6)) => 2
(index 'so (list 'do 're 'mi 'fa 'so 'la 'ti 'do)) => 4
(index "a" (list "b" "c" "d")) => -1
(index 'cat null) => -1
```

### Exercise 6: Iota, Once Again

Recall that `(iota n)` is to be the list of all nonnegative integers less than n in increasing order. Define and test a tail-recursive version of `iota`.

### Exercise 7: Reverse

Write your own tail-recursive version of `reverse`.

## For Those Who Finish Early

### Extra 1: Reporting on Steps

Here are two versions of `sum`, one tail-recursive and one not.

```;;; Procedures:
;;;   sumr
;;;   suml
;;; Parameters
;;;   numbers, a list of numbers of the form (n1 n2 ... nk)
;;; Purpose:
;;;   Sum the values in numbers.
;;; Produces:
;;;   result, a number
;;; Preconditions:
;;;   numbers is nonempty.
;;; Postconditions:
;;;   result = n1 + n2 + ... + nk
;;;   If any of n1 ... nk is inexact, result is inexact.
;;;   If all of n1 ... nk are exact, result is exact.
(define sumr
(lambda (lst)
(if (null? (cdr lst))
(car lst)
(+ (car lst) (sumr (cdr lst))))))

(define suml
(lambda (lst)
(let kernel ((remaining (cdr lst)) (result (car lst)))
(if (null? remaining)
result
(kernel (cdr remaining ) (+ result (car remaining)))))))
```

Those intereseted in observing the steps in `suml` can do so easily by inserting a few extra lines.

```(define suml-report
(lambda (lst)
(let kernel ((remaining (cdr lst)) (result (car lst)))
(display (list 'suml-kernel remaining result))
(newline)
(if (null? remaining)
result
(kernel (cdr remaining ) (+ result (car remaining)))))))
```

For example,

```> (suml-report (list 1 2 3 4 5))
(suml-kernel (2 3 4 5) 1)
(suml-kernel (3 4 5) 3)
(suml-kernel (4 5) 6)
(suml-kernel (5) 10)
(suml-kernel () 15)
15
```

Write a variant of `sumr` that prints the recursive steps. For example

```> (sumr-report (list 1 2 3))
(sumr (1 2 3 4))
(+ 1 (sumr 2 3 4))
(+ 1 (+ 2 (sumr 3 4)))
(+ 1 (+ 2 (+ 3 (sumr 4))))
(+ 1 (+ 2 (+ 3 4)))
(+ 1 (+ 2 7))
(+ 1 9)
10
```

### Extra 2: Appending

Here's a non-tail-recursive version of `append`.

```(define append
(lambda (list-one list-two)
(if (null? list-one) list-two
(cons (car list-one)
(append (cdr list-one) list-two)))))
```

a. Write your own tail-recursive version.

b. Determine experimentally which of the three versions (built-in, given above, tail-recursive) is fastest.

### Extra 3: Finding the Largest

Generalize `longest-string-on-list` to ```(best better? lst)```, which, given a binary comparator, finds the best value in `lst`.

## History

Monday, 30 October 2000 [Samuel A. Rebelsky]

Sunday, 8 April 2001 [Samuel A. Rebelsky]

• Slight updates to code and wording.
• Removed problem that asked for tail-recursive `add-to-end` after adding the answer to the reading.
• Added instructions for determining the running time of an expression in DrScheme.
• Added problems on `reverse` and `append`.
• This version available at `Labs/tail-recursion.html`.

Thursday, 7 November 2002 [Samuel A. Rebelsky]

• Added problem on `select`.
• Moved `append` to if you have time.

Monday, 11 November 2002 [Samuel A. Rebelsky]

• Added the code for the two versions of `factorial` and the three versions of `add-to-all`.
• Changed the suggestion on code for timing.
• This version available at `2002F/Labs/tail-recursion.html`.

Sunday, 11 April 2003 [Samuel A. Rebelsky]

Thursday, 13 November 2003 [Samuel A. Rebelsky]

Thursday, 19 February 2004 [Samuel A. Rebelsky]

• Removed a problem related to timing (and the notes on that problem).
• Added the problem with `display`.
• Added the extra problem of higher-order greatest.
• Added the extra problem of printing the other sum.
• This version available at `2004S/Labs/tail-recursion.html`.

Disclaimer: I usually create these pages on the fly, which means that I rarely proofread them and they may contain bad grammar and incorrect details. It also means that I tend to update them regularly (see the history for more details). Feel free to contact me with any suggestions for changes.

This document was generated by Siteweaver on Fri May 7 09:44:24 2004.
The source to the document was last modified on Thu Feb 19 21:22:02 2004.
This document may be found at `http://www.cs.grinnell.edu/~rebelsky/Courses/CS153/2004S/Labs/tail-recursion.html`.

Samuel A. Rebelsky, rebelsky@grinnell.edu