Computer Science Fundamentals (CS153 2004S)

Tail Recursion

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


Related Pages:


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

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))
        ; 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))

b. Verify your answer through experimentation.

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)
          (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))
      (if (null? remaining)
          (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)

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)

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.



Monday, 30 October 2000 [Samuel A. Rebelsky]

Sunday, 8 April 2001 [Samuel A. Rebelsky]

Thursday, 7 November 2002 [Samuel A. Rebelsky]

Monday, 11 November 2002 [Samuel A. Rebelsky]

Sunday, 11 April 2003 [Samuel A. Rebelsky]

Thursday, 13 November 2003 [Samuel A. Rebelsky]

Thursday, 19 February 2004 [Samuel A. Rebelsky]


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

Valid HTML 4.0 ; Valid CSS! ; Check with Bobby

Samuel A. Rebelsky,