Functional Problem Solving (CSC 151 2014F) : Readings
Primary: [Front Door] [Schedule] - [Academic Honesty] [Disabilities] [Email] - [FAQ] [Teaching & Learning] [Grading] [Rubric] - [Calendar]
Current: [Assignment] [EBoard] [Lab] [Outline] [Reading]
Sections: [Assignments] [EBoards] [Examples] [Handouts] [Labs] [Outlines] [Readings]
Reference: [Setup] [VM] [Errors] - [Functions A-Z] [Functions By Topic] - [Racket] [Scheme Report (R5RS)] [R6RS] [TSPL4]
Related Courses: [Davis (2013F)] [Rebelsky (2014S)] [Weinman (2014F)]
Misc: [Submit Questions] - [SamR] [Glimmer Labs] [CS@Grinnell] [Grinnell] - [Issue Tracker (Course)]
Summary: We consider techniques for recursion over natural numbers.
We have written a wide variety of recursive procedures so far.
We have written recursive procedures that return lists (e.g.,
a variety of procedures that select or filter elements from lists),
numbers (e.g., procedures that tally elements in a list, as well as
things like sum
and product
),
and even Boolean values (e.g., the all-___?
and
any-___?
predicates). Yet the procedures have
had one thing in common: All of them took lists as parameters.
While the recursive procedures we've written so far have used lists as the basis of recursion, we can also write recursive procedures with other types as the basis of recursion. All we really need to do recursion are (a) a way to determine if a value is simple enough that we can compute an answer directly and (b) a way to simplify the value.
Natural numbers provide a nice basis of recursion.
Like lists, natural numbers have a recursive structure of which
we can take advantage when we write direct-recursion procedures.
A natural number, n
, is either (a) zero, or
(b) the successor of a smaller natural number, which we can obtain by
subtracting 1 from n
.
Recall that the common format of a recursive procedure is
(define recursive-proc (lambda (val) (if (base-case-test) (base-case val) (combine (partof val) (recursive-proc (simplify val))))))
For lists, the test for a base case was typically “is the list empty”
or “does the list have only one value”, which we would express
as (empty? lst)
and (empty? (cdr lst))
, respectively.
We typically simplify a list by taking the cdr of the lst. Hence, the
simplest form of a recursive procedure for lists is
(define recursive-proc (lambda (lst) (if (null? lst) (base-case) (combine (car lst) (recursive-proc (cdr lst))))))
Clearly, with other data types, we'll have different tests for the base case and different mechanisms for simplifying values.
To write recursive procedures with numeric arguments, we first
need a technique for identifying the base case. With natural
numbers, 0 often provides an appropriate base case. Standard Scheme
provides the predicate zero?
to distinguish
between the base and recursive cases, which permits us to use an
if
-expression to ensure that only the expression
for the appropriate case is evaluated. We can potentially write a
procedure that applies to any natural number if
we know (a) what value it should return when the argument is 0 and (b)
how to convert the value that the procedure would return for the next
smaller natural number into the appropriate return value for a given
non-zero natural number.
Hence, a typical numeric recursive procedure will look something like
(define recursive-proc (lambda (val) (if (zero? val) (base-case) (combine val (recursive-proc (- val 1))))))
In this sample code, we subtract 1 to simplify the number. However, one can also subtract more than 1, or divide the number by 2, or do anything else that gives a result that is closer to zero.
For instance, here is a procedure that, given a natural
number, number
, computes the result of
adding together all of the natural numbers up to and including
number
. This result is traditionally called the
termial of the number.
;;; Procedure: ;;; termial ;;; Parameters: ;;; number, a natural number ;;; Purpose: ;;; Compute the sum of natural numbers not greater than a given ;;; natural number ;;; Produces: ;;; sum, a natural number ;;; Preconditions: ;;; number is a number, exact, an integer, and non-negative. ;;; The sum is not larger than the largest integer the language ;;; permits. ;;; Postconditions: ;;; sum is the sum of natural numbers not greater than number. ;;; That is, sum = 0 + 1 + 2 + ... + number (define termial (lambda (number) (if (zero? number) 0 (+ number (termial (- number 1))))))
Whereas in a list
recursion, we called the cdr
procedure to reduce the length
of the list in making the recursive call, the operation that we apply
in recursion with natural numbers is reducing the number by 1.
termial
in Action
Here's a summary of what
actually happens during the evaluation of a call to the
termial
procedure, say, (termial 5)
:
(termial 5) => (+ 5 (termial 4)) => (+ 5 (+ 4 (termial 3))) => (+ 5 (+ 4 (+ 3 (termial 2)))) => (+ 5 (+ 4 (+ 3 (+ 2 (termial 1))))) => (+ 5 (+ 4 (+ 3 (+ 2 (+ 1 (termial 0)))))) => (+ 5 (+ 4 (+ 3 (+ 2 (+ 1 0))))) => (+ 5 (+ 4 (+ 3 (+ 2 1)))) => (+ 5 (+ 4 (+ 3 3))) => (+ 5 (+ 4 6)) => (+ 5 10) => 15
termial
The restriction that termial
takes only non-negative
integers as arguments is an important one: If we gave it a negative
number or a non-integer, we'd have a runaway recursion. We
cannot get to zero by subtracting 1 repeatedly from a negative number or
from a non-integer, and so the base case would never be reached. For
example,
(termial -5) => (+ -5 (termial -6)) => (+ -5 (+ -6 (termial -7))) => (+ -5 (+ -6 (+ -7 (termial -8)))) => (+ -5 (+ -6 (+ -7 (+ -8 (termial -9))))) => ...
Similarly, if we gave the termial
procedure an approximation
rather than an exact number, we might or might not be able to reach
zero, depending on how accurate the approximation is and how much of
that accuracy is preserved by the subtraction procedure.
(termial 4.1) => (+ 4.1 (termial 3.1)) => (+ 4.1 (+ 3.1 (termial 2.1))) => (+ 4.1 (+ 3.1 (+ 2.1 (termial 1.1)))) => (+ 4.1 (+ 3.1 (+ 2.1 (+ 1.1 (termial 0.1))))) => (+ 4.1 (+ 3.1 (+ 2.1 (+ 1.1 (+ 0.1 (termial -0.9)))))) => (+ 4.1 (+ 3.1 (+ 2.1 (+ 1.1 (+ 0.1 (+ -0.9 (termial -1.9))))))) => ...
Hence, we might use a husk-and-kernel strategy to protect our procedure. If you haven't seen husk-and-kernel, don't worry, we'll get to it soon. The basic idea is that you design code to check that the preconditions are met.
(define termial (lambda (number) (cond [(not (number? number)) (error "termial expects a number, received" number)] [(not (integer? number)) (error "termial expects an integer, received" number)] [(< number 1) (error "termial expects a positive integer, received" number)] [(inexact? number) (error "termial expects an exact integer, received" number)] [else (let kernel ([current number]) (if (zero? current) 0 (+ current (kernel (- current 1)))))])))
termial
Note that our “sum all the values” algorithm is not the only way to compute the termial of a natural number. Many of you may have learned a more efficient (or at least more elegant) algorithm. We'll return to this algorithm later.
The important part of getting recursion to work is making sure that the base case is inevitably reached by performing the simplification operation enough times. For instance, we can use direct recursion on exact positive integers with a base case of 1, rather than 0.
;;; Procedure: ;;; factorial ;;; Parameters: ;;; n, a positive integer ;;; Purpose: ;;; Compute n!, the product of positive integers less than or ;;; equal to a given positive integer. ;;; Produces: ;;; product, an integer ;;; Preconditions: ;;; n is a number, exact, an integer, and positive. ;;; The product is not larger than the largest integer the ;;; language permits. ;;; Postconditions: ;;; product is the product of the positive integers less than or ;;; equal to n. That is, ;;; product = 1 * 2 * ... * n (define factorial (lambda (n) (if (= n 1) 1 (* n (factorial (- n 1))))))
We require the invoker of this factorial
procedure to provide
an exact, strictly positive integer. (Zero won't work in this case,
because we can't reach the base case, 1, by repeated subtractions if we
start from 0.)
But our base case need not be a small number. We can use direct recursion to approach the base case from below by repeated additions of 1, if we know that our starting point is less than or equal to that base case. Here's an example.
;;; Procedure: ;;; count-from ;;; Parameters: ;;; lower, an integer ;;; upper, an integer ;;; Purpose: ;;; Construct a list of the integers from lower to upper, ;;; inclusive, in ascending order. ;;; Produces: ;;; ls, a list ;;; Preconditions: ;;; lower <= upper ;;; Both lower and upper are numbers, exact, and integers. ;;; Postconditions: ;;; The length of ls is 1 + upper - lower. ;;; Every integer between lower and upper, inclusive, appears ;;; in the list. ;;; Every value in the list with a successor is smaller than its ;;; successor. ;;; For every integer 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)))))
Why is this useful? Well, it acts much like a generalized version of
iota
, and we've already seen that
iota
is useful in many different situations.
You may also recall much more manually intensive ways of making such lists in the past, such as listing all the integers between 0 and 16.
The reading shows you how the basic patterns of recursion we have
seen apply to numbers just as well as lists. Identify the standard
pieces of the recursive procedure count-from
by
filling in the blanks below.