Fundamentals of CS I (CS151 2002F)
Primary:
[Skip To Body]
[Front Door]
[Current]
[Glance]
[Honesty]
[Instructions]
[Links]
[Search]
[Syllabus]
Groupings:
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Outlines]
[Readings]
[Reference]
ECA:
[About]
[Grades]
[Quizzes]
[Submit Work]
[Change Password]
[Reset Password]
Miscellaenous:
[Scheme Reference]
[CS151 2002F Gum]
[CS151 2001S]
[SamR]
[Glimmer Labs]
[schemers.org]
a. Review the reading on tail recursion.
b. Start DrScheme.
Identify three (or more) tail-recursive procedures you've already written.
In DrScheme, you can find out how long it takes to evaluate an
expression by using (time expression)
. The
time
procedure prints out the time it takes to evaluate
and then returns the value computed. If you care only about the
time it takes, you can write
> (define junk (time expression))
That command sets junk
the value of expression
and prints out the time it took to compute as a side-effect.
a. Try the two versions of factorial
on some large numbers.
Does one seem to be faster than the other? You can find the two versions
of factorial in the notes on this problem.
b. Try the three versions of add-to-all
on some lists
of varying sizes (you'll probably need at least a hundred values in
each list, and possibly more) until you can determine a difference
in running times. Note that you should make sure to build the list
before you start timing.
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
(select odd? (list 1 2 3 4 5 6 7)) (select even? (list 1 2 3 4 5 6 7))
to be?
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.
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
.
If you finish early, you may want to consider the following problem.
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.
Here are the two versions of factorial
.
;;; Procedures: ;;; factorial ;;; factorial-tr ;;; Parameters: ;;; n, a non-negative integer ;;; Purpose: ;;; Computes n! = 1*2*3*...*n ;;; Produces: ;;; result, a positive integer ;;; Preconditions: ;;; n is a non-negative integer [unchecked] ;;; Postconditions: ;;; result = 1*2*3*...*n (define factorial (lambda (n) (if (<= n 0) 1 (* n (factorial (- n 1)))))) (define factorial-tr (lambda (n) (letrec ((kernel (lambda (m acc) (if (<= m 0) acc (kernel (- m 1) (* acc m)))))) (kernel n 1))))
Here are the three versions of add-to-all
.
;;; Procedures: ;;; add-to-all-1 ;;; add-to-all-2 ;;; add-to-all-3 ;;; Parameters: ;;; value, a number ;;; values, a list of numbers ;;; Purpose: ;;; Creates a new list by adding value to each member of values. ;;; Produces: ;;; new-values, a list of numbers ;;; Preconditiosn: ;;; value is a number [unchecked] ;;; values is a list of numbers [unchecked] ;;; Postconditions: ;;; (list-ref new-values i) equals (+ value (list-ref values i)) ;;; for all reasonable values of i. (define add-to-all-1 (lambda (value values) (if (null? values) null (cons (+ value (car values)) (add-to-all-1 value (cdr values)))))) (define add-to-all-2 (lambda (value values) (let kernel ((values-remaining values) (values-processed null)) (if (null? values-remaining) values-processed (kernel (cdr values-remaining) (append values-processed (list (+ value (car values-remaining))))))))) (define add-to-all-3 (lambda (value values) (let kernel ((values-remaining values) (values-processed null)) ; If we've run out of values to process, (if (null? values-remaining) (reverse values-processed) (kernel (cdr values-remaining) (cons (+ value (car values-remaining)) values-processed))))))
Monday, 30 October 2000 [Samuel A. Rebelsky]
http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2000F/Labs/tail-recursion.html
Sunday, 8 April 2001 [Samuel A. Rebelsky]
add-to-end
after adding the answer to the reading.
reverse
and append
.
http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2001S/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
.
http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2002F/Labs/tail-recursion.html
.
Primary:
[Skip To Body]
[Front Door]
[Current]
[Glance]
[Honesty]
[Instructions]
[Links]
[Search]
[Syllabus]
Groupings:
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Outlines]
[Readings]
[Reference]
ECA:
[About]
[Grades]
[Quizzes]
[Submit Work]
[Change Password]
[Reset Password]
Miscellaenous:
[Scheme Reference]
[CS151 2002F Gum]
[CS151 2001S]
[SamR]
[Glimmer Labs]
[schemers.org]
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 Mon Dec 2 09:19:30 2002.
The source to the document was last modified on Mon Nov 11 09:44:15 2002.
This document may be found at http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2002F/Labs/tail-recursion.html
.
You may wish to validate this document's HTML ; ; Check with Bobby
Samuel A. Rebelsky, rebelsky@grinnell.edu