1
00:00:06,070 --> 00:00:08,290
This is going to be our most exciting 
week so far. 

2
00:00:08,290 --> 00:00:13,550
The programs that we write, are going to 
do more interesting things, and be more 

3
00:00:13,550 --> 00:00:16,110
interesting to think about than any 
program we've written before. 

4
00:00:17,330 --> 00:00:20,974
The main idea this week is what's called 
Generative Recursion. 

5
00:00:22,300 --> 00:00:25,360
Now, we've been writing recursive 
programs already, so what's the 

6
00:00:25,360 --> 00:00:29,200
difference between those and these? 
Well, the ones we've been writing are 

7
00:00:29,200 --> 00:00:33,290
called Structural Recursion. 
And the way they work is they start with 

8
00:00:33,290 --> 00:00:38,518
a piece of data, and at each recursive 
call, they take some sub-piece of that 

9
00:00:38,518 --> 00:00:41,630
data as the argument for the next 
recursive call. 

10
00:00:41,630 --> 00:00:46,320
So going through a list, you keep taking 
the rest of the list. 

11
00:00:46,320 --> 00:00:49,810
Going through an arbitrary-arity tree, 
you keep taking the first of the 

12
00:00:49,810 --> 00:00:53,390
remaining children. 
Each time you're taking some sub-piece of 

13
00:00:53,390 --> 00:00:57,390
the whole and that defines the structure 
of the recursion. 

14
00:00:57,390 --> 00:01:00,310
In Generative Recursion, a different 
thing happens. 

15
00:01:01,400 --> 00:01:06,770
Which is that at each recursive call, we 
generate entirely new data to operate on 

16
00:01:06,770 --> 00:01:11,670
in the recursive call. 
So what kinds of things are we going to 

17
00:01:11,670 --> 00:01:14,290
do? 
Well, we're going to draw some pretty 

18
00:01:14,290 --> 00:01:18,980
pictures, we're going to look at 
fractals, and we're going to look at 

19
00:01:18,980 --> 00:01:22,390
solving puzzles. 
We'll work through a Sudoku solver. 

20
00:01:24,520 --> 00:01:30,330
The other thing is that with Generative 
Recursion, we've lost the old proof that 

21
00:01:30,330 --> 00:01:34,300
our recursive functions will end up 
stopping, that they'll reach an end. 

22
00:01:34,300 --> 00:01:38,060
So that thing that bothered us for a 
little while a few weeks ago, which was 

23
00:01:38,060 --> 00:01:40,330
why won't this recursive function ever 
end. 

24
00:01:41,420 --> 00:01:43,280
We're going to have to look at that 
question one more time. 

25
00:01:43,280 --> 00:01:43,280
[BLANK_AUDIO]