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]