Built with from Grav and Hugo
Recursion is an important tool for working with lists. In this lecture
module we extend our recursive capabilities with a self-referential
data definition for natural numbers, a corresponding template, and
examples of problems that we can now solve.
We’ll start with a quick review of lists because our work with natural
numbers will have many parallels.
The data definition tells us how we can build a (listof Int) (or any other type):
(cons 29 empty)
(cons 3 (cons 29 empty))
(cons 5 (cons 3 (cons 29 empty)))
Alternatively, given (cons 5 (cons 3 (cons 29 empty))) we can use the data definition to
work backwards, proving that it is a (listof Int). In fact, with the built-in
predicate integer? we can write a function that determines whether its argument is
a list of integers:
;; (listof-int? x) produces true if x is (listof Int) and
;; false otherwise.
(check-expect (listof-int? empty) true)
(check-expect (listof-int? (cons 1 (cons 2 empty))) true)
(check-expect (listof-int? (cons "a" empty)) false)
(check-expect (listof-int? "A string") false)
;; listof-int?: Any -> Bool
(define (listof-int? x)
(cond [(empty? x) true]
[(cons? x) (and (integer? (first x))
(listof-int? (rest x)))]
By the way, can you rewrite this function to eliminate the cond? You should.
Note that this doesn’t look quite like the listof-X-template because we
aren not necessarily consuming a list.
Given the data definition on the previous slide, let’s review how we developed the template.
To repeat this reasoning, we’ll need to start with a data definition for
Just like we built up a list based on the data definition, we can use this
data definition to build natural numbers.
This logic parallels the logic for the list template. Note that for both data
NASA would love this function! Launch in T-10, 9, 8, … Liftoff!
Note that (countdown 2) produces 2 cons’d onto the result of (countdown 1)
and that (countdown 1) produces 1 cons’d onto the result of (countdown 0).
countdown, applied to n-1, is the rest of the list.
Just like with the list template, we have some crucial questions to answer:
(f (sub1 n))
We should have the answer to question 1 from our examples. The answer to question 3
should be obvious from our purpose statement.
In this case, we do nothing to transform n (question 2); we just cons it onto
the result of processing (f (sub1 n)) (question 4).
Predict what will happen if countdown consumes a negative value. Then check
How long will this go on? Is
there something you can do to the function to catch
this and stop it?
What values can we generate from this data definition? Well, 7 belongs thanks to
the first clause in the data definition. Because of that, 8 belongs and 9 and
10 and ….
Remember the definition of “simple recursion”? All the arguments in each
recursive application are either unchanged or one step closer to a base case.
“Going along for the ride” is a informal CS135 expression for an argument that
is passed unchanged to the recursive application.
Notice that the recursive applications all have two parameters, one for n
and one for the base or stopping condition.
This work just find if we put in a negative number for the base – so long
as the requires relationship still holds: n>=b.
A simple change in the data definition gives us the non-positive integers.
Carrying that change through to a template and then a function gives us
a way to count up instead of down (sorry, NASA).
Doing a task some number of times is a common thing, both in real life and
in programming. countup-to and countdown-to give us a mechanism to do
that. We happened to use it to build a list, but there’s no reason we couldn’t
substitute other tasks like finding the nth prime number or deploying
n stuffed bears in a game or displaying a list of n friends on Facebook.
Combining the countup template with higher-order functions (Module 14) will
be a powerful and flexible tool in our toolbelt.
This exercise can be done with information you now have, with careful thought.
We’ll be talking about similar problems in the next lecture module, too.