CMSC 15100 — Lecture 7

Recursion

It's time for us to revisit an idea that we left hanging at the beginning of the quarter. Recall the following definition.

Let $n$ be a natural number. The factorial $n!$ is defined as follows:

If $n = 0$, then $n! = 1$.
If $n \gt 0$, then $n! = n \times (n-1)!$.

At this point, we have enough experience with Racket to turn this into a function. Let's do it.


(: factorial (-> Integer Integer))
;; Computes the factorial of a given integer n
(define (factorial n)
  (match n
    [0 1]
    [_ (* n (factorial (- n 1)))]))

Notice, as was alluded to earlier, that our program looks almost exactly like our definition. We call such a function a recursive function. Recursion is another idea whose origins is intimately tied to the development of computer science.

As before, we note that there are two pieces to our recursive definition: a base case, which is straightforward, and an inductive case, which is self-referential. Both of these parts are important. While the recursive case is perhaps more interesting, just having a self-referential definition is pointless: it'd just go on forever. We need a basis, or a point where we know we can stop.

Notice that what we've done here essentially allows us to "count". In other words, counting is recursive! We can make use of this in various ways by keeping the basic template.

Consider the following definition.

The Fibonacci words $F_n$ are defined by:

$F_0 = 0$,
$F_1 = 1$,
$F_n = F_{n-1} \cdot F_{n-2}$ for $n \gt 1$.

This differs slightly from our template above, because we have two base cases, but otherwise, the shape of the definition looks almost exactly the same. As with factorial, we see that our function will look pretty close to our definition.


(: fib-word (-> Integer String))
;; Computes the nth Fibonacci word
(define (fib-word n)
  (match n
    [0 "0"]
    [1 "1"]
    [_ (string-append (fib-word (- n 1)) (fib-word (- n 2)))]))

Note that while this is a function about strings, it's really about counting: we want the $n$th term of our sequence and $n$ is a natural number. Again, despite being about strings, the definition of the sequence looks very similar to the definition of the factorial.

We can also do some more exotic things with this. Suppose we wanted to draw a bunch of squares. Before, we would have to arduously write (square len 'solid colour) out a bunch of times. But we can count now! For instance, we can draw an arbitrary number of squares that alternate colours. Notice again that the shape of the function is similar.


(: draw-squares (-> Integer Integer Image-Color Image-Color Image))
;; Draws squares in alternating colours
(define (draw-squares num len col1 col2)
  (match num
    [0 empty-image]
    [_ (beside (square len 'solid col1)
               (draw-squares (sub1 num) len col2 col1))]))

Like before, we can think through what this function is doing. If we know that the function produces a bunch of squares, we can extrapolate that the recursive case places a new square beside the result of the function, a bunch of squares. This sort of extrapolation is the same idea as the principle of mathematical induction, which if you haven't seen already, you will very soon in CS 271.

Of course, this is all well and good, but only being able to count is maybe a bit underwhelming, even if we are now given the ability to repeat things. But we should think about this idea a bit more. Why does recursion give us the ability to count and why do recursive functions on natural numbers have this template?

Recursive Types

Up until now, we've been dealing with data of fixed size, whether it's atomic or compound. This idea of self-reference and recursion is what will allow us to write programs and solve problems on arbitrarily large amounts of data. Of course, there is the question of how to represent such data.

Union types and structure types are basic examples of what we call algebraic data types. These types are composable using basic algebraic operations (sum and product) and are the basis for defining recursive types.

So let's define a recursive type. Ever wonder why recursion is possible to do with natural numbers? Recall that the natural numbers can be defined in the following way:

0 is a natural number (or more formally, a zero element), and
if $n$ is a natural number, then $\operatorname{Succ}(n)$, the successor of $n$, is a natural number.

Let's try to construct our own handcrafted artisinal natural numbers based on this definition.

(define-type Nat (U 'Zero Succ))
(define-struct Succ ([pre : Nat])

What's going on here? We have our bespoke natural number type, Nat which is a union type of two possible types:

'Zero, which is supposedly 0, and
Succ, which is a struct that contains a Nat.

First, notice that the type happens to mirror our definition of the naturals quite naturally (ha ha). But there's something stranger going on: our definition of Nat refers to Succ, but the definition of Succ refers to Nat!

Nat is an example of a recursive type. These are types whose definitions refer to themselves. However, types are not allowed to refer to themselves directly. But they can be mutually recursive, in that type definitions can refer to each other like above.

The nice thing about this definition is it makes very explicit that the natural numbers are a recursive structure and not just a floating goop of nonnegative integers.

What can we do with natural numbers? Well, we can try to add them. To do so we need to somehow define addition recursively, based on our definition of the natural numbers. Let's think this through.

Let's say we want to add two natural numbers $m$ and $n$. We can break this down into two cases.

If $n = 0$, then $m + n = m + 0 = m$.
Otherwise, $n = \operatorname{Succ}(k)$ for some natural number $k$. So \[m + n = m + \operatorname{Succ}(k).\] But this is just $\operatorname{Succ}(m+k)$, which is something we would have to prove if we were in a math class, but since we're not, we'll just leave it to your intuition.

Notice again that this looks very similar to our definition of the natural numbers. This definition then gives us the following function.


(: plus (-> Nat Nat Nat))
;; Computes m + n
(define (plus m n)
  (match n
    ['Zero m]
    [(Succ k) (Succ (plus m k))]))

We can also compare two numbers. Again, while this is intuitive to us at this point in our lives, it takes a bit of work to define formally. Suppose we want to compare two natural numbers $m$ and $n$. As usual, we break this down into two cases.

If $m = 0$ and $n = \operatorname{Succ}(\ell)$, then $m \lt n$.
If $m = \operatorname{Succ}(k)$ and $n = \operatorname{Succ}(\ell)$, then $m \lt n$ if and only if $k \lt \ell$.
Otherwise, $m \not \lt n$.

This is slightly more complicated, but the definition will again helpfully mirror our definition.


(: lt? (-> Nat Nat Boolean))
;; Is m < n?
(define (lt? m n)
  (match* (m n)
    [('Zero (Succ l)) #t]
    [((Succ k) (Succ l)) (lt? k l)]
    [_ _ #f]))

We get a few things out of this. We can continue to define operations on the natural numbers in this way, so we get very robust definitions. These definitions then translate almost perfectly to code. But this also gives us a very nice way to prove that these things actually work. Of course, this is not something you really need to worry about until you take discrete math.

For the computer scientist, the takeaway is that this not only gives us the ability to count, but the ability to construct data of arbitrarily large size. Note how this is enabled by our use of algebraic data types. And once we're able to construct these objects, their construction gives us a standard way to construct functions that process them. This will be important to keep in mind as we delve further into other kinds of recursive data.