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) tailrecursive procedures you've already written.
Here's the tailrecursive version of factorial.
;;; Procedure: ;;; factorial ;;; Parameters: ;;; n, a nonnegative 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 tailrecursive 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 tailrecursive longeststringonlist
procedure which,
given a list of strings as a parameter, returns the longest string in
the list.
Note that you can use stringlength
to find the length of
a string.
Define a tailrecursive procedure (index val
lst)
that returns the index of val
in lst. That is, it should return zerobased 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 tailrecursive version of iota
.
Write your own tailrecursive version of reverse
.
Here are two versions of sum
, one tailrecursive 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 sumlreport (lambda (lst) (let kernel ((remaining (cdr lst)) (result (car lst))) (display (list 'sumlkernel remaining result)) (newline) (if (null? remaining) result (kernel (cdr remaining ) (+ result (car remaining)))))))
For example,
> (sumlreport (list 1 2 3 4 5)) (sumlkernel (2 3 4 5) 1) (sumlkernel (3 4 5) 3) (sumlkernel (4 5) 6) (sumlkernel (5) 10) (sumlkernel () 15) 15
Write a variant of sumr
that prints the recursive steps.
For example
> (sumrreport (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 nontailrecursive version of append
.
(define append (lambda (listone listtwo) (if (null? listone) listtwo (cons (car listone) (append (cdr listone) listtwo)))))
a. Write your own tailrecursive version.
b. Determine experimentally which of the three versions (builtin, given above, tailrecursive) is fastest.
Generalize longeststringonlist
to (best
better? lst)
, which, given a binary comparator,
finds the best
value in lst
.
Monday, 30 October 2000 [Samuel A. Rebelsky]
Labs/tailrecursion.html
Sunday, 8 April 2001 [Samuel A. Rebelsky]
addtoend
after adding the answer to the reading.
reverse
and append
.
Labs/tailrecursion.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 addtoall
.
2002F/Labs/tailrecursion.html
.
Sunday, 11 April 2003 [Samuel A. Rebelsky]
2003S/Labs/tailrecursion.html
.
Thursday, 13 November 2003 [Samuel A. Rebelsky]
2003F/Labs/tailrecursion.html
.
Thursday, 19 February 2004 [Samuel A. Rebelsky]
display
.
2004S/Labs/tailrecursion.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/tailrecursion.html
.
; ; Check with Bobby
Samuel A. Rebelsky, rebelsky@grinnell.edu