[Current] [News] [Glance] [Discussions] [Instructions] [Search] [Links] [Handouts] [Outlines] [Readings] [Labs] [Homeworks] [Quizzes] [Exams] [Examples] [Fall2000.01] [Spring2000]
You may wish to scan through the reading on recrusion and the second reading on recursion.
Using natural-number recursion, define and test a recursive Scheme
procedure named power-of-two
that takes a natural number
as its argument and returns the result of raising 2 to the power of
that number. (For instance, the value of (power-of-two 3)
should be 23, or 8.)
It's possible to define this procedure non-recursively, using Scheme's
primitive expt
procedure, but the point of the exercise is to
use recursion.
Define and test a Scheme procedure named count-down
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:
> (count-down 5) (5 4 3 2 1 0) > (count-down 0) (0)
Define and test a Scheme procedure named fill-list
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:
> (fill-list 'sample 5) (sample sample sample sample sample) > (fill-list (list 'left 'right) 3) ((left right) (left right) (left right)) > (fill-list null 1) (())
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.)
What is the value of the call (count-from -10 10)
?
a. Write down what you think that it should be.
b. Copy the definition of
count-from
into DrScheme and use it to find out what the call
actually returns.
Using count-from
, 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 should use count-from
as a helper.
Here is the definition of a procedure that computes the number of digits in
the decimal representation of number
:
(define number-of-decimal-digits (lambda (number) (if (< number 10) 1 (+ (number-of-decimal-digits (quotient number 10)) 1))))
a. Test this procedure.
The definition of number-of-decimal-digits
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.
d. Explain how the procedure correctly determines that the decimal numeral for the number 2000 contains four digits.
e. What preconditions does number-of-decimal-digits
impose on its
argument?
Tuesday, 12 September 2000
http://www.math.grin.edu/~stone/courses/scheme/recursion-with-natural-numbers.xhtml
Friday, 15 September 2000
[Current] [News] [Glance] [Discussions] [Instructions] [Search] [Links] [Handouts] [Outlines] [Readings] [Labs] [Homeworks] [Quizzes] [Exams] [Examples] [Fall2000.01] [Spring2000]
Disclaimer Often, these pages were created "on the fly" with little, if any, proofreading. Any or all of the information on the pages may be incorrect. Please contact me if you notice errors.
This page may be found at http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2000F/Labs/recursion2.html
Source text last modified Fri Sep 15 10:27:03 2000.
This page generated on Fri Sep 15 10:27:21 2000 by Siteweaver. Validate this page's HTML.
Contact our webmaster at rebelsky@grinnell.edu