Computer Science Fundamentals (CS153 2004S)
[Skip to Body]
Primary:
[Front Door]
[Current]
[Glance]
-
[Honesty]
[Instructions]
[Links]
[Search]
Groupings:
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Outlines]
[Readings]
[Reference]
Misc:
[Experiments in Java]
[Java API]
[Scheme Reference]
[Scheme Report]
[CS153 2003S]
[CS151 2003F]
[CS152 2000F]
[SamR]
Summary: In this laboratory, you will reflect on the appropriate and inappropriate uses of tail recursion.
Contents:
Related Pages:
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 if
.
(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
the list.
Note that you can use string-length
to find the length of
a string.
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
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
.
Write your own tail-recursive version of reverse
.
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
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.
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]
Labs/tail-recursion.html
Sunday, 8 April 2001 [Samuel A. Rebelsky]
add-to-end
after adding the answer to the reading.
reverse
and append
.
Labs/tail-recursion.html
.
Thursday, 7 November 2002 [Samuel A. Rebelsky]
select
.
append
to if you have time.
Monday, 11 November 2002 [Samuel A. Rebelsky]
factorial
and
the three versions of add-to-all
.
2002F/Labs/tail-recursion.html
.
Sunday, 11 April 2003 [Samuel A. Rebelsky]
2003S/Labs/tail-recursion.html
.
Thursday, 13 November 2003 [Samuel A. Rebelsky]
2003F/Labs/tail-recursion.html
.
Thursday, 19 February 2004 [Samuel A. Rebelsky]
display
.
2004S/Labs/tail-recursion.html
.
[Skip to Body]
Primary:
[Front Door]
[Current]
[Glance]
-
[Honesty]
[Instructions]
[Links]
[Search]
Groupings:
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Outlines]
[Readings]
[Reference]
Misc:
[Experiments in Java]
[Java API]
[Scheme Reference]
[Scheme Report]
[CS153 2003S]
[CS151 2003F]
[CS152 2000F]
[SamR]
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
.
;
;
Check with Bobby