Summary: In this laboratory, you will reflect on the appropriate and inappropriate uses of tail recursion.
a. Review the reading on tail recursion.
b. Start DrScheme.
Identify three (or more) tail-recursive procedures you've already written.
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
(display (list 'factorial m acc)) (newline)
Examine the effects of inserting these lines by computing the factorial of 10.
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))
b. Verify your answer through experimentation.
c. Correct any errors in
select that you observed in a or b.
Write a tail-recursive
longest-string-on-list procedure which,
given a list of strings as a parameter, returns the longest string in
Note that you can use
string-length to find the length of
Define a tail-recursive procedure
lst) that returns the index of val
in lst. That is, it should return zero-based location of
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
(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
Write your own tail-recursive version of
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
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)))))))
> (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.
> (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
Here's a non-tail-recursive version of
(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.
better? lst), which, given a binary comparator,
best value in
Monday, 30 October 2000 [Samuel A. Rebelsky]
Sunday, 8 April 2001 [Samuel A. Rebelsky]
add-to-endafter adding the answer to the reading.
Thursday, 7 November 2002 [Samuel A. Rebelsky]
if you have time.
Monday, 11 November 2002 [Samuel A. Rebelsky]
factorialand the three versions of
Sunday, 11 April 2003 [Samuel A. Rebelsky]
Thursday, 13 November 2003 [Samuel A. Rebelsky]
Thursday, 19 February 2004 [Samuel A. Rebelsky]
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
; ; Check with BobbySamuel A. Rebelsky, firstname.lastname@example.org