This is going to be our most exciting week so far.
The programs that we write, are going to do more interesting things, and be more
interesting to think about than any program we've written before.
The main idea this week is what's called Generative Recursion.
Now, we've been writing recursive programs already, so what's the
difference between those and these? Well, the ones we've been writing are
called Structural Recursion. And the way they work is they start with
a piece of data, and at each recursive call, they take some sub-piece of that
data as the argument for the next recursive call.
So going through a list, you keep taking the rest of the list.
Going through an arbitrary-arity tree, you keep taking the first of the
remaining children. Each time you're taking some sub-piece of
the whole and that defines the structure of the recursion.
In Generative Recursion, a different thing happens.
Which is that at each recursive call, we generate entirely new data to operate on
in the recursive call. So what kinds of things are we going to
do? Well, we're going to draw some pretty
pictures, we're going to look at fractals, and we're going to look at
solving puzzles. We'll work through a Sudoku solver.
The other thing is that with Generative Recursion, we've lost the old proof that
our recursive functions will end up stopping, that they'll reach an end.
So that thing that bothered us for a little while a few weeks ago, which was
why won't this recursive function ever end.
We're going to have to look at that question one more time.
[BLANK_AUDIO]