Fundamentals of CS I (CS151 2001S)

[Current]
[Discussions]
[Glance]
[Honesty]
[Instructions]
[Links]
[News]
[Search]
[Syllabus]
**Primary**

[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Outlines]
[Quizzes]
[Readings]
[Reference]
**Sets**

[Blackboard]
[Scheme Report]
[SamR's Schedule]
[Rebelsky/Fall 2000]
[Walker/Fall2000]
[Stone/Spring2000]
**Links**

a. Make sure you understand the reading on recursion and the second reading on recursion.

b. Start DrScheme

Using recursion over natural numbers, define and test a recursive Scheme
procedure, `(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*)`(power-of-two 3)`

should be 2^{3}, or 8.

It is 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, ```
(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:
*val*)

>(count-down 5)(5 4 3 2 1 0) >(count-down 0)(0)

Define and test a Scheme procedure, `(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:
*value*
*count*)

>(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.)

You may recall the `count-from`

procedure from
the reading on recursion
over natural numbers.

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 **must** 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?

For those of you unable to find the reading on recursion over
natural numbers and for completeness, here is the `count-from`

procedure.

;;; Procedure: ;;; count-from ;;; 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 non-negative. ;;; 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 count-from (lambda (lower upper) (if (= lower upper) (list upper) (cons lower (count-from (+ lower 1) upper)))))

Tuesday, 12 September 2000

- Created.
- Most of the problems were taken from
`http://www.math.grin.edu/~stone/courses/scheme/recursion-with-natural-numbers.xhtml`

Friday, 15 September 2000

- Removed one question (odd-prod, which requires you to write a precondition)
- Added the first "Count to" question.

Sunday, 18 February 2001

- Reformatted slightly.
- Added code for
`count-from`

.

[Current]
[Discussions]
[Glance]
[Honesty]
[Instructions]
[Links]
[News]
[Search]
[Syllabus]
**Primary**

[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Outlines]
[Quizzes]
[Readings]
[Reference]
**Sets**

[Blackboard]
[Scheme Report]
[SamR's Schedule]
[Rebelsky/Fall 2000]
[Walker/Fall2000]
[Stone/Spring2000]
**Links**

**Disclaimer**:
I usually create these pages on the fly. This means that they
are rarely proofread and may contain bad grammar and incorrect details.
It also means that I may update them regularly (see the history for
more details). Feel free to contact me with any suggestions for changes.

This page was generated by Siteweaver on Thu May 3 23:08:00 2001.

This page may be found at `http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2001S/recursion2.html`

.

You may validate
this page's HTML.

The source was last modified Sun Feb 18 21:58:29 2001.