Computer Science Fundamentals (CS153 2003S)
[Skip to Body]
Primary:
[Front Door]
[Current]
[Glance]

[EC]
[Honesty]
[Instructions]
[Links]
[Search]
[Syllabus]
Groupings:
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Lab Writeups]
[Outlines]
[Readings]
[Reference]
ECA:
[About]
[Grades]
[Quizzes]
[Submit Work]
[Change Password]
[Reset Password]
Misc:
[Experiments in Java]
[Scheme Reference]
[Scheme Report]
[CS153 2002S (Walker)]
[CS151 2003S (Rebelsky)]
[CS152 2000F (Rebelsky)]
[SamR]
a. Make sure you understand the first reading on recursion and the second reading on recursion.
b. Start DrScheme.
Using recursion over natural numbers, define and test a recursive Scheme
procedure, (poweroftwo power)
that takes a natural
number (an integer greater than or equal to 0)
as its argument and returns the result of raising 2 to the power of
that number. For example,
> (poweroftwo 3) 8 > (poweroftwo 10) 1024 > (poweroftwo 1) 2
It is possible to define this procedure nonrecursively, using Scheme's
primitive expt
procedure, but the point of the exercise is to
use recursion.
You should also avoid using the trick I taught you in a previous class.
Define and test a Scheme procedure, (countdown
val)
, that takes a natural number as argument and returns
a list of all the natural numbers less than or equal to that number, in
descending order:
> (countdown 5) (5 4 3 2 1 0) > (countdown 0) (0)
Define and test a Scheme procedure, (filllist value
count)
, that takes two arguments, the second of which is a
natural number, and returns a list consisting of the specified number of
repetitions of the first argument:
> (filllist 'sample 5) (sample sample sample sample sample) > (filllist (list 'left 'right) 3) ((left right) (left right) (left right)) > (filllist null 1) (()) > (filllist null 2) (() ())
Define and test a recursive Scheme procedure that takes a natural number
as argument and returns a list of all the natural numbers that are
strictly less than the argument, in ascending order. (The traditional
name for this procedure is iota
 another Greek letter.)
For example,
> (iota 3) (0 1 2) > (iota 5) (0 1 2 3 4) > (iota 1) (0)
You may recall the countfrom
procedure from
the reading on recursion
over natural numbers. That procedure is also reproduced
at the end of this lab.
What is the value of the call (countfrom 10 10)
?
a. Write down what you think that it should be.
b. Copy the definition of
countfrom
into DrScheme and use it to find out what the call
actually returns.
Using countfrom
, define and test a Scheme procedure that
takes a natural number as argument and returns a list of all the natural
numbers that are strictly less than the argument, in ascending order.
Note that your procedure must use
countfrom
as a helper.
Here is the definition of a procedure that computes the number of digits in
the decimal representation of number
:
(define numberofdecimaldigits (lambda (number) (if (< number 10) 1 (+ (numberofdecimaldigits (quotient number 10)) 1))))
a. Test this procedure.
The definition of numberofdecimaldigits
uses direct
recursion.
b. Describe the base case of this recursion.
c. Identify and describe the way in which a simpler instance of the problem is created for the recursive call. That is, explain what problem is solved recursively and why you know that that problem is simpler.
d. Explain how the procedure correctly determines that the decimal numeral for the number 2000 contains four digits.
e. What preconditions does numberofdecimaldigits
impose
on its argument?
Rewrite poweroftwo
to permit negative exponents.
countfrom
For those of you unable to find the reading on recursion over
natural numbers and for completeness, here is the countfrom
procedure.
;;; Procedure: ;;; countfrom ;;; Parameters: ;;; lower, a natural number ;;; upper, a natural number ;;; Purpose: ;;; Construct a list of the natural numbers from lower to upper, ;;; inclusive, in ascending order. ;;; Produces: ;;; ls, a list ;;; Preconditions: ;;; lower <= upper ;;; Both lower and upper are numbers, exact, integers, and nonnegative. ;;; Postconditions: ;;; The length of ls is upper  lower + 1. ;;; Every natural number between lower and upper, inclusive, appears ;;; in the list. ;;; Every value in the list with a successor is smaller than its ;;; successor. ;;; For every natural number k less than or equal to the length of ;;; ls, the element in position k of ls is lower + k. (define countfrom (lambda (lower upper) (if (= lower upper) (list upper) (cons lower (countfrom (+ lower 1) upper)))))
Tuesday, 12 September 2000 [Samuel A. Rebelsky]
http://www.math.grin.edu/~stone/courses/scheme/spring2000/recursionwithnaturalnumbers.xhtml
Friday, 15 September 2000 [Samuel A. Rebelsky]
Count toquestion.
http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2000F/Labs/recursion2.html
.
Sunday, 18 February 2001 [Samuel A. Rebelsky]
countfrom
.
http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2001S/Labs/recursion2.html
.
Friday, 27 September 2002 [Samuel A. Rebelsky]
http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2002F/Labs/recursion2.html
.
Thursday, 30 January 2003 [Samuel A. Rebelsky]
Friday, 31 January 2003 [Samuel A. Rebelsky]
For those who finish early.
http://www.cs.grinnell.edu/~rebelsky/Courses/CS153/2003S/Labs/numericrecursion.html
.
[Skip to Body]
Primary:
[Front Door]
[Current]
[Glance]

[EC]
[Honesty]
[Instructions]
[Links]
[Search]
[Syllabus]
Groupings:
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Lab Writeups]
[Outlines]
[Readings]
[Reference]
ECA:
[About]
[Grades]
[Quizzes]
[Submit Work]
[Change Password]
[Reset Password]
Misc:
[Experiments in Java]
[Scheme Reference]
[Scheme Report]
[CS153 2002S (Walker)]
[CS151 2003S (Rebelsky)]
[CS152 2000F (Rebelsky)]
[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 Tue May 6 09:19:55 2003.
The source to the document was last modified on Fri Jan 31 10:09:34 2003.
This document may be found at http://www.cs.grinnell.edu/~rebelsky/Courses/CS153/2003S/Labs/numericrecursion.html
.
You may wish to validate this document's HTML ; ; Check with Bobby
Samuel A. Rebelsky, rebelsky@grinnell.edu