M07: Natural Numbers

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.

There are no videos in Module 07.

The data definition tells us how we can build a (listof Int) (or any other type):

• empty is a (listof Int) by definition.
• 29 is an Int and therefore (by the second clause) (cons 29 empty) is a (listof Int).
• 3 is an Int and therefore (by the second clause) (cons 3 (cons 29 empty)) is a (listof Int).
• 5 is an Int and therefore (cons 5 (cons 3 (cons 29 empty))) is a (listof Int).

Given the data definition, we could develop a template.

The reasoning on the previous slide leads us to the listof-X-template.

You may like to read more about the Peano axioms .

When a data definition uses a function f to move away from the base case, we use the inverse function of f to move toward the base case.

The inverse function of add1 is sub1.

(sub1 3) ⇒ 2
(sub1 2) ⇒ 1
(sub1 1) ⇒ 0
(sub1 (add1 42)) ⇒ 42

Just like we built up a list based on the data definition, we can use this data definition to build natural numbers.

• 0 is a natural number by definition (first clause).
• 1 is a Nat because it’s 1 more than 0, which is a Nat (second clause).
• 2 is a Nat because it’s 1 more than 1, which is a Nat (second clause).
• 3 is a Nat because it’s 1 more than 2….
• 4 is a Nat because it’s 1 more than 3….

This logic parallels the logic for the list template. 

Note that for both data definitions we:
* Use a predicate to determine which case of the data definition applies.
* Figure out how to pull the second, self-referential case apart into its pieces.
* Apply the template recursively to the self-referential part of the data definition.

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 four crucial questions to answer:

1. What do we produce in the base case?
2. In the recursive case, what (if anything) do we do to transform n?
3. What is the result of processing (f (sub1 n)) recursively?
4. How do we combine steps 2 and 3 to obtain the result for (f n)?

We should have the answer to question 1 from our examples: (cons 0 empty)

The answer to question 3 should be obvious from our purpose statement: (countdown (sub1 n)) should be the list of natural numbers from n-1 down to 0.

In this case, we do nothing to transform n (question 2).

We combine the result of steps 2 and 3 (question 4) by consing the result of step 2 (n) onto the result of step 3 ((countdown (sub1 n))).

The stepper provides the full trace of (countdown 2). The condensed trace is on the slide.

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 in the recursive application.

Notice that the recursive applications all have two parameters, one for n and one for the base or stopping condition.

This works just fine 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).

To develop the proposed function (call it countup?) we should ask our standard questions:

1. What do we produce in the base case?
2. In the recursive case, what (if anything) do we do to transform n?
3. What is the result of processing (f (add1 n)) recursively?
4. How do we combine steps 2 and 3 to obtain the result for (f n)?

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 n^th 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 16) 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.