# M07: Natural Numbers

Hint: If possible, make your browser wide enough to place the slides and commentary side-by-side.

The slides on this page are not accessible (for screen readers, etc). The 1up and 3up slides are better.

## Module Topics

- Review: data definitions and templates
- A Formal Definition of Natural Numbers
- Templates
- Intervals
- Counting up

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.

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:

- What do we produce in the base case?
- In the recursive case, what (if anything) do we do to transform
`n`

? - What is the result of processing
`(f (sub1 n))`

recursively? - 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 `cons`

ing the result of
step 2 (`n`

) onto the result of step 3 (`(countdown (sub1 n))`

).

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:

- What do we produce in the base case?
- In the recursive case, what (if anything) do we do to transform
`n`

? - What is the result of processing
`(f (add1 n))`

recursively? - 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.