1
00:00:00,475 --> 00:00:02,160
- [Presenter] The following
content is provided

2
00:00:02,160 --> 00:00:04,419
under a Creative Commons license.

3
00:00:04,419 --> 00:00:06,675
Your support will help MIT OpenCourseWare

4
00:00:06,675 --> 00:00:08,330
continue to offer high quality

5
00:00:08,330 --> 00:00:11,139
educational resources for free.

6
00:00:11,139 --> 00:00:13,748
To make a donation or
view additional materials

7
00:00:13,748 --> 00:00:16,066
from hundreds of MIT courses,

8
00:00:16,066 --> 00:00:19,924
visit MIT opencourseware at ocw.mit.edu.

9
00:00:20,945 --> 00:00:23,518
- So my name is Curran Kelleher,

10
00:00:23,518 --> 00:00:26,243
I'll be lecturing today
about recursion and fractals.

11
00:00:26,243 --> 00:00:29,276
Justin Curry's not here
today so I'm gonna fill in.

12
00:00:30,227 --> 00:00:34,766
So today I'm gonna just do
a bunch of example programs,

13
00:00:34,766 --> 00:00:36,785
computer programs that are recursive.

14
00:00:36,785 --> 00:00:39,008
Some of them don't make
pictures and some of them do,

15
00:00:39,008 --> 00:00:40,373
and when they make
pictures, they're fractals.

16
00:00:40,373 --> 00:00:43,035
Fractals are things that are self-similar

17
00:00:43,035 --> 00:00:46,507
at different scales,
so you can zoom in on.

18
00:00:46,507 --> 00:00:49,946
We're gonna take a break at
four o'clock for 10 minutes.

19
00:00:49,946 --> 00:00:52,301
And then towards the end,
hopefully I'll show you

20
00:00:52,301 --> 00:00:56,158
a bunch of examples of fractals
in place in Bach music.

21
00:00:56,158 --> 00:00:58,702
So first of all,

22
00:00:58,702 --> 00:01:02,326
let's consider a recursive
mathematical function,

23
00:01:04,183 --> 00:01:08,629
a factorial, something
factorial like three factorials,

24
00:01:08,629 --> 00:01:10,991
three times two times one.

25
00:01:10,991 --> 00:01:14,108
And four factorial is four
times three times two times one.

26
00:01:14,108 --> 00:01:15,741
So like...

27
00:01:16,637 --> 00:01:19,339
And this is factorial,
the exclamation point.

28
00:01:24,607 --> 00:01:29,422
So the way this is defined
is actually recursive.

29
00:01:30,659 --> 00:01:34,744
So if you take anything
factorial, say n factorial is

30
00:01:39,125 --> 00:01:41,299
n minus one factorial,

31
00:01:42,577 --> 00:01:47,061
let's say n is four and n
minus one would be three.

32
00:01:47,061 --> 00:01:49,223
So four factorial is...

33
00:01:51,669 --> 00:01:53,367
Wait.

34
00:01:53,367 --> 00:01:55,575
N, yeah, times n.

35
00:01:58,030 --> 00:02:01,042
So it's gonna be, well n
times n minus one factorial.

36
00:02:01,042 --> 00:02:05,224
So four is n times this whole
thing is three factorial.

37
00:02:07,406 --> 00:02:09,724
It's n minus one factorial.

38
00:02:12,632 --> 00:02:15,179
So this is a recursive definition.

39
00:02:15,179 --> 00:02:17,401
And if you look in the handout,

40
00:02:17,401 --> 00:02:20,541
I wrote a little computer program

41
00:02:20,541 --> 00:02:24,389
on page three I think

42
00:02:24,389 --> 00:02:26,131
that does the factorial.

43
00:02:26,131 --> 00:02:28,577
So it goes like this.

44
00:02:40,186 --> 00:02:44,766
So for those of you who don't
know much about programming,

45
00:02:44,766 --> 00:02:46,320
def means define.

46
00:02:46,320 --> 00:02:49,217
So we're defining a
function called factorial.

47
00:02:49,217 --> 00:02:51,231
And it takes as an argument n.

48
00:02:51,231 --> 00:02:53,535
So you can call this
function pass it a number.

49
00:02:53,535 --> 00:02:56,341
And inside the function,
it's referred to as n.

50
00:02:56,341 --> 00:03:00,403
So this factorial function
says if n is greater than one,

51
00:03:05,275 --> 00:03:09,251
return n times factorial of n minus one.

52
00:03:19,850 --> 00:03:22,397
Else return one.

53
00:03:29,981 --> 00:03:33,217
So what makes this function recursive

54
00:03:33,217 --> 00:03:34,938
is the fact that it calls itself.

55
00:03:34,938 --> 00:03:39,005
Factorial is defined as n times
factorial of something else.

56
00:03:40,840 --> 00:03:44,619
So a recursive function is a
function that calls itself.

57
00:03:46,654 --> 00:03:48,064
So maybe an example.

58
00:03:48,064 --> 00:03:50,433
So if n is five say,

59
00:03:52,338 --> 00:03:56,767
the way we call this is
we say factorial of five.

60
00:04:02,029 --> 00:04:05,022
So when we say this,

61
00:04:05,022 --> 00:04:07,735
it calls this function

62
00:04:07,735 --> 00:04:10,424
and gives n the number five.

63
00:04:10,424 --> 00:04:13,214
So what's it's gonna do
is n is gonna be five.

64
00:04:13,214 --> 00:04:16,565
So n is greater than
one so we return n times

65
00:04:16,565 --> 00:04:19,075
factorial of n minus one.

66
00:04:19,075 --> 00:04:23,341
So say we're doing this
algorithm, five is n.

67
00:04:23,341 --> 00:04:27,295
So we're gonna return five
times factorial of n minus one.

68
00:04:27,295 --> 00:04:31,448
So we call factorial with the value four,

69
00:04:31,448 --> 00:04:34,108
and that's also greater than one

70
00:04:34,108 --> 00:04:37,400
so we return four times
factorial of three.

71
00:04:38,281 --> 00:04:41,898
So five times four

72
00:04:41,898 --> 00:04:44,100
times factorial three.

73
00:04:44,100 --> 00:04:46,203
So we loop,

74
00:04:46,203 --> 00:04:49,264
we call itself a bunch of times until

75
00:04:49,264 --> 00:04:51,568
we get down to one.

76
00:04:57,936 --> 00:04:59,933
So that's what actually ends up happening.

77
00:04:59,933 --> 00:05:01,495
This is recursion.

78
00:05:01,495 --> 00:05:04,101
So another simple example,
which is sort of like

79
00:05:04,101 --> 00:05:08,451
the factorial is the Fibonacci numbers.

80
00:05:08,451 --> 00:05:10,141
Fibonacci sequence.

81
00:05:18,971 --> 00:05:21,352
So the Fibonacci numbers

82
00:05:23,662 --> 00:05:25,589
goes one, one

83
00:05:25,589 --> 00:05:28,340
and then the next one you
add the first two together.

84
00:05:28,340 --> 00:05:30,498
So it goes one, one, two.

85
00:05:30,498 --> 00:05:34,448
One plus two is three,
two plus three is five

86
00:05:37,268 --> 00:05:39,877
and so on, eight, blah, blah, blah.

87
00:05:39,877 --> 00:05:42,126
These are the Fibonacci numbers.

88
00:05:42,126 --> 00:05:44,674
So this is a recursive definition.

89
00:05:44,674 --> 00:05:47,444
Let's say this is...

90
00:05:54,368 --> 00:05:57,608
This is like the number of the element,

91
00:05:57,608 --> 00:06:01,042
like they're just numbers,
indices if you will.

92
00:06:01,042 --> 00:06:04,756
So Fibonacci of two is Fibonacci of zero

93
00:06:06,739 --> 00:06:08,830
plus Fibonacci of one.

94
00:06:08,830 --> 00:06:12,119
And so Fibonacci five is
gonna be Fibonacci of three

95
00:06:12,119 --> 00:06:13,807
plus Fibonacci of four.

96
00:06:13,807 --> 00:06:16,591
So generally, Fibonacci of n is gonna be

97
00:06:16,591 --> 00:06:20,133
Fibonacci of n minus one plus
Fibonacci of n minus two.

98
00:06:21,986 --> 00:06:24,648
So we could say that here.

99
00:06:26,814 --> 00:06:29,424
Instead of factorial,
we call it Fibonacci.

100
00:06:29,424 --> 00:06:31,897
And we'll notice that like
they're almost the same thing.

101
00:06:33,980 --> 00:06:35,852
Say Fib.

102
00:06:35,852 --> 00:06:39,076
If n minus, if n is
greater than one, we return

103
00:06:45,290 --> 00:06:48,622
Fibonacci of n minus one.

104
00:06:54,828 --> 00:06:58,924
And this gives us the
Fibonacci numbers actually.

105
00:07:00,337 --> 00:07:03,463
So it makes sense to you guys?

106
00:07:03,463 --> 00:07:06,872
So in the handout, there
are some example outputs

107
00:07:06,872 --> 00:07:09,675
of both of these.

108
00:07:09,675 --> 00:07:11,885
See that's what happens.

109
00:07:15,803 --> 00:07:19,711
So who has their copy of
Godel, Escher, Bach today?

110
00:07:19,711 --> 00:07:22,837
So if we look on page 132
of Godel, Escher, Bach...

111
00:07:25,055 --> 00:07:27,147
Oh no, now I can't look at it.

112
00:07:27,147 --> 00:07:28,694
Oh well.

113
00:07:28,694 --> 00:07:31,484
132 of Grodel, Escher,
Bach has these two diagrams

114
00:07:31,484 --> 00:07:35,512
that are recursive transition networks.

115
00:07:35,512 --> 00:07:38,433
They define a grammar,

116
00:07:38,433 --> 00:07:40,426
like sort of like English.

117
00:07:40,426 --> 00:07:42,119
It's not English, it's not complete,

118
00:07:42,119 --> 00:07:44,197
it's a simplified version of English

119
00:07:44,197 --> 00:07:46,841
but he communicates the essence

120
00:07:46,841 --> 00:07:49,418
of the notion of a grammar,
a recursive grammar.

121
00:07:50,385 --> 00:07:52,746
So you'll notice that

122
00:07:54,306 --> 00:07:56,306
it's hard to do it in my head.

123
00:07:56,306 --> 00:08:00,457
Fancy noun, one of the nodes
calls fancy noun again.

124
00:08:02,001 --> 00:08:04,806
It loops back out on itself.

125
00:08:04,806 --> 00:08:07,334
So this is where the recursion is.

126
00:08:07,334 --> 00:08:09,955
So what I did is I took this diagram

127
00:08:09,955 --> 00:08:12,206
and wrote a little computer program

128
00:08:12,206 --> 00:08:15,651
that whenever there's a
choice of the transitions,

129
00:08:15,651 --> 00:08:18,244
it chooses one of those
transitions at random.

130
00:08:18,244 --> 00:08:21,978
And this is the program I wrote.

131
00:08:21,978 --> 00:08:25,291
I think it's on page five of my handout.

132
00:08:25,291 --> 00:08:27,743
So if you look at that,

133
00:08:29,343 --> 00:08:33,439
yeah, I wish I had the
projector, it's unfortunate.

134
00:08:37,762 --> 00:08:40,968
Actually, can I look at the diagram?

135
00:08:45,245 --> 00:08:46,710
So if we look at fancy noun,

136
00:08:46,710 --> 00:08:49,735
we begin and it calls ordinate noun.

137
00:08:49,735 --> 00:08:53,119
And then if you look at
the program in the handout,

138
00:08:53,119 --> 00:08:55,246
you find fancy noun.

139
00:08:55,246 --> 00:08:58,180
It's sort of halfway down,
says the RTN for fancy noun.

140
00:08:59,050 --> 00:09:01,180
Fancy noun equals,

141
00:09:03,067 --> 00:09:04,590
and this is a function call.

142
00:09:04,590 --> 00:09:07,225
Well, first of all, fancy noun equals.

143
00:09:07,225 --> 00:09:09,032
When you put curly
braces around something,

144
00:09:09,032 --> 00:09:11,401
it makes it a function pretty much.

145
00:09:12,468 --> 00:09:14,782
So fancy noun equals,

146
00:09:17,124 --> 00:09:20,963
and it copies pretty much
directly from the diagram.

147
00:09:20,963 --> 00:09:25,054
Ornate noun, which is
also a function call,

148
00:09:25,054 --> 00:09:26,843
which is defined above.

149
00:09:26,843 --> 00:09:29,624
Plus, I'm still back in fancy noun,

150
00:09:29,624 --> 00:09:32,820
so ornate noun plus pick from preposition

151
00:09:34,871 --> 00:09:37,527
or relative pronoun or nothing.

152
00:09:37,527 --> 00:09:40,083
And if you look at the diagram
in Godel, Escher, Bach,

153
00:09:40,083 --> 00:09:42,420
the arrows coming out of ornate noun

154
00:09:42,420 --> 00:09:45,487
point to relative pronoun, nothing,

155
00:09:45,487 --> 00:09:47,499
the end, and preposition.

156
00:09:47,499 --> 00:09:51,091
So you can make this
into a computer program,

157
00:09:53,721 --> 00:09:55,943
which is what I did.

158
00:09:55,943 --> 00:09:58,610
So if you look at my
program for a little while,

159
00:09:58,610 --> 00:10:02,094
you'll notice that all
the arrows in the diagrams

160
00:10:02,094 --> 00:10:05,556
correspond to function
calls in the program.

161
00:10:07,153 --> 00:10:09,033
And they're recursive
because they eventually

162
00:10:09,033 --> 00:10:10,651
loop back on themselves.

163
00:10:10,651 --> 00:10:13,827
So here, Hofstadter is
trying to communicate

164
00:10:13,827 --> 00:10:15,826
the fact that languages themselves

165
00:10:15,826 --> 00:10:18,384
are defined by recursive grammars.

166
00:10:18,384 --> 00:10:22,235
This is why we can nest
sentences inside of each other.

167
00:10:22,235 --> 00:10:23,866
It's recursive.

168
00:10:23,866 --> 00:10:26,206
So recursion leads to nesting.

169
00:10:26,206 --> 00:10:28,740
And sometimes, infinite nesting.

170
00:10:28,740 --> 00:10:31,332
And that's where fractals come from.

171
00:10:31,332 --> 00:10:34,653
So right after this
program in the handout,

172
00:10:37,335 --> 00:10:39,208
there's a sample output.

173
00:10:39,208 --> 00:10:42,660
So just read through some
of those sample outputs.

174
00:10:42,660 --> 00:10:44,617
They're pretty funny.

175
00:10:46,903 --> 00:10:48,258
I have an old version.

176
00:10:48,258 --> 00:10:51,275
Can I look at someone's
handout just to read?

177
00:10:54,141 --> 00:10:57,591
So small, small bagel
inside the strange cow.

178
00:10:57,591 --> 00:11:00,339
It makes sense as an English sentence,

179
00:11:00,339 --> 00:11:03,009
and it was generated by
this computer program.

180
00:11:03,009 --> 00:11:05,519
So I think that's just fascinating.

181
00:11:05,519 --> 00:11:07,653
But of course some of
them don't make sense,

182
00:11:07,653 --> 00:11:11,217
like large small bagel that
runs large small large horn.

183
00:11:12,182 --> 00:11:15,585
Just doesn't make any sense.

184
00:11:15,585 --> 00:11:17,239
So next example.

185
00:11:20,928 --> 00:11:25,201
So the next example on page
five, I think, is a tree.

186
00:11:25,201 --> 00:11:29,742
We're gonna make a tree picture
using recursive functions.

187
00:11:29,742 --> 00:11:33,493
So I'm gonna write some
pseudocode, it's not real code,

188
00:11:44,127 --> 00:11:46,163
it's sort of pseudocode
to communicate the idea

189
00:11:46,163 --> 00:11:48,707
of what this program is doing.

190
00:12:05,294 --> 00:12:08,363
So we have a function

191
00:12:08,363 --> 00:12:09,541
that grows a tree.

192
00:12:09,541 --> 00:12:12,298
It starts from a single branch,

193
00:12:12,298 --> 00:12:14,815
and I'll do it down here.

194
00:12:14,815 --> 00:12:17,426
This is like the starting point.

195
00:12:17,426 --> 00:12:18,949
This is the entry point.

196
00:12:18,949 --> 00:12:22,050
So it says class, all this stuff, tree.

197
00:12:23,265 --> 00:12:28,017
Tree parentheses, that gets
called when the program starts.

198
00:12:28,017 --> 00:12:31,259
So this function call, grow
tree 0.5, zero, trunk height,

199
00:12:31,259 --> 00:12:34,597
all this stuff, is this first one.

200
00:12:34,597 --> 00:12:37,387
This is what initiates the process.

201
00:12:37,387 --> 00:12:40,211
And then what the function does

202
00:12:40,211 --> 00:12:42,257
is pretty much...

203
00:12:47,514 --> 00:12:50,968
If the depth is greater than zero.

204
00:13:16,636 --> 00:13:20,551
So this tree function calls itself twice,

205
00:13:22,156 --> 00:13:24,587
once for each branch.

206
00:13:25,815 --> 00:13:28,954
So the first time the
program calls this function,

207
00:13:28,954 --> 00:13:31,880
it makes this, it draws it on the screen.

208
00:13:31,880 --> 00:13:34,207
So notice here it adds

209
00:13:40,020 --> 00:13:43,654
the actual line if you look at the code.

210
00:13:44,882 --> 00:13:49,169
It says add new JV line,
x one, x two, that stuff.

211
00:13:50,140 --> 00:13:53,692
That actually adds a line to the screen.

212
00:13:54,614 --> 00:13:58,140
I wish I could show you the
actual code running but I can't.

213
00:14:00,258 --> 00:14:01,774
So this is the first time.

214
00:14:01,774 --> 00:14:04,777
And then depth is the number of times

215
00:14:04,777 --> 00:14:07,145
it's going to branch out.

216
00:14:07,145 --> 00:14:11,192
And so depth is 11, it's
gonna make a big tree.

217
00:14:12,590 --> 00:14:16,931
What it's gonna do is
make two sub branches.

218
00:14:16,931 --> 00:14:20,497
This is grow tree, this one
correlates to this one here,

219
00:14:21,918 --> 00:14:24,605
and this one corresponds to this one here.

220
00:14:27,465 --> 00:14:29,874
If you look at the code in the handout,

221
00:14:29,874 --> 00:14:32,678
it says grow tree, x two, y two.

222
00:14:34,393 --> 00:14:38,230
X two, y two is the end
point of the previous branch.

223
00:14:38,230 --> 00:14:40,212
Root length times size factor.

224
00:14:40,212 --> 00:14:44,392
So size factor is a factor
by which it's going to scale.

225
00:14:44,392 --> 00:14:48,578
So this would be like
maybe half a size, or 0.7.

226
00:14:50,237 --> 00:14:53,941
Size factor is 0.58, so
it's about half the size.

227
00:14:54,820 --> 00:14:57,547
And root angle plus angle factor,

228
00:14:57,547 --> 00:14:59,495
root angle minus angle factor.

229
00:14:59,495 --> 00:15:02,697
These are in the two
grow tree function calls.

230
00:15:02,697 --> 00:15:06,686
Angle factor, which is
point, well, pi over four,

231
00:15:08,847 --> 00:15:11,299
it's exactly 45 degrees.

232
00:15:11,299 --> 00:15:14,090
So each time it branches,
the two branches are gonna

233
00:15:14,090 --> 00:15:16,611
branch out as that angle.

234
00:15:16,611 --> 00:15:20,703
And so here, say we do depth of four

235
00:15:22,188 --> 00:15:24,127
when we call it the first time.

236
00:15:24,127 --> 00:15:26,138
The depth here is gonna be four.

237
00:15:26,138 --> 00:15:30,058
And then you pass into the
function, depth minus one.

238
00:15:31,720 --> 00:15:36,105
So here inside the function
that's generating this depth

239
00:15:36,105 --> 00:15:37,727
that's gonna be three,

240
00:15:37,727 --> 00:15:40,342
and so it's gonna keep going
down until depth is zero.

241
00:15:40,342 --> 00:15:44,086
So here, depth is, well, depth it's four,

242
00:15:45,970 --> 00:15:48,720
three, two, one.

243
00:15:55,817 --> 00:15:58,520
And it does it on this side too.

244
00:16:04,506 --> 00:16:05,931
So it just keeps going like this.

245
00:16:05,931 --> 00:16:07,647
This is a fractal.

246
00:16:09,228 --> 00:16:11,593
And you could imagine if you were to

247
00:16:11,593 --> 00:16:13,896
continue this infinitely,

248
00:16:15,374 --> 00:16:17,769
like instead of saying depth of 10 or 11,

249
00:16:17,769 --> 00:16:19,940
just say depth of infinity,

250
00:16:19,940 --> 00:16:21,874
say theoretically if we could do this,

251
00:16:21,874 --> 00:16:25,473
this shape could be zoomed
in on infinitely forever,

252
00:16:27,151 --> 00:16:29,008
and this is the notion of a fractal.

253
00:16:29,008 --> 00:16:32,709
And it would look the same as
it does on the large scale.

254
00:16:32,709 --> 00:16:35,913
So any questions about the tree?

255
00:16:35,913 --> 00:16:38,626
So next we're gonna do the Koch curve.

256
00:16:41,559 --> 00:16:44,389
Koch curve is sort of similar to the tree

257
00:16:45,775 --> 00:16:48,602
except that the rules are different.

258
00:16:50,482 --> 00:16:54,071
So first conceptually, this
is what a Koch curve is.

259
00:16:54,071 --> 00:16:56,517
You start with a line,

260
00:16:56,517 --> 00:17:00,135
or in some cases a triangle
to make the the whole thing;

261
00:17:00,135 --> 00:17:03,609
and you divide it into three
parts and then you make

262
00:17:03,609 --> 00:17:07,736
an equilateral triangle, I
mean the sides are all the same

263
00:17:07,736 --> 00:17:11,180
out of the thing in the middle
and get rid of this line.

264
00:17:13,797 --> 00:17:15,253
So this is the rule.

265
00:17:15,253 --> 00:17:17,369
Go from a line to this thing.

266
00:17:17,369 --> 00:17:19,691
And then this rule is applied to each one

267
00:17:19,691 --> 00:17:21,028
of these segments.

268
00:17:21,028 --> 00:17:22,722
So you go like this.

269
00:17:24,997 --> 00:17:28,752
And so on, like to each
of these smaller segments.

270
00:17:30,795 --> 00:17:33,375
So the fact that like the simple rule

271
00:17:33,375 --> 00:17:36,114
is being applied to
something over and over again

272
00:17:36,114 --> 00:17:40,535
and the thing that's being applied to
is the result of the previous execution

273
00:17:40,535 --> 00:17:43,587
of the rule, makes it recursive.

274
00:17:45,090 --> 00:17:48,651
So I keep drawing it.

275
00:17:48,651 --> 00:17:51,790
Let's look at the actual
code, the program.

276
00:17:51,790 --> 00:17:55,975
This is Koch, I think it's on page seven.

277
00:17:59,653 --> 00:18:02,955
So let's see, CreateCurve.

278
00:18:12,718 --> 00:18:16,464
What CreateCurve does essentially is

279
00:18:19,652 --> 00:18:22,281
call itself four times.

280
00:18:27,963 --> 00:18:31,509
And each of those four times
corresponds to this one,

281
00:18:31,509 --> 00:18:34,259
this one, this one and this one.

282
00:18:41,286 --> 00:18:44,107
So yeah, let's look at the actual code.

283
00:18:45,310 --> 00:18:47,596
You see these four function
calls to CreateCurve

284
00:18:47,596 --> 00:18:49,867
in the middle there?

285
00:18:49,867 --> 00:18:53,238
x one, y one, ax, ay, cx,
cy, by, all this stuff.

286
00:18:56,868 --> 00:19:00,027
If you look at the little red diagram,

287
00:19:01,010 --> 00:19:04,716
this point is x one y, one and you know,

288
00:19:06,026 --> 00:19:08,359
it's in the diagram what the points are.

289
00:19:08,359 --> 00:19:10,705
So the first function call

290
00:19:12,486 --> 00:19:16,052
pretty much says apply
the rule to this segment.

291
00:19:16,052 --> 00:19:18,061
The second function call starts from a,

292
00:19:18,061 --> 00:19:20,741
which is this point here,
which says apply the rule

293
00:19:20,741 --> 00:19:22,310
to this segment.

294
00:19:22,310 --> 00:19:24,784
The third one starts at
c, which is the top point

295
00:19:24,784 --> 00:19:28,097
and it says apply the
rule to this segment.

296
00:19:29,182 --> 00:19:33,150
And and the fourth one
applies the rule to this one.

297
00:19:33,150 --> 00:19:36,933
So it's another beautiful
recursive fractal.

298
00:19:39,874 --> 00:19:43,141
So what happens, so
this is the Koch curve.

299
00:19:43,141 --> 00:19:46,560
If you generalize this and
add a randomness to it,

300
00:19:46,560 --> 00:19:50,184
say these points are a, it doesn't matter

301
00:19:50,184 --> 00:19:52,516
what they're called, if you move this one

302
00:19:52,516 --> 00:19:55,833
up and down a little bit randomly,

303
00:19:56,740 --> 00:19:59,467
so like you start from this

304
00:19:59,467 --> 00:20:02,511
instead of making these points exact,

305
00:20:02,511 --> 00:20:04,524
make them like a little bit off

306
00:20:04,524 --> 00:20:07,270
and then connect the lines

307
00:20:07,270 --> 00:20:10,554
and make a line, a triangle there.

308
00:20:10,554 --> 00:20:12,604
And this is also a little bit off.

309
00:20:12,604 --> 00:20:14,984
And then if you keep doing
this, adding a little bit

310
00:20:14,984 --> 00:20:16,974
of randomization each time,

311
00:20:16,974 --> 00:20:20,988
you actually get lines that
look just like coastlines

312
00:20:20,988 --> 00:20:24,351
around pieces of land.

313
00:20:24,351 --> 00:20:26,637
And if you generalize
this into three dimensions

314
00:20:26,637 --> 00:20:28,943
and do this randomness,
it actually generates

315
00:20:28,943 --> 00:20:33,160
3D mountains like virtual 3D surfaces

316
00:20:33,160 --> 00:20:36,566
that look exactly like real mountains.

317
00:20:36,566 --> 00:20:40,885
So it's sort of strange like
these recursive structures are

318
00:20:40,885 --> 00:20:43,385
definitely in nature.

319
00:20:45,360 --> 00:20:47,930
- [Female student] What
does it mean (mumbles) page,

320
00:20:47,930 --> 00:20:49,985
page six, the Koch
snowflake has finite area

321
00:20:49,985 --> 00:20:51,344
but infinite perimeter?

322
00:20:51,344 --> 00:20:53,587
- Oh yeah, yeah, I forgot to mention that,

323
00:20:53,587 --> 00:20:54,970
that's a really cool thing.

324
00:20:54,970 --> 00:20:59,595
So the Koch snowflake is when
you start with a triangle

325
00:20:59,595 --> 00:21:02,762
and you apply the rule to
each sides of the triangle

326
00:21:04,845 --> 00:21:09,845
and you get this curve on all these sides.

327
00:21:10,214 --> 00:21:12,601
So it's been mathematically proven,

328
00:21:12,601 --> 00:21:14,348
or you know extrapolated that

329
00:21:14,348 --> 00:21:17,531
if you were to do this rule
an infinite number of times,

330
00:21:17,531 --> 00:21:20,455
which you can do in math
because it's all theoretical,

331
00:21:20,455 --> 00:21:23,717
the volume inside of this
object would be finite.

332
00:21:23,717 --> 00:21:25,989
It's a definite amount.

333
00:21:25,989 --> 00:21:28,461
But the surface area is infinite.

334
00:21:29,958 --> 00:21:32,193
Well, not surface area, the perimeter.

335
00:21:32,193 --> 00:21:34,055
The perimeter is infinite.

336
00:21:34,055 --> 00:21:37,284
That's because every
time you apply the rule,

337
00:21:37,284 --> 00:21:40,886
you actually increase the perimeter.

338
00:21:40,886 --> 00:21:42,164
So this

339
00:21:44,885 --> 00:21:46,697
has a certain length.

340
00:21:46,697 --> 00:21:48,441
And then once you apply the rule to it,

341
00:21:48,441 --> 00:21:50,628
if you do this,

342
00:21:50,628 --> 00:21:54,927
then this new curve, the
total length is longer

343
00:21:54,927 --> 00:21:56,501
than this one.

344
00:21:56,501 --> 00:21:58,439
So you can imagine, if
you do it infinitely,

345
00:21:58,439 --> 00:22:01,289
like it's just gonna be infinitely long.

346
00:22:01,289 --> 00:22:02,891
So it's sort of mind-boggling.

347
00:22:02,891 --> 00:22:05,024
And this goes, yeah, what's up?

348
00:22:05,024 --> 00:22:06,670
(distant indistinct muttering)

349
00:22:07,910 --> 00:22:10,963
Yeah, it gets smaller
and smaller definitely.

350
00:22:12,379 --> 00:22:16,481
But if you do it theoretically
an infinite number of times,

351
00:22:18,221 --> 00:22:19,902
like it'll still exist.

352
00:22:19,902 --> 00:22:22,017
If you look at the picture

353
00:22:24,554 --> 00:22:27,831
on page six, right next to the title,

354
00:22:29,367 --> 00:22:33,329
the Koch snowflake, that
curve there, you see it?

355
00:22:35,124 --> 00:22:37,011
That's sort of what it would look like

356
00:22:37,011 --> 00:22:39,382
even if you did it an
infinite number of times.

357
00:22:39,382 --> 00:22:41,272
(distant indistinct muttering)

358
00:22:45,448 --> 00:22:47,679
Say again?
(distant indistinct muttering)

359
00:22:57,351 --> 00:22:59,684
So like, you just cut it in half?

360
00:22:59,684 --> 00:23:01,875
- [Male student] Not in
half but just cut like

361
00:23:01,875 --> 00:23:04,230
(distant indistinct muttering)

362
00:23:10,537 --> 00:23:12,808
- I don't really understand.

363
00:23:12,808 --> 00:23:14,573
You can draw it on the board if you want.

364
00:23:14,573 --> 00:23:16,475
- On the board?
- Yeah.

365
00:23:22,013 --> 00:23:26,347
- I have like a circle, I just
cut like this part over here.

366
00:23:26,347 --> 00:23:29,074
Even if this is like finite area,

367
00:23:29,074 --> 00:23:31,644
you're saying that if I
cut it like that, (mumbles)

368
00:23:31,644 --> 00:23:33,441
(crosstalk)

369
00:23:39,445 --> 00:23:40,798
- I see what you mean.

370
00:23:40,798 --> 00:23:43,648
So say you have Koch curve, this shape,

371
00:23:48,817 --> 00:23:52,005
and it were a string and you would cut it

372
00:23:52,005 --> 00:23:54,273
so the string would now be loose?

373
00:23:54,273 --> 00:23:58,045
And if you pulled it,
it would go on forever?

374
00:23:58,045 --> 00:23:59,942
Yeah, it would.

375
00:23:59,942 --> 00:24:01,563
- [Male student] Sounds nice.

376
00:24:01,563 --> 00:24:02,945
- Yeah.

377
00:24:02,945 --> 00:24:05,381
That's what it means to
have infinite perimeter,

378
00:24:05,381 --> 00:24:09,172
which is why it's just so
fascinating, like it's crazy.

379
00:24:09,172 --> 00:24:11,189
People trying to measure
the coast of Britain.

380
00:24:11,189 --> 00:24:12,798
How long is the coast of Britain, right?

381
00:24:12,798 --> 00:24:14,697
Have you heard about this problem?

382
00:24:14,697 --> 00:24:17,298
If you look at it on a large scale,

383
00:24:17,298 --> 00:24:19,738
like from a satellite
image of the whole country,

384
00:24:19,738 --> 00:24:21,846
you can just draw a line
around it and say like oh yeah,

385
00:24:21,846 --> 00:24:23,865
it's this length, this is the length

386
00:24:23,865 --> 00:24:25,228
of the coast of Britain.

387
00:24:25,228 --> 00:24:28,706
But if you zoom in on it,
you'll find tha those big lines

388
00:24:28,706 --> 00:24:31,302
that you drew are actually
like really wrong.

389
00:24:31,302 --> 00:24:33,716
Like they don't actually line up.

390
00:24:33,716 --> 00:24:37,049
So if you make it more precise
to this new zooming angle,

391
00:24:37,049 --> 00:24:39,888
the zooming, it gets longer.

392
00:24:39,888 --> 00:24:42,430
And so actually, the more that you zoom in

393
00:24:42,430 --> 00:24:45,788
on the coast of Britain the
longer the perimeter gets.

394
00:24:46,673 --> 00:24:49,000
(distant indistinct muttering)

395
00:24:50,740 --> 00:24:52,455
Yeah, just adding little pieces.

396
00:24:52,455 --> 00:24:56,319
So say the actual coast
of Britain is like that,

397
00:24:57,337 --> 00:25:01,102
but you look at it like at
this huge distance away.

398
00:25:01,102 --> 00:25:04,523
You say like oh yeah, this
is approximately that line.

399
00:25:04,523 --> 00:25:06,757
But if you look at it
more detail and refine it,

400
00:25:06,757 --> 00:25:08,367
you say oh it's not actually that line,

401
00:25:08,367 --> 00:25:11,255
it's maybe like these lines.

402
00:25:11,255 --> 00:25:14,575
But the new lines are actually,
the whole thing is longer.

403
00:25:14,575 --> 00:25:16,561
And if you do it even
more and more precisely,

404
00:25:16,561 --> 00:25:18,555
you'd just get longer
and longer and longer.

405
00:25:18,555 --> 00:25:20,572
So nobody's been able to really figure out

406
00:25:20,572 --> 00:25:22,418
how long the coast of Britain is.

407
00:25:22,418 --> 00:25:23,724
It's a fractal.

408
00:25:23,724 --> 00:25:26,505
- [Male] Is it even possible like

409
00:25:26,505 --> 00:25:29,432
(distant indistinct muttering)

410
00:25:32,618 --> 00:25:35,169
- Well, not really.

411
00:25:39,334 --> 00:25:41,805
So he asks like, is it
possible in this world

412
00:25:41,805 --> 00:25:44,877
to have something that's
really infinite like that?

413
00:25:44,877 --> 00:25:46,981
No, it's not.

414
00:25:46,981 --> 00:25:50,875
Because I mean, there's only
finite space on the earth.

415
00:25:50,875 --> 00:25:53,968
- [Male student] Yeah but I mean,

416
00:25:53,968 --> 00:25:57,132
you just said that even
if it has finite area

417
00:25:57,132 --> 00:26:00,486
(distant indistinct muttering)

418
00:26:00,486 --> 00:26:03,041
- Yeah, so the Koch curve theoretically,

419
00:26:03,041 --> 00:26:05,551
you know in math language,

420
00:26:05,551 --> 00:26:07,837
if you do it mathematically,
it has infinite perimeter

421
00:26:07,837 --> 00:26:09,296
but finite area.

422
00:26:09,296 --> 00:26:11,519
But keep in mind this is
a theoretical creation.

423
00:26:11,519 --> 00:26:14,713
It's just in the world of math

424
00:26:14,713 --> 00:26:18,666
and it can't really exist in the universe.

425
00:26:18,666 --> 00:26:21,702
But things come pretty
close to it in nature.

426
00:26:21,702 --> 00:26:24,394
It's not actually infinite,
the coastline of Britain

427
00:26:24,394 --> 00:26:25,979
is not actually infinite,

428
00:26:25,979 --> 00:26:29,437
but it really resembles
this sort of shape.

429
00:26:30,596 --> 00:26:32,100
So let's see.

430
00:26:35,359 --> 00:26:38,769
Yeah, so any questions
about the Koch curve?

431
00:26:38,769 --> 00:26:40,821
It's really interesting.

432
00:26:41,671 --> 00:26:45,241
So the next example is

433
00:26:45,241 --> 00:26:47,896
the Sierpinski triangle, page eight.

434
00:26:50,372 --> 00:26:53,811
So the Sierpinski triangle
is very interesting.

435
00:27:02,911 --> 00:27:05,696
You take a big triangle

436
00:27:06,987 --> 00:27:10,866
and you add a smaller triangle
inside of it like this.

437
00:27:13,712 --> 00:27:17,792
So this is the rule for
the Sierpinski triangle.

438
00:27:17,792 --> 00:27:21,778
And you know, this is
colored in or something.

439
00:27:23,044 --> 00:27:26,230
So this is the rule and what
you get is three new triangles.

440
00:27:26,230 --> 00:27:30,356
And then you apply the same
rule to these new triangles.

441
00:27:35,386 --> 00:27:38,776
So that's recursion when you apply a rule

442
00:27:38,776 --> 00:27:41,494
to something that you
already applied a rule to.

443
00:27:41,494 --> 00:27:45,762
So you apply it again and you
get these even smaller things,

444
00:27:47,576 --> 00:27:50,970
these smaller triangles,
and it goes down infinitely

445
00:27:50,970 --> 00:27:54,068
if you do it infinitely.

446
00:27:54,068 --> 00:27:55,667
So imagine this.

447
00:27:55,667 --> 00:27:58,033
So this is one way of computing
it, one way of doing it,

448
00:27:58,033 --> 00:28:00,085
one way of looking at the rule.

449
00:28:00,085 --> 00:28:04,247
But what I did in the, if
you look in the lecture notes

450
00:28:04,247 --> 00:28:07,667
I talked about iterated function system.

451
00:28:08,658 --> 00:28:10,495
So that means...

452
00:28:12,849 --> 00:28:14,940
Oh, I'll just do it and
you'll see what it means.

453
00:28:14,940 --> 00:28:16,556
So let's say we start with a point.

454
00:28:16,556 --> 00:28:19,553
Say this point here, it could be any point

455
00:28:21,614 --> 00:28:23,468
and we have three possible choices,

456
00:28:23,468 --> 00:28:25,838
this is called the chaos game.

457
00:28:25,838 --> 00:28:27,696
We have three possible
choices of something

458
00:28:27,696 --> 00:28:29,105
to do with this point.

459
00:28:29,105 --> 00:28:30,808
We either bring it halfway to this point,

460
00:28:30,808 --> 00:28:34,209
half way to this point or
half way to this point.

461
00:28:34,209 --> 00:28:36,606
So let's say we bring it
halfway to this point.

462
00:28:36,606 --> 00:28:39,624
We go right here, right in the middle.

463
00:28:39,624 --> 00:28:42,243
And what we do in an
iterated function system,

464
00:28:42,243 --> 00:28:44,506
we do this over and over and over again,

465
00:28:44,506 --> 00:28:47,038
picking randomly which
one of the three points

466
00:28:47,038 --> 00:28:49,537
we go half way towards.

467
00:28:49,537 --> 00:28:52,763
So let's say we go to this
one next, we go here half way.

468
00:28:52,763 --> 00:28:54,525
And we go half way to this one.

469
00:28:54,525 --> 00:28:55,826
Half way to this one again,

470
00:28:55,826 --> 00:28:57,330
half way to this one again.

471
00:28:57,330 --> 00:28:59,971
And then half way to this one.

472
00:28:59,971 --> 00:29:02,954
And then half way to this one.

473
00:29:02,954 --> 00:29:05,313
Half way to this one and
half way to this one,

474
00:29:05,313 --> 00:29:08,722
half way to this one,
half way to this one.

475
00:29:08,722 --> 00:29:10,794
So we just plot these points

476
00:29:10,794 --> 00:29:14,545
and the program that I wrote,

477
00:29:14,545 --> 00:29:16,988
which is in the handout does this.

478
00:29:16,988 --> 00:29:19,421
It executes this.

479
00:29:19,421 --> 00:29:22,741
It just keeps going and it
keeps plotting the points.

480
00:29:22,741 --> 00:29:26,843
And eventually, what you get
is the Sierpinski triangle.

481
00:29:26,843 --> 00:29:28,209
It's crazy.

482
00:29:29,386 --> 00:29:31,556
So page eight is the...

483
00:29:32,557 --> 00:29:34,670
The picture of this is
on page eight, right?

484
00:29:34,670 --> 00:29:35,663
Yeah?

485
00:29:35,663 --> 00:29:37,025
- [Male student] So
when you do it randomly,

486
00:29:37,025 --> 00:29:39,621
it doesn't matter which one you choose?

487
00:29:39,621 --> 00:29:41,186
No matter what you choose whenever you do

488
00:29:41,186 --> 00:29:43,934
(distant indistinct muttering)

489
00:29:48,393 --> 00:29:49,862
but now this time since it's random,

490
00:29:49,862 --> 00:29:52,189
we're gonna have like
(distant indistinct muttering)

491
00:29:52,189 --> 00:29:53,670
still gonna make the same triangle?

492
00:29:53,670 --> 00:29:55,372
- Yeah, exactly.

493
00:29:55,372 --> 00:29:57,619
So he's getting at,

494
00:29:58,660 --> 00:29:59,999
say you run the program again,

495
00:29:59,999 --> 00:30:01,917
it's gonna choose differently.

496
00:30:01,917 --> 00:30:03,641
Maybe it'll choose instead
of going to this one first,

497
00:30:03,641 --> 00:30:05,579
it'll go to this one first.

498
00:30:05,579 --> 00:30:10,018
Say it does it 10 times
or 100 times to this one.

499
00:30:10,018 --> 00:30:13,225
But the program chooses
randomly which one to go to.

500
00:30:16,226 --> 00:30:18,487
And it goes to this one
and just chooses randomly.

501
00:30:18,487 --> 00:30:20,606
So he asked even though it's random,

502
00:30:20,606 --> 00:30:22,295
will it still generate the same picture?

503
00:30:22,295 --> 00:30:24,980
And the answer is yes, it will.

504
00:30:24,980 --> 00:30:26,925
It's crazy, like just fascinating.

505
00:30:28,521 --> 00:30:30,245
And we'll understand this better

506
00:30:30,245 --> 00:30:33,167
after we do the next example,
which is making a fern,

507
00:30:33,167 --> 00:30:35,826
a fractal fern, which is really cool.

508
00:30:36,885 --> 00:30:40,175
So let's just look at the code quickly

509
00:30:42,131 --> 00:30:43,174
and think about this.

510
00:30:43,174 --> 00:30:45,570
Is the code for the
Sierpinski triangle recursive?

511
00:30:47,082 --> 00:30:49,630
So what it does is

512
00:30:49,630 --> 00:30:51,098
see def, draw Sierpinski,

513
00:30:51,098 --> 00:30:53,732
that's the thing that draws the triangle.

514
00:30:53,732 --> 00:30:56,994
Def a, b and c are these three points.

515
00:30:56,994 --> 00:30:59,165
So this is like a, b, c.

516
00:31:06,569 --> 00:31:09,427
Def points equals a list of a, b and c.

517
00:31:10,537 --> 00:31:14,337
Current point is just, you
know, say start at point a.

518
00:31:17,894 --> 00:31:20,140
This statement, while true,

519
00:31:21,387 --> 00:31:24,325
means execute this code repeatedly.

520
00:31:24,325 --> 00:31:26,124
Just keep doing it an
infinite number of times

521
00:31:26,124 --> 00:31:29,025
until you stop the program.

522
00:31:29,025 --> 00:31:32,794
So it says def next point
equals pick from points,

523
00:31:32,794 --> 00:31:34,938
and pick from is a function defined above,

524
00:31:34,938 --> 00:31:37,596
which pretty much picks
at random out of the list

525
00:31:37,596 --> 00:31:39,380
that you give it.

526
00:31:39,380 --> 00:31:42,528
So that pick from is the
thing that picks randomly

527
00:31:42,528 --> 00:31:45,137
which one of these to go to.

528
00:31:45,137 --> 00:31:47,484
So it says okay, next
point, pick from points.

529
00:31:47,484 --> 00:31:49,619
So that gives you a point

530
00:31:49,619 --> 00:31:52,229
and then current point
x equals current point x

531
00:31:52,229 --> 00:31:54,366
plus next point x divided by two.

532
00:31:54,366 --> 00:31:56,558
So what you're doing is averaging

533
00:31:56,558 --> 00:31:59,172
the x coordinates of the current point

534
00:31:59,172 --> 00:32:01,528
and the point that you're
going to go to next.

535
00:32:01,528 --> 00:32:03,143
And if you do that for x and y,

536
00:32:03,143 --> 00:32:05,581
what you do is go, that's going halfway

537
00:32:05,581 --> 00:32:08,130
between the current
point and the next point.

538
00:32:09,674 --> 00:32:11,259
That's what that does.

539
00:32:11,259 --> 00:32:13,927
An image dot fill pixel at that point.

540
00:32:13,927 --> 00:32:16,971
So that's what plots it on the screen.

541
00:32:16,971 --> 00:32:19,089
And the picture here is actually,

542
00:32:19,089 --> 00:32:22,847
what's actually generated
by this very program.

543
00:32:24,347 --> 00:32:26,300
So it keeps going, keeps plotting it.

544
00:32:26,300 --> 00:32:28,418
So here's the question, is this recursive?

545
00:32:28,418 --> 00:32:30,566
Is this thing actually recursive?

546
00:32:30,566 --> 00:32:32,510
Because we said a recursive function

547
00:32:32,510 --> 00:32:34,873
is a function that calls itself.

548
00:32:34,873 --> 00:32:37,123
Let's hold off on that answer

549
00:32:37,123 --> 00:32:38,984
until after we do the next one.

550
00:32:38,984 --> 00:32:41,440
Any questions so far?

551
00:32:41,440 --> 00:32:43,890
So the next thing we're
gonna do is the fern.

552
00:32:43,890 --> 00:32:45,304
Yeah?

553
00:32:45,304 --> 00:32:48,532
(distant indistinct muttering)

554
00:32:48,532 --> 00:32:50,387
So recursion is...

555
00:32:52,403 --> 00:32:55,471
Generally, recursion is
something which is defined

556
00:32:55,471 --> 00:32:57,696
in terms of itself.

557
00:32:59,927 --> 00:33:03,698
Something that loops back on itself.

558
00:33:03,698 --> 00:33:05,853
(distant indistinct muttering)

559
00:33:07,138 --> 00:33:08,131
Say again?

560
00:33:08,131 --> 00:33:10,400
- [Female student] Like
if you apply that rule,

561
00:33:10,400 --> 00:33:12,194
it'll become the same
thing you started with?

562
00:33:12,194 --> 00:33:13,355
- If you apply which rule?

563
00:33:13,355 --> 00:33:14,897
The recursive rule?
- [Female student] Yeah.

564
00:33:14,897 --> 00:33:18,182
- It'll become the same
that it started with?

565
00:33:18,182 --> 00:33:22,059
No, not necessarily because
each time it applies the rule,

566
00:33:23,895 --> 00:33:25,956
there's a slight change.

567
00:33:25,956 --> 00:33:29,897
With this factorial, it's
not just saying n factorial

568
00:33:29,897 --> 00:33:31,693
equals n factorial.

569
00:33:31,693 --> 00:33:34,659
It's saying n factorial
equals n minus one factorial.

570
00:33:36,971 --> 00:33:38,556
The factorial part is recursive,

571
00:33:38,556 --> 00:33:41,529
but it doesn't loop
back on itself exactly.

572
00:33:41,529 --> 00:33:43,889
There's some change.

573
00:33:43,889 --> 00:33:47,638
And with recursive functions at least...

574
00:33:49,821 --> 00:33:53,159
So the function is
defined, it calls itself.

575
00:33:53,159 --> 00:33:56,115
I don't know if this really
answers your question but

576
00:33:56,115 --> 00:33:58,310
say if we didn't have these parts,

577
00:33:58,310 --> 00:34:00,181
if the function just was this,

578
00:34:00,181 --> 00:34:03,623
if def Fibonachi, return
Fibonacci of n minus one,

579
00:34:03,623 --> 00:34:06,711
n minus two, what would
happen is it would call itself

580
00:34:08,545 --> 00:34:10,894
and just keep going infinitely,

581
00:34:10,894 --> 00:34:12,958
which is a problem.

582
00:34:12,958 --> 00:34:16,805
So all recursive functions,
in order to do anything,

583
00:34:16,805 --> 00:34:18,570
have to bottom out at some
point, they have to stop.

584
00:34:18,570 --> 00:34:20,618
And that's what this is.

585
00:34:20,618 --> 00:34:23,063
Only do this if n is greater than one.

586
00:34:23,063 --> 00:34:25,638
If n is less than or equal to one, return.

587
00:34:27,103 --> 00:34:29,165
So it just stops it.

588
00:34:29,165 --> 00:34:32,656
So I mean, does it answer your question?

589
00:34:34,691 --> 00:34:37,146
You can ask it again if you want.

590
00:34:38,079 --> 00:34:40,471
- [Female student] So from the trianble b

591
00:34:40,471 --> 00:34:43,510
(distant indistinct muttering)

592
00:34:43,510 --> 00:34:45,383
- It is yeah.

593
00:34:45,383 --> 00:34:47,525
- [Female student] Because it
has to return to some place

594
00:34:47,525 --> 00:34:50,416
(distant indistinct muttering)

595
00:34:52,309 --> 00:34:55,331
- Only functions, computer functions

596
00:34:55,331 --> 00:34:57,901
that are recursive need to bottom out.

597
00:34:57,901 --> 00:35:01,562
There are other kinds of recursion.

598
00:35:01,562 --> 00:35:03,504
- [Female student] Natural recursions?

599
00:35:03,504 --> 00:35:04,791
- Well, they do.

600
00:35:04,791 --> 00:35:07,115
Like natural recursions don't bottom out.

601
00:35:07,115 --> 00:35:09,591
Well, they do have to
bottom out eventually.

602
00:35:09,591 --> 00:35:11,764
Take for example a tree in nature.

603
00:35:11,764 --> 00:35:13,328
It branches and branches and branches,

604
00:35:13,328 --> 00:35:15,261
but eventually it just gets to a leaf

605
00:35:15,261 --> 00:35:16,720
and it stops branching.

606
00:35:16,720 --> 00:35:18,540
There's some sort of program

607
00:35:18,540 --> 00:35:22,346
that's executing inside of
this tree that's recursive

608
00:35:22,346 --> 00:35:26,026
and there's a certain signal
that this program gets

609
00:35:26,026 --> 00:35:28,316
when the branch gets to
a certain size I think

610
00:35:28,316 --> 00:35:31,393
or something, that signals
it to generate a leaf.

611
00:35:31,393 --> 00:35:35,589
So I mean, those kind of
recursive processes do bottom out.

612
00:35:35,589 --> 00:35:37,463
But this one is actually recursive.

613
00:35:37,463 --> 00:35:38,922
We'll see why in a minute,

614
00:35:38,922 --> 00:35:40,244
but it doesn't bottom out

615
00:35:40,244 --> 00:35:42,872
because it just keeps going forever.

616
00:35:42,872 --> 00:35:45,544
- [Male student] Do you mean
that when you have like,

617
00:35:45,544 --> 00:35:48,567
when you're doing (distant
indistinct muttering)

618
00:36:09,066 --> 00:36:10,868
- Yeah, exactly, exactly.

619
00:36:10,868 --> 00:36:12,805
That was very well put.

620
00:36:12,805 --> 00:36:15,572
So what he's basically
was if you want to get

621
00:36:15,572 --> 00:36:19,538
any real manifestation of recursion,

622
00:36:19,538 --> 00:36:22,526
it has to bottom out in order
to return to you the result.

623
00:36:22,526 --> 00:36:24,630
But yeah, you can imagine
theoretical worlds

624
00:36:24,630 --> 00:36:26,806
where it doesn't bottom out.

625
00:36:26,806 --> 00:36:28,333
It goes on forever.

626
00:36:28,333 --> 00:36:30,722
Actually, Douglas
Hofstadter in the dialogue

627
00:36:30,722 --> 00:36:33,073
before this chapter does that.

628
00:36:33,073 --> 00:36:35,885
A genie has to ask a meta
genie, has to ask a meta genie.

629
00:36:35,885 --> 00:36:37,374
Did anybody read that?

630
00:36:37,374 --> 00:36:39,750
(distant indistinct muttering)

631
00:36:41,619 --> 00:36:43,703
Yeah, the time is smaller and smaller.

632
00:36:43,703 --> 00:36:46,638
So like eventually, you just repeat

633
00:36:46,638 --> 00:36:48,724
an infinite number of intensely small...

634
00:36:48,724 --> 00:36:50,835
(distant indistinct muttering)

635
00:36:50,835 --> 00:36:54,237
Yeah, yeah, isn't that crazy?

636
00:36:54,237 --> 00:36:57,780
Yeah, it's really something
to think about, yeah.

637
00:36:57,780 --> 00:36:59,625
But that's like theoretical

638
00:36:59,625 --> 00:37:03,050
but it is very interesting to think about.

639
00:37:03,050 --> 00:37:05,762
So we'll see how this is
recursive after we do the fern.

640
00:37:05,762 --> 00:37:09,002
So the fractal fern is next, page nine.

641
00:37:11,735 --> 00:37:14,708
Yeah, this is really, really cool.

642
00:37:26,999 --> 00:37:28,885
So the fractal fern.

643
00:37:28,885 --> 00:37:31,356
It looks beautiful, doesn't it?

644
00:37:31,356 --> 00:37:34,110
So we have this triangle.

645
00:37:38,921 --> 00:37:40,840
This isn't a picture in the handout.

646
00:37:40,840 --> 00:37:43,149
There's an outside triangle that's black

647
00:37:43,149 --> 00:37:46,306
and there's an inside triangle that's blue

648
00:37:46,306 --> 00:37:50,181
and some other triangles
that (mumbles) leaves.

649
00:37:50,181 --> 00:37:51,865
So first of all, I wanna talk about

650
00:37:51,865 --> 00:37:54,857
this notion of a
coordinate transformation.

651
00:37:54,857 --> 00:37:56,300
You have...

652
00:37:59,267 --> 00:38:01,526
Say we had a coordinate transformation

653
00:38:01,526 --> 00:38:05,286
between this rectangle and this rectangle.

654
00:38:05,286 --> 00:38:07,891
What would happen it like
it's a function on a point,

655
00:38:07,891 --> 00:38:10,229
a two-dimensional point.

656
00:38:10,229 --> 00:38:13,464
So say you had the point
right here, this point.

657
00:38:14,584 --> 00:38:16,976
You apply this transformation to the point

658
00:38:16,976 --> 00:38:19,992
and what you get is this point here.

659
00:38:21,481 --> 00:38:24,537
So you have this point here

660
00:38:24,537 --> 00:38:27,710
and you apply the
transformation to that point,

661
00:38:27,710 --> 00:38:30,578
you'll get this point here.

662
00:38:30,578 --> 00:38:34,059
It's just like a little
copy of this, okay?

663
00:38:35,518 --> 00:38:39,924
So this is a function,
this is the function part

664
00:38:39,924 --> 00:38:42,427
of iterated function systems.

665
00:38:42,427 --> 00:38:45,554
Iteration is the fact that
you just keep doing it,

666
00:38:45,554 --> 00:38:48,673
and a system is the fact that
there's more than one of them.

667
00:38:48,673 --> 00:38:51,290
It's like a bunch, in
this case it's three.

668
00:38:51,290 --> 00:38:54,014
I'll talk about it in a minute.

669
00:38:58,396 --> 00:39:01,363
With a fractal fern, what we have is

670
00:39:05,450 --> 00:39:07,434
a rectangle like this.

671
00:39:14,311 --> 00:39:17,644
So this, the fractal fern

672
00:39:17,644 --> 00:39:20,341
is an iterated function system

673
00:39:20,341 --> 00:39:23,486
that has four possible functions.

674
00:39:23,486 --> 00:39:25,385
This one has three.

675
00:39:25,385 --> 00:39:27,852
Each one of those points
is one, it's a function.

676
00:39:27,852 --> 00:39:30,106
Going halfway to one of
those points as a function.

677
00:39:30,106 --> 00:39:33,442
But in the fern one,
there are four functions.

678
00:39:33,442 --> 00:39:35,953
This is one of them.

679
00:39:35,953 --> 00:39:38,771
And each function is a
coordinate transformation.

680
00:39:38,771 --> 00:39:40,544
This function is a
coordinate transformation

681
00:39:40,544 --> 00:39:42,211
from this outer one.

682
00:39:42,211 --> 00:39:45,162
This outer rectangle to
this inner rectangle.

683
00:39:45,162 --> 00:39:48,038
So if we had this point in this rectangle

684
00:39:48,038 --> 00:39:50,500
and we applied this transformation,

685
00:39:50,500 --> 00:39:53,695
we would get this point here.

686
00:39:56,221 --> 00:40:00,395
So say we have the middle
point of this outer rectangle.

687
00:40:03,549 --> 00:40:07,315
And we apply this transformation once.

688
00:40:07,315 --> 00:40:09,852
We would get the middle point
of this inner rectangle,

689
00:40:09,852 --> 00:40:12,528
which is about right here.

690
00:40:14,758 --> 00:40:18,113
But here, what we do is we say okay,

691
00:40:18,113 --> 00:40:22,033
now this new point is actually
in the outer rectangle,

692
00:40:22,033 --> 00:40:25,717
and we'll apply the
transformation again on that.

693
00:40:26,655 --> 00:40:29,587
So this this point in the outer rectangle

694
00:40:29,587 --> 00:40:33,249
maps to about this point
in the smaller rectangle.

695
00:40:35,009 --> 00:40:38,402
And then you say okay, this
point is now a point in this one

696
00:40:38,402 --> 00:40:41,528
and you apply it again,
and you get this point here

697
00:40:41,528 --> 00:40:44,107
in this point here, this point here.

698
00:40:44,107 --> 00:40:46,723
And like all these points.

699
00:40:46,723 --> 00:40:50,275
And eventually, they just
get smaller and smaller

700
00:40:50,275 --> 00:40:53,578
because the corner points

701
00:40:53,578 --> 00:40:57,754
of these two rectangles
are the same point.

702
00:40:57,754 --> 00:41:00,000
I think, (mumbles)

703
00:41:01,300 --> 00:41:04,650
So let's look at another one.

704
00:41:04,650 --> 00:41:06,368
Let's see.

705
00:41:16,840 --> 00:41:20,821
So this is the thing that's gonna map to.

706
00:41:23,060 --> 00:41:26,829
It's a line, but think
of it as a rectangle.

707
00:41:28,128 --> 00:41:30,084
It's a coordinate transformation.

708
00:41:30,084 --> 00:41:34,371
So we go from any point
in this outer rectangle

709
00:41:35,641 --> 00:41:37,348
to a point on here.

710
00:41:37,348 --> 00:41:41,113
So say if we have this point
here in the outer rectangle,

711
00:41:41,113 --> 00:41:44,129
it's gonna go to the
top point of this line.

712
00:41:44,129 --> 00:41:46,047
If we have this point here, it's gonna go

713
00:41:46,047 --> 00:41:47,279
to the bottom point of this line.

714
00:41:47,279 --> 00:41:48,469
If we have the center point,

715
00:41:48,469 --> 00:41:50,982
it'll go to the center of this line.

716
00:41:50,982 --> 00:41:54,692
So let's imagine an
iterated function system

717
00:41:54,692 --> 00:41:56,267
with only these two functions.

718
00:41:56,267 --> 00:42:00,371
What's gonna happen is, and
let's say each one is chosen,

719
00:42:01,381 --> 00:42:04,721
well, let's see, each one is chosen

720
00:42:04,721 --> 00:42:08,726
about half the time randomly,
picked between each one.

721
00:42:08,726 --> 00:42:11,620
Or no, let's say that
it applies this mapping

722
00:42:11,620 --> 00:42:13,940
about 90% of the time.

723
00:42:13,940 --> 00:42:16,471
So say we start with this point here,

724
00:42:16,471 --> 00:42:19,833
it'll map to this point
here and this point here

725
00:42:19,833 --> 00:42:23,231
and it will just go up and up into here

726
00:42:23,231 --> 00:42:27,561
as long as this transformation
is being applied.

727
00:42:27,561 --> 00:42:31,196
But say it does that like a hundred times

728
00:42:31,196 --> 00:42:35,042
and then one time it goes down to here.

729
00:42:35,042 --> 00:42:36,507
So say it's all the way up here

730
00:42:36,507 --> 00:42:38,605
and we map to this one,
it's gonna start here

731
00:42:38,605 --> 00:42:40,246
and it's gonna map here and here and here,

732
00:42:40,246 --> 00:42:41,301
it's gonna go up.

733
00:42:41,301 --> 00:42:44,483
And say we at this point
the computer decides

734
00:42:44,483 --> 00:42:46,872
to map to here.

735
00:42:46,872 --> 00:42:51,872
It's about 3/4 up, it's
gonna go 3/4 up here.

736
00:42:52,104 --> 00:42:55,274
So because it's random,

737
00:42:55,274 --> 00:42:57,892
if you do this just forever,

738
00:42:57,892 --> 00:43:00,538
it's gonna eventually fill
in pretty much every point

739
00:43:00,538 --> 00:43:05,190
on this line, which is very
interesting to think about.

740
00:43:05,190 --> 00:43:07,622
Any questions so far?

741
00:43:08,599 --> 00:43:11,539
So let's have this rectangle.

742
00:43:15,384 --> 00:43:16,888
All four of the transformations

743
00:43:16,888 --> 00:43:19,573
are from the outer
rectangle, this big one,

744
00:43:19,573 --> 00:43:23,828
to one of the ones inside, one
of the smaller ones inside.

745
00:43:24,879 --> 00:43:29,588
So say we have this point up here

746
00:43:29,588 --> 00:43:32,220
and we apply this
transformation to this one.

747
00:43:32,220 --> 00:43:36,106
It's gonna go to this point here.

748
00:43:36,106 --> 00:43:37,634
Makes sense?

749
00:43:37,634 --> 00:43:40,873
And if we have this one, it's
gonna go to this point here.

750
00:43:40,873 --> 00:43:45,292
So the transformation is
pretty much going like this.

751
00:43:45,292 --> 00:43:50,292
So say our IFS, iterated
function system, has these three.

752
00:43:51,365 --> 00:43:53,462
Say we go about halfway up here

753
00:43:53,462 --> 00:43:55,435
and we choose to apply this mapping.

754
00:43:55,435 --> 00:43:58,193
It's gonna go about here,
the middle of this one.

755
00:43:58,193 --> 00:44:01,436
And then we apply this
mapping like a bunch of times,

756
00:44:01,436 --> 00:44:03,672
just keep going up and up and up.

757
00:44:03,672 --> 00:44:05,534
We apply this mapping again,

758
00:44:05,534 --> 00:44:06,908
but it's sort of closer
to the top this time

759
00:44:06,908 --> 00:44:10,881
so it's gonna be out here closer to this,

760
00:44:10,881 --> 00:44:12,452
the top of this rectangle.

761
00:44:12,452 --> 00:44:14,842
And then we apply it
again and again and again

762
00:44:14,842 --> 00:44:17,279
and maybe it only goes up one.

763
00:44:17,279 --> 00:44:18,725
So it'll be down here.

764
00:44:18,725 --> 00:44:22,578
So eventually, it's gonna fill in

765
00:44:22,578 --> 00:44:26,010
this rectangle with this pattern.

766
00:44:27,415 --> 00:44:29,197
It's gonna look like this.

767
00:44:31,084 --> 00:44:32,372
Okay?

768
00:44:32,372 --> 00:44:34,949
And this, since that's,

769
00:44:34,949 --> 00:44:38,777
every point in here is
probably going to get applied

770
00:44:38,777 --> 00:44:42,568
to this mapping a bunch of
times so what we're gonna get is

771
00:44:44,718 --> 00:44:47,515
this fern structure.

772
00:44:52,778 --> 00:44:54,272
Okay.

773
00:44:54,272 --> 00:44:56,623
Isn't that really cool?

774
00:44:56,623 --> 00:44:59,598
(distant indistinct muttering)

775
00:45:09,997 --> 00:45:13,971
Are you tlaking about the
Sierpinski triangle or the fern?

776
00:45:13,971 --> 00:45:15,360
- [Male student] The fern.

777
00:45:15,360 --> 00:45:17,936
(distant indistinct muttering)

778
00:45:37,071 --> 00:45:39,180
- Right, you can't actually.

779
00:45:39,180 --> 00:45:40,590
And this is...

780
00:45:41,794 --> 00:45:43,589
Okay, I'll go through an example.

781
00:45:43,589 --> 00:45:47,358
Say we have, instead of just
applying it to one point,

782
00:45:48,700 --> 00:45:51,100
we apply it to a bunch of points.

783
00:45:51,100 --> 00:45:54,020
Say all the points on this
line, or almost all the points.

784
00:45:57,089 --> 00:46:00,344
Say we apply this
mapping a bunch of times.

785
00:46:00,344 --> 00:46:03,307
So we get this one, this
one, this one, this one.

786
00:46:07,344 --> 00:46:11,882
And say we apply this mapping
to all of these points.

787
00:46:11,882 --> 00:46:14,143
It's gonna map to here.

788
00:46:14,143 --> 00:46:16,420
And then we do that again
and again and again.

789
00:46:16,420 --> 00:46:18,609
And say, and then what we have,

790
00:46:18,609 --> 00:46:20,958
say all those points eventually

791
00:46:20,958 --> 00:46:23,546
are going to get mapped to this one.

792
00:46:23,546 --> 00:46:27,747
So you have a whole little
copy of this thing in here.

793
00:46:27,747 --> 00:46:30,481
So you have these little branches.

794
00:46:32,531 --> 00:46:34,794
And then that is gonna be mapped up here

795
00:46:34,794 --> 00:46:37,339
and then it branches, branches, branches.

796
00:46:37,339 --> 00:46:42,184
And then since you have
the smaller branches here,

797
00:46:42,184 --> 00:46:43,736
you have two levels down.

798
00:46:43,736 --> 00:46:46,948
And then this whole thing
gets mapped back onto here

799
00:46:46,948 --> 00:46:49,550
including the new branches.

800
00:46:49,550 --> 00:46:52,646
And it gets filled in as it goes on.

801
00:46:54,959 --> 00:46:59,515
But it doesn't just keep going
up to here and just like,

802
00:47:00,938 --> 00:47:03,200
say we were to apply this
mapping 100% of the time,

803
00:47:03,200 --> 00:47:05,741
it would just go up here
and go nowhere else.

804
00:47:05,741 --> 00:47:09,519
But say we apply this
mapping like 7% of the time,

805
00:47:09,519 --> 00:47:11,916
it'll go up different lengths and then

806
00:47:13,213 --> 00:47:16,587
it will map back down there
and go up, map back down.

807
00:47:16,587 --> 00:47:20,942
And then if we add this transformation,

808
00:47:20,942 --> 00:47:23,181
going from this one to this one,

809
00:47:23,181 --> 00:47:27,516
we have this and it's recursive.

810
00:47:27,516 --> 00:47:31,016
The reason why it's recursive
is because the mappings

811
00:47:31,016 --> 00:47:34,896
map onto themselves eventually.

812
00:47:34,896 --> 00:47:37,000
If we look at the code,
it's really similar

813
00:47:37,000 --> 00:47:40,885
to the Sierpinski triangle code.

814
00:47:40,885 --> 00:47:45,045
The code itself is not
recursive, but the mappings are.

815
00:47:45,045 --> 00:47:48,392
And that's what makes this
whole thing recursive.

816
00:47:52,339 --> 00:47:55,737
So yeah, let's just look
at the code a little bit.

817
00:47:55,737 --> 00:47:57,816
Class fern.

818
00:47:57,816 --> 00:48:00,864
So draw fern.

819
00:48:00,864 --> 00:48:03,562
While true, so that means execute this,

820
00:48:03,562 --> 00:48:06,136
just keep doing it over and over and over,

821
00:48:06,136 --> 00:48:10,680
pick from these list of transformations.

822
00:48:10,680 --> 00:48:13,197
So the first one says maps to the stem.

823
00:48:13,197 --> 00:48:17,050
That means it goes from
here to here, to the stem.

824
00:48:17,050 --> 00:48:19,558
The second one maps to the left branch,

825
00:48:19,558 --> 00:48:22,611
meaning it goes from here to this one.

826
00:48:22,611 --> 00:48:25,337
The third one maps to the
right branch, goes down here.

827
00:48:25,337 --> 00:48:27,867
And the fourth one maps from here to here,

828
00:48:27,867 --> 00:48:30,105
just goes up and up like that.

829
00:48:31,050 --> 00:48:34,419
And following that, just
pick from a list of functions

830
00:48:36,104 --> 00:48:38,667
and then a list of probabilities.

831
00:48:38,667 --> 00:48:41,186
It says .01, .07, .07 .85.

832
00:48:42,340 --> 00:48:45,864
So these are the probabilities at which

833
00:48:45,864 --> 00:48:48,654
these mapping functions
are gonna be chosen.

834
00:48:48,654 --> 00:48:50,819
If you choose them all equally,

835
00:48:50,819 --> 00:48:54,402
then the chances are very
low that this mapping

836
00:48:55,476 --> 00:48:58,478
is going to occur more than
like five times or something.

837
00:48:58,478 --> 00:49:00,715
So we just go up here and get map.

838
00:49:00,715 --> 00:49:03,280
So it'd be a very sparse fractal.

839
00:49:03,280 --> 00:49:06,485
Most of the points
would be like down here.

840
00:49:06,485 --> 00:49:08,120
It just didn't look very good, I tried it.

841
00:49:08,120 --> 00:49:11,519
I wish I could like code it and show you.

842
00:49:12,949 --> 00:49:16,156
So the .01 means that
the mapping to the stem

843
00:49:16,156 --> 00:49:18,680
happens 1% of the time.

844
00:49:18,680 --> 00:49:20,243
The mapping to each of the branches

845
00:49:20,243 --> 00:49:21,719
happens 7% of the time.

846
00:49:21,719 --> 00:49:23,769
And the mapping up and spiraling

847
00:49:23,769 --> 00:49:26,321
happens 85% of the time.

848
00:49:28,939 --> 00:49:32,220
So I'm gonna take a
break now for 10 minutes.

849
00:49:33,573 --> 00:49:35,811
Anybody have any questions?

850
00:49:38,233 --> 00:49:40,268
So I guess we'll start up again.

851
00:49:43,003 --> 00:49:45,804
Before we leave these
iterated function system,

852
00:49:45,804 --> 00:49:48,748
I wanna point out how
the Sierpinski triangles

853
00:49:49,635 --> 00:49:52,758
is pretty much the same thing as the ferns

854
00:49:52,758 --> 00:49:54,924
in terms of mappings.

855
00:50:05,870 --> 00:50:09,515
With a Sierpinski triangle,
we have these three mappings.

856
00:50:09,515 --> 00:50:13,156
One of them maps from this triangle

857
00:50:13,156 --> 00:50:16,462
to this triangle here.

858
00:50:18,673 --> 00:50:21,442
One of them maps from the
big triangle to this triangle

859
00:50:21,442 --> 00:50:25,126
and the other one maps from
this triangle to this triangle.

860
00:50:25,126 --> 00:50:29,254
And each one of them are
applied with equal probability.

861
00:50:29,254 --> 00:50:32,644
So if you think about it, going half way

862
00:50:32,644 --> 00:50:35,651
from any of these points
to one of the other points

863
00:50:35,651 --> 00:50:39,222
is essentially mapping it down.

864
00:50:39,222 --> 00:50:42,492
So say you have this one, this line,

865
00:50:43,603 --> 00:50:46,989
you apply the function
to all these points.

866
00:50:46,989 --> 00:50:50,517
What it does is maps it
down to that triangle.

867
00:50:52,692 --> 00:50:55,659
So you can see these triangles

868
00:50:55,659 --> 00:50:58,957
map onto themselves recursively,

869
00:51:00,217 --> 00:51:02,510
and that's why it actually is,

870
00:51:02,510 --> 00:51:04,317
there is a recursion going on here

871
00:51:04,317 --> 00:51:05,722
but it's not in the code itself.

872
00:51:05,722 --> 00:51:07,526
The code itself is just repetitive,

873
00:51:07,526 --> 00:51:08,963
but what it's repeating

874
00:51:08,963 --> 00:51:12,531
is these recursive
mappings onto themselves.

875
00:51:12,531 --> 00:51:14,554
Yeah?
(distant indistinct muttering)

876
00:51:16,987 --> 00:51:21,754
There's always more than one
way to represent an algorithm.

877
00:51:21,754 --> 00:51:23,881
Yeah, it's really fascinating,

878
00:51:23,881 --> 00:51:26,361
especially with these fractals and things.

879
00:51:26,361 --> 00:51:30,397
It seems like there's
always another way to do it,

880
00:51:30,397 --> 00:51:32,113
to achieve the same result.

881
00:51:32,113 --> 00:51:34,801
And that's one thing,
especially Sierpinski triangle,

882
00:51:34,801 --> 00:51:36,582
it's really amazing.

883
00:51:36,582 --> 00:51:39,324
(distant indistinct muttering)

884
00:51:52,947 --> 00:51:55,107
Ah, so how can you figure out

885
00:51:55,107 --> 00:51:57,283
if the output is gonna be recursive

886
00:51:57,283 --> 00:51:59,029
without running the code?

887
00:51:59,029 --> 00:52:02,292
(distant indistinct muttering)

888
00:52:02,292 --> 00:52:04,753
Right.
(distant indistinct muttering)

889
00:52:11,958 --> 00:52:15,938
So he said since the code
itself is not recursive,

890
00:52:16,785 --> 00:52:19,830
how do you know that the
output is gonna be recursive?

891
00:52:19,830 --> 00:52:21,567
(distant indistinct muttering)

892
00:52:21,567 --> 00:52:24,337
Even without any recursive functions.

893
00:52:24,337 --> 00:52:26,942
Right, I mean the thing is

894
00:52:26,942 --> 00:52:29,278
when you write the code,
if you realize that

895
00:52:29,278 --> 00:52:32,034
what the code is doing is mapping

896
00:52:32,034 --> 00:52:35,694
these two dimensional mappings,

897
00:52:35,694 --> 00:52:39,205
you could sort of think
in your head, okay,

898
00:52:39,205 --> 00:52:43,206
these mappings are gonna be
applied with equal probability.

899
00:52:48,179 --> 00:52:52,301
So just by mentally
extrapolating in your head,

900
00:52:52,301 --> 00:52:54,749
so you're sort of stepping
out of the system,

901
00:52:54,749 --> 00:52:57,046
you're saying okay, what's
the thing actually doing?

902
00:52:57,046 --> 00:53:00,268
(distant indistinct muttering)

903
00:53:02,265 --> 00:53:03,618
While you're in the system?

904
00:53:03,618 --> 00:53:05,351
Well, being in the system in this case

905
00:53:05,351 --> 00:53:07,953
is actually running
the code and like being

906
00:53:07,953 --> 00:53:11,052
a computer program running it.

907
00:53:11,052 --> 00:53:14,051
Stepping out of the system,
what I mean by that,

908
00:53:14,051 --> 00:53:16,909
is like taking a higher level
view of what's going on.

909
00:53:16,909 --> 00:53:19,826
(distant indistinct muttering)

910
00:53:24,606 --> 00:53:27,562
Yeah, exactly, exactly.

911
00:53:27,562 --> 00:53:29,341
Yes, that's it.

912
00:53:29,341 --> 00:53:32,814
So he said when you abstract
away from all the details

913
00:53:32,814 --> 00:53:35,809
of what's going on with
the actual functions,

914
00:53:35,809 --> 00:53:39,682
you begin to perceive
this higher level thing

915
00:53:39,682 --> 00:53:43,229
which is itself recursion, yeah,

916
00:53:43,229 --> 00:53:45,099
and has recursion in it.

917
00:53:45,099 --> 00:53:49,269
So if you abstract your thought process

918
00:53:49,269 --> 00:53:52,851
significantly enough, you'll
be able to logically tell

919
00:53:52,851 --> 00:53:57,244
that it's going to create
this recursive shape, yeah.

920
00:53:57,244 --> 00:53:59,736
(distant indistinct muttering)

921
00:54:03,833 --> 00:54:05,861
Yeah, so you mean like a test?

922
00:54:05,861 --> 00:54:10,113
No, you have to think about
it, that's what humans can do.

923
00:54:10,113 --> 00:54:13,722
Like, there's no strict
test that could be applied

924
00:54:13,722 --> 00:54:16,223
to some computer program
that would tell you

925
00:54:16,223 --> 00:54:19,115
whether or not it's going
to create a recursive result

926
00:54:19,115 --> 00:54:21,207
because in this case, there's
no recursive function.

927
00:54:21,207 --> 00:54:24,212
So the computer can't
know like okay, hmmm oh,

928
00:54:24,212 --> 00:54:26,672
can I abstract them to, you know?

929
00:54:26,672 --> 00:54:30,271
Only humans can do that, yeah, so far.

930
00:54:30,271 --> 00:54:34,068
And it's not coded up
as a system of mappings,

931
00:54:34,068 --> 00:54:36,358
it's just these simple functions.

932
00:54:36,358 --> 00:54:37,786
I don't know.

933
00:54:39,259 --> 00:54:41,187
So yeah.

934
00:54:41,187 --> 00:54:43,493
It's really cool.

935
00:54:43,493 --> 00:54:45,603
So yeah, if you just think about mapping,

936
00:54:45,603 --> 00:54:47,611
mapping, mapping and you map it over here,

937
00:54:47,611 --> 00:54:49,905
all the stuff that was in
here that goes infinitely down

938
00:54:49,905 --> 00:54:54,282
is now like, like this little subsection

939
00:54:55,635 --> 00:54:59,779
of this little triangle,
and you just, yeah.

940
00:54:59,779 --> 00:55:01,693
It's a recursive structure.

941
00:55:01,693 --> 00:55:03,431
So let's go on to the next example,

942
00:55:03,431 --> 00:55:06,507
which is very interesting,
the Mandelbrot set.

943
00:55:07,694 --> 00:55:10,020
First, now that we have
this up and running,

944
00:55:10,020 --> 00:55:14,652
I just wanna run the programs
that are in the handout

945
00:55:14,652 --> 00:55:18,087
to give you a sense of what's going on.

946
00:55:18,087 --> 00:55:21,549
So the recursive transition
network, let's run it

947
00:55:21,549 --> 00:55:23,432
and see what happens.

948
00:55:23,432 --> 00:55:25,370
It's gonna generate a hundred sentences

949
00:55:25,370 --> 00:55:28,049
because if you look at the code,

950
00:55:28,049 --> 00:55:32,600
there's a print statement
that goes a hundred times.

951
00:55:35,841 --> 00:55:37,179
Yeah, page five.

952
00:55:37,179 --> 00:55:42,179
Zero to 100 .each, print line,
call the function fancy noun.

953
00:55:43,290 --> 00:55:45,218
So this is just fancy notation

954
00:55:45,218 --> 00:55:47,976
in the groovy programming
language to just, oh crap.

955
00:55:47,976 --> 00:55:49,897
It's not working.

956
00:55:51,547 --> 00:55:54,823
Oh well, I'll just try to get
this to work as I'm talking.

957
00:55:56,509 --> 00:55:58,754
I can't do the examples.

958
00:56:03,692 --> 00:56:07,701
Yeah, I've been having problems
with this thing all day.

959
00:56:07,701 --> 00:56:09,412
So the next example and the last example

960
00:56:09,412 --> 00:56:11,465
is the Mandelbrot set.

961
00:56:14,066 --> 00:56:16,891
You guys probably have heard
about the Mandelbrot set.

962
00:56:16,891 --> 00:56:18,517
It's very famous, probably one of the most

963
00:56:18,517 --> 00:56:20,902
famous fractals of all.

964
00:56:24,738 --> 00:56:28,197
It's called Mandelbrot
because this guy, Mandelbrot,

965
00:56:28,197 --> 00:56:30,673
really loved fractals
and tried to communicate

966
00:56:30,673 --> 00:56:33,432
the notion of fractals to the world

967
00:56:33,432 --> 00:56:37,389
and this is really a great fractal.

968
00:56:37,389 --> 00:56:41,104
So it'll get a little bit
mathy but that's okay.

969
00:56:43,204 --> 00:56:46,472
So we'll have, it's in the complex plane.

970
00:56:46,472 --> 00:56:49,258
So that means that we have this plane

971
00:56:49,258 --> 00:56:51,486
where these are the real numbers

972
00:56:51,486 --> 00:56:54,172
and these are the imaginary numbers.

973
00:56:54,172 --> 00:56:57,778
I think this is the way it goes.

974
00:56:57,778 --> 00:57:02,041
So the Mandelbrot set is
defined by the function

975
00:57:04,653 --> 00:57:08,407
z equals z squared plus c.

976
00:57:10,647 --> 00:57:14,873
And when you square a complex number,

977
00:57:14,873 --> 00:57:16,848
well first of all, first of all,

978
00:57:16,848 --> 00:57:18,931
a complex number is a point in this plane.

979
00:57:18,931 --> 00:57:21,607
So say this point is,

980
00:57:24,640 --> 00:57:28,726
this is b say and this is a.

981
00:57:28,726 --> 00:57:32,159
This point is represented by a plus b, i,

982
00:57:35,437 --> 00:57:38,220
and i is the square root of negative one,

983
00:57:38,220 --> 00:57:40,686
which is not really possible,

984
00:57:40,686 --> 00:57:44,373
that's why it's called imaginary.

985
00:57:44,373 --> 00:57:48,750
So if you multiply two
complex numbers together,

986
00:57:59,830 --> 00:58:03,273
it's not really that simple.

987
00:58:03,273 --> 00:58:06,533
You have to do like the
actual multiplication out.

988
00:58:06,533 --> 00:58:09,831
What you get is ac plus you know.

989
00:58:15,176 --> 00:58:17,362
I don't know if I should do it all out.

990
00:58:17,362 --> 00:58:20,077
It'll take a little bit of time.

991
00:58:20,927 --> 00:58:24,736
But you get this sort of a
mapping function essentially

992
00:58:24,736 --> 00:58:27,569
that's not really linear.

993
00:58:27,569 --> 00:58:30,937
It's not really that
predictable what it's gonna do.

994
00:58:30,937 --> 00:58:33,657
So you have this this point here and

995
00:58:36,528 --> 00:58:39,028
okay, so the way the algorithm works,

996
00:58:39,028 --> 00:58:42,501
you take a point on the complex plane.

997
00:58:42,501 --> 00:58:45,781
C gets the value of that point and then z

998
00:58:45,781 --> 00:58:47,922
starts off at zero, just zero, zero.

999
00:58:47,922 --> 00:58:51,192
And you apply this
function a bunch of times.

1000
00:58:53,506 --> 00:58:56,599
So say we apply this function once.

1001
00:58:56,599 --> 00:58:58,891
Z equals z squared plus c.

1002
00:58:58,891 --> 00:59:01,370
So zero squared is nothing plus c.

1003
00:59:01,370 --> 00:59:04,228
So the first iteration,
z gets the value c.

1004
00:59:04,228 --> 00:59:06,374
So z is gonna be there.

1005
00:59:06,374 --> 00:59:09,408
And you apply the function again

1006
00:59:09,408 --> 00:59:13,383
and this c is now the
new z that we just got.

1007
00:59:14,293 --> 00:59:17,163
So z equals z squared plus c.

1008
00:59:17,163 --> 00:59:20,990
So z squared, you apply
the squaring function,

1009
00:59:23,588 --> 00:59:26,090
and you add c, you add the real

1010
00:59:26,090 --> 00:59:28,235
and imaginary components of c.

1011
00:59:28,235 --> 00:59:31,973
So it just maps this
point to some other point

1012
00:59:31,973 --> 00:59:35,000
over here say.

1013
00:59:35,000 --> 00:59:38,555
And then you apply this again
and again and again and again.

1014
00:59:38,555 --> 00:59:41,815
So apply it here and you're here.

1015
00:59:41,815 --> 00:59:44,356
So I don't know if I'm
going too fast but like

1016
00:59:44,356 --> 00:59:47,741
we get this point after
applying the function to this.

1017
00:59:47,741 --> 00:59:50,122
So now this is the new z.

1018
00:59:50,122 --> 00:59:52,637
And then the new z loops back around

1019
00:59:52,637 --> 00:59:54,954
and so we apply it.

1020
00:59:54,954 --> 00:59:58,239
Now z squared plus c, c is always gonna be

1021
00:59:58,239 --> 01:00:01,846
the initial point but z will be changing.

1022
01:00:01,846 --> 01:00:04,636
And it maps to here for example.

1023
01:00:04,636 --> 01:00:08,882
And now the new point is z
equals z squared plus c again

1024
01:00:10,704 --> 01:00:14,014
that maps over here.

1025
01:00:14,014 --> 01:00:17,430
So I wrote a little applet

1026
01:00:19,541 --> 01:00:21,571
that demonstrates this mapping

1027
01:00:21,571 --> 01:00:22,877
and what it actually looks like.

1028
01:00:22,877 --> 01:00:23,634
Yeah?

1029
01:00:23,634 --> 01:00:25,864
- [Male student] Z can
be anywhere in the plane?

1030
01:00:25,864 --> 01:00:27,835
- Z can be anywhere?
(crosstalk)

1031
01:00:27,835 --> 01:00:31,595
The starting point
could be anywhere, yeah.

1032
01:00:31,595 --> 01:00:34,758
But when you actually run the algorithm,

1033
01:00:34,758 --> 01:00:38,275
you only go from negative two to two.

1034
01:00:40,167 --> 01:00:42,149
Negative two, two,

1035
01:00:43,466 --> 01:00:45,457
because that's the only region

1036
01:00:45,457 --> 01:00:48,151
in which interesting things
happen with this fractal.

1037
01:00:48,151 --> 01:00:52,339
So I didn't finish
explaining the algorithm.

1038
01:00:52,339 --> 01:00:54,523
So say a point in here,
a point that's very close

1039
01:00:54,523 --> 01:00:56,907
to the origin, zero, zero,

1040
01:00:56,907 --> 01:01:00,480
what it tends to do is spiral inward

1041
01:01:00,480 --> 01:01:02,395
as you iterate it.

1042
01:01:02,395 --> 01:01:04,653
But a point out here,
what it tends to do...

1043
01:01:05,975 --> 01:01:08,898
Oh definitely a point outside of two.

1044
01:01:08,898 --> 01:01:11,594
What it tends to do when
you apply this function

1045
01:01:11,594 --> 01:01:13,095
is to get mapped out here

1046
01:01:13,095 --> 01:01:14,706
and then to get mapped like over there

1047
01:01:14,706 --> 01:01:17,471
and just go like really far away.

1048
01:01:17,471 --> 01:01:22,471
So what we do to render the Mandelbrot set

1049
01:01:22,538 --> 01:01:26,117
is apply the function a number of times.

1050
01:01:29,038 --> 01:01:34,038
And if the point eventually
goes outside this circle

1051
01:01:35,589 --> 01:01:39,219
at the origin of radius two,
sorry it's a bad circle,

1052
01:01:39,219 --> 01:01:42,514
if the point eventually
goes outside of the circle,

1053
01:01:42,514 --> 01:01:44,851
we stop performing the
function because we know

1054
01:01:44,851 --> 01:01:46,535
that after it gets outside,

1055
01:01:46,535 --> 01:01:48,413
it's gonna keep going forever out.

1056
01:01:48,413 --> 01:01:51,102
It has escaped.

1057
01:01:51,102 --> 01:01:53,407
It's called the escape iterations,

1058
01:01:53,407 --> 01:01:55,202
the number of iterations it takes

1059
01:01:55,202 --> 01:01:58,821
to escape outside of the circle,
so the escape iterations.

1060
01:01:58,821 --> 01:02:03,165
So what we do is we color the point

1061
01:02:03,165 --> 01:02:06,042
depending on its escape iteration.

1062
01:02:06,042 --> 01:02:08,511
So when we actually, and
the other part of it is

1063
01:02:08,511 --> 01:02:10,934
if it never escapes, we color it black.

1064
01:02:10,934 --> 01:02:12,848
To actually test that, we just iterate

1065
01:02:12,848 --> 01:02:16,306
a certain number of
times, say like 500 times

1066
01:02:16,306 --> 01:02:18,376
or like 70 times.

1067
01:02:18,376 --> 01:02:21,148
And if it hasn't escaped
after that many iterations,

1068
01:02:21,148 --> 01:02:23,026
we sort of assume that
it's never going to.

1069
01:02:23,026 --> 01:02:26,230
It's not valid, so it's an
approximation to the actual set

1070
01:02:26,230 --> 01:02:29,910
but we have to do it to
render the actual thing.

1071
01:02:29,910 --> 01:02:31,550
Then we color black.

1072
01:02:31,550 --> 01:02:33,861
So when we actually render
it, what we do is go through

1073
01:02:33,861 --> 01:02:37,457
each pixel on the screen
and apply this algorithm.

1074
01:02:38,416 --> 01:02:40,393
So for this point, this point becomes c

1075
01:02:40,393 --> 01:02:44,341
and we iterate, test,
iterate, test, iterate, test,

1076
01:02:44,341 --> 01:02:48,095
and it's a test and what we're testing

1077
01:02:48,095 --> 01:02:49,804
is if it's outside of the circle.

1078
01:02:49,804 --> 01:02:52,357
If it's outside of the
circle, we assign it a color

1079
01:02:52,357 --> 01:02:54,781
based on the number of iterations it took.

1080
01:02:54,781 --> 01:02:57,988
And we do that for each one.

1081
01:02:57,988 --> 01:03:00,729
So we keep going and
say this one for example

1082
01:03:00,729 --> 01:03:03,185
is gonna spiral in.

1083
01:03:03,185 --> 01:03:06,374
It's not a continuous line,
it just applies the function

1084
01:03:06,374 --> 01:03:08,384
and spirals in.

1085
01:03:09,669 --> 01:03:11,530
So that's never going to escape

1086
01:03:11,530 --> 01:03:13,640
so we're gonna color it black.

1087
01:03:13,640 --> 01:03:18,091
And this applet is
excellent in showing this.

1088
01:03:21,728 --> 01:03:26,368
So I implemented this algorithm in Java

1089
01:03:26,368 --> 01:03:29,735
and it's gonna output the point

1090
01:03:33,382 --> 01:03:37,345
and it's gonna draw the
lines between each point.

1091
01:03:38,192 --> 01:03:40,720
So say it starts here, it's
gonna draw a line here,

1092
01:03:40,720 --> 01:03:42,757
here, here, here.

1093
01:03:42,757 --> 01:03:44,842
So what we're gonna see is really cool.

1094
01:03:44,842 --> 01:03:47,959
So this is what we get in the end.

1095
01:03:47,959 --> 01:03:52,045
And as I move my mouse
around, it does these tests.

1096
01:03:52,045 --> 01:03:55,672
So here we can see that
there's only one iteration,

1097
01:03:55,672 --> 01:03:59,310
the one iteration gets
the color light blue.

1098
01:03:59,310 --> 01:04:01,689
And then here, there are two iterations

1099
01:04:01,689 --> 01:04:04,176
and they're listed up there, one, two.

1100
01:04:04,176 --> 01:04:07,506
So you can see all the way,
wherever it's this color,

1101
01:04:07,506 --> 01:04:11,180
there are only two iterations
before the point gets outside

1102
01:04:11,180 --> 01:04:13,113
of this circle.

1103
01:04:13,113 --> 01:04:15,643
Two, two, two I think.

1104
01:04:17,482 --> 01:04:21,038
So as we go deeper in and
it takes three iterations,

1105
01:04:21,038 --> 01:04:24,096
four or five, six, a lot of iterations.

1106
01:04:24,096 --> 01:04:27,355
So all the points that are colored

1107
01:04:27,355 --> 01:04:29,972
they do eventually escape.

1108
01:04:29,972 --> 01:04:32,601
But all the points that
are black don't escape.

1109
01:04:32,601 --> 01:04:35,506
And so the patterns that are
inside are really interesting.

1110
01:04:35,506 --> 01:04:38,787
See these in the middle,
they just sort of spiral

1111
01:04:38,787 --> 01:04:40,829
and keep going.

1112
01:04:40,829 --> 01:04:43,980
The ones here, there's
some looping pattern.

1113
01:04:43,980 --> 01:04:47,719
See, the function loops back on itself.

1114
01:04:47,719 --> 01:04:49,119
So it's sort of recursive,

1115
01:04:49,119 --> 01:04:52,287
like I don't really understand
how its recursive but

1116
01:04:52,287 --> 01:04:53,871
it sort of is.

1117
01:04:53,871 --> 01:04:55,762
So if we go out to this other nub,

1118
01:04:55,762 --> 01:04:59,005
the second nub out, it gets
this, it's really cool shape.

1119
01:05:00,276 --> 01:05:04,121
So what we could do is
zoom in actually on this.

1120
01:05:04,121 --> 01:05:06,151
It redraws it.

1121
01:05:06,151 --> 01:05:08,592
So it's calculating this
algorithm for every single point

1122
01:05:08,592 --> 01:05:10,984
as we speak, it's getting really fast.

1123
01:05:13,701 --> 01:05:17,912
So we can see all these really cool shapes

1124
01:05:17,912 --> 01:05:20,245
that generate this fractal.

1125
01:05:22,242 --> 01:05:24,847
And it's just crazy.

1126
01:05:31,435 --> 01:05:34,331
So we can sort of see recursion here.

1127
01:05:34,331 --> 01:05:36,318
Like it looks like there's definitely some

1128
01:05:36,318 --> 01:05:38,644
recursive thing going on,

1129
01:05:38,644 --> 01:05:41,258
and the recursive part
of this is the fact that

1130
01:05:43,463 --> 01:05:45,617
z gets applied to itself.

1131
01:05:48,388 --> 01:05:52,263
The nth z is equal to
the z that came before it

1132
01:05:54,196 --> 01:05:56,112
squared plus c.

1133
01:05:56,112 --> 01:05:59,326
And then this z is reframed as the old z,

1134
01:05:59,326 --> 01:06:02,319
and this reframing and
reapplying of the function

1135
01:06:02,319 --> 01:06:05,033
is what makes it recursive.

1136
01:06:05,033 --> 01:06:09,682
Yeah, it sort of makes sense.

1137
01:06:10,598 --> 01:06:13,339
Let's just go through the code quickly

1138
01:06:13,339 --> 01:06:15,490
and then I want to

1139
01:06:16,578 --> 01:06:19,761
show some really cool things.

1140
01:06:20,834 --> 01:06:22,816
Oh, where did it go?

1141
01:06:22,816 --> 01:06:25,397
(distant indistinct muttering)

1142
01:06:25,397 --> 01:06:28,802
So yeah, in the black part
it just recurses infinitely.

1143
01:06:28,802 --> 01:06:30,854
And the code itself is not recursive,

1144
01:06:30,854 --> 01:06:34,372
but the mapping function,
again, it's what's recursive.

1145
01:06:34,372 --> 01:06:38,996
So yeah, the black parts are in the set.

1146
01:06:40,740 --> 01:06:42,939
So the real actual Mandelbrot set

1147
01:06:42,939 --> 01:06:44,719
is just the black points.

1148
01:06:44,719 --> 01:06:47,961
We just color the other
point so it looks pretty.

1149
01:06:47,961 --> 01:06:50,916
So let's look at the code.

1150
01:06:50,916 --> 01:06:52,687
Def draw Mandelbrot.

1151
01:06:52,687 --> 01:06:54,848
See that there?

1152
01:06:57,625 --> 01:06:59,561
Window .set negative two, two.

1153
01:06:59,561 --> 01:07:01,907
So it just sets the
window, the plotting range

1154
01:07:01,907 --> 01:07:03,824
to be in this range.

1155
01:07:03,824 --> 01:07:08,247
For every x pixel in
the height of the window

1156
01:07:08,247 --> 01:07:09,874
or the width of the window,

1157
01:07:09,874 --> 01:07:11,680
and every y pixel in the height,

1158
01:07:11,680 --> 01:07:15,114
c .real and c .imaginary
get the x and y values

1159
01:07:15,114 --> 01:07:17,446
on the screen.

1160
01:07:17,446 --> 01:07:20,682
So what we're doing there is saying

1161
01:07:20,682 --> 01:07:25,524
basically the pixel gets this
actual point in the space

1162
01:07:25,524 --> 01:07:28,713
that we're working, the complex plane.

1163
01:07:28,713 --> 01:07:32,553
Def iterations equals
calculate iterations c.

1164
01:07:32,553 --> 01:07:36,298
And we pass it c, keep in mind this is c.

1165
01:07:36,298 --> 01:07:38,548
The starting point is c.

1166
01:07:38,548 --> 01:07:42,891
So let's just stay inside
this function for now.

1167
01:07:42,891 --> 01:07:46,314
Def color equals calculate
color iterations.

1168
01:07:46,314 --> 01:07:48,456
So we're calculating the color

1169
01:07:48,456 --> 01:07:51,316
based on the number of
iterations it took to escape.

1170
01:07:51,316 --> 01:07:54,427
And then fill the pixel with the color.

1171
01:07:54,427 --> 01:07:56,761
That plots it on the screen.

1172
01:07:56,761 --> 01:07:59,336
So let's look at the
calculate iterations function,

1173
01:07:59,336 --> 01:08:01,637
int calculated iterations.

1174
01:08:01,637 --> 01:08:05,167
This notation means that it
will return an integer number.

1175
01:08:05,167 --> 01:08:07,062
It takes a complex number c.

1176
01:08:07,062 --> 01:08:10,299
So z real z imaginary
start at zero, start there.

1177
01:08:10,299 --> 01:08:13,582
And then iteration starts off at zero.

1178
01:08:15,500 --> 01:08:19,814
So this is, we're gonna count
how many iterations it takes.

1179
01:08:19,814 --> 01:08:22,240
So while the circled contains z,

1180
01:08:22,240 --> 01:08:26,248
that's another function that
just tests if it's inside,

1181
01:08:26,248 --> 01:08:29,830
and the number of iterations
is less than max iterations,

1182
01:08:31,165 --> 01:08:34,077
max iterations is the number of iterations

1183
01:08:34,077 --> 01:08:37,357
after which we assume is
it's just gonna spiral inward

1184
01:08:37,357 --> 01:08:40,254
and just stay inside.

1185
01:08:40,254 --> 01:08:44,682
So while that stuff is true,
z equals z squared plus c.

1186
01:08:44,682 --> 01:08:47,836
Z equals z times z plus
c, which is the squared.

1187
01:08:49,066 --> 01:08:53,576
So we can do that because
I overloaded the operators,

1188
01:08:53,576 --> 01:08:57,440
the multiplication and
addition, for a complex number.

1189
01:08:57,440 --> 01:08:59,359
So it behaves correctly,

1190
01:08:59,359 --> 01:09:02,508
it does this strange multiplication thing.

1191
01:09:03,584 --> 01:09:06,604
And so we do that, iterations plus, plus.

1192
01:09:06,604 --> 01:09:10,337
That means we increment the
number of iterations by one.

1193
01:09:10,337 --> 01:09:13,408
And calculate color just,

1194
01:09:13,408 --> 01:09:16,615
it calculates a color based
on number of iterations.

1195
01:09:18,711 --> 01:09:20,255
So we have 20 minutes left,

1196
01:09:20,255 --> 01:09:23,660
I want to blow you away

1197
01:09:23,660 --> 01:09:26,162
with music and fractals.

1198
01:09:29,464 --> 01:09:33,311
So I'm gonna play a piece,
three pieces of Bach.

1199
01:09:33,311 --> 01:09:35,795
And yeah, this is great.

1200
01:09:36,855 --> 01:09:40,373
So the first one, it's
actually not written by Bach.

1201
01:09:40,373 --> 01:09:42,590
Oh no, what's going on here?

1202
01:09:46,488 --> 01:09:47,670
It's not written by Bach,

1203
01:09:47,670 --> 01:09:49,728
but it's the Little Harmonic Labyrinth,

1204
01:09:49,728 --> 01:09:53,728
which is the song that
the dialogue is based on

1205
01:09:55,204 --> 01:09:58,282
in Godel, Escher, Bach.

1206
01:09:58,282 --> 01:10:01,800
English language has a grammar.

1207
01:10:01,800 --> 01:10:05,392
We could nest sentences
inside which we can nest

1208
01:10:05,392 --> 01:10:08,864
more sentences in which we
could nest more sentences.

1209
01:10:08,864 --> 01:10:10,663
And that itself was a nested sentence.

1210
01:10:10,663 --> 01:10:12,748
So music, sort of like English,

1211
01:10:12,748 --> 01:10:16,314
has sort of a grammar to it.

1212
01:10:16,314 --> 01:10:19,660
These chord progressions
and melodies and harmonies

1213
01:10:19,660 --> 01:10:23,444
particularly have a sort of a language

1214
01:10:23,444 --> 01:10:26,877
in which they can move
between keys and whatnot.

1215
01:10:26,877 --> 01:10:31,087
And so that's one way in
which Bach embeds recursion

1216
01:10:33,631 --> 01:10:35,089
inside of music.

1217
01:10:35,089 --> 01:10:38,536
He has these nested harmonic structures

1218
01:10:38,536 --> 01:10:40,059
of chord progressions.

1219
01:10:40,059 --> 01:10:44,437
In Chapter five of Godel,
Escher, Bach, he talks about it.

1220
01:10:44,437 --> 01:10:47,132
And the dialogue is modeled after

1221
01:10:49,312 --> 01:10:52,686
that first song that we heard,
Little Harmonic Labyrinth.

1222
01:10:52,686 --> 01:10:55,497
And melodies also can
sort of have recursion

1223
01:10:55,497 --> 01:10:57,716
in that they can have patterns.

1224
01:10:57,716 --> 01:11:01,113
Like this theme for example,

1225
01:11:01,113 --> 01:11:04,680
this theme, like Bach does this a lot,

1226
01:11:06,758 --> 01:11:09,996
what he does is he takes
themes and he restates them

1227
01:11:09,996 --> 01:11:12,381
with maybe different harmonies

1228
01:11:12,381 --> 01:11:17,110
and embeds them inside
smaller and larger scales.

1229
01:11:18,351 --> 01:11:20,973
So for example, I don't
know if he did this,

1230
01:11:20,973 --> 01:11:24,210
like maybe on a larger scale,

1231
01:11:24,210 --> 01:11:27,290
the actual harmony might actually follow

1232
01:11:27,290 --> 01:11:30,765
this sort of theme.

1233
01:11:30,765 --> 01:11:34,171
And inside those, like
for a long period of time

1234
01:11:34,171 --> 01:11:36,887
be this key, and a long
period of time, be this key.

1235
01:11:36,887 --> 01:11:41,671
And then when you're in that
key, he plays this theme.

1236
01:11:41,671 --> 01:11:43,673
So that's an example of nesting.

1237
01:11:43,673 --> 01:11:47,546
So recursion per se is not there,

1238
01:11:47,546 --> 01:11:50,339
but the result of recursion,

1239
01:11:50,339 --> 01:11:52,866
this is the distinction
between recursive processes

1240
01:11:52,866 --> 01:11:54,762
and recursive structures.

1241
01:11:54,762 --> 01:11:56,923
Recursive structures are
basically any structure

1242
01:11:56,923 --> 01:11:58,560
that has nesting to it.

1243
01:11:58,560 --> 01:12:00,552
So English languages is
a recursive structure

1244
01:12:00,552 --> 01:12:03,769
because it comes from a
recursive grammar, it's nesting.

1245
01:12:03,769 --> 01:12:07,763
And music also, it's
a recursive structure,

1246
01:12:07,763 --> 01:12:09,996
not a recursive process.

1247
01:12:09,996 --> 01:12:12,782
(distant indistinct muttering)

1248
01:12:16,724 --> 01:12:18,048
Exactly, that's it.

1249
01:12:18,048 --> 01:12:21,001
He says so a recursive process is

1250
01:12:21,001 --> 01:12:23,416
sort of like a function
or something that defines

1251
01:12:23,416 --> 01:12:26,300
how you end up with a recursive structure.

1252
01:12:26,300 --> 01:12:28,259
That's exactly it, yeah.

1253
01:12:28,259 --> 01:12:30,712
(distant indistinct muttering)

1254
01:12:43,998 --> 01:12:46,695
Yeah, it's hard to hear.

1255
01:12:46,695 --> 01:12:50,324
It takes a really fine
musical ear to hear this.

1256
01:12:54,058 --> 01:12:56,128
Let's see, how much time?

1257
01:12:56,128 --> 01:12:58,063
Three minutes.

1258
01:12:58,063 --> 01:13:02,333
So we talked about pushing
and popping of stacks.

1259
01:13:05,496 --> 01:13:08,373
So a function, a computer function,

1260
01:13:08,373 --> 01:13:10,433
say f, Foo actually.

1261
01:13:14,827 --> 01:13:17,256
Foo is a function.

1262
01:13:17,256 --> 01:13:21,608
Or better yet, well no (mumbles).

1263
01:13:21,608 --> 01:13:25,844
and inside this Foo, it
calls the function bar.

1264
01:13:28,821 --> 01:13:31,692
And here's a function bar.

1265
01:13:34,223 --> 01:13:36,956
It does some stuff and it calls maybe g.

1266
01:13:39,056 --> 01:13:41,878
And does some other stuff, here's g.

1267
01:13:44,699 --> 01:13:48,610
G maybe does just one thing
and I don't know, ends.

1268
01:13:48,610 --> 01:13:52,596
So what you have is a stack, a call stack.

1269
01:13:52,596 --> 01:13:57,056
Like it happens in any grammar actually

1270
01:13:57,056 --> 01:13:59,343
that's sort of recursive.

1271
01:13:59,343 --> 01:14:01,565
So in computer programs
and also in English,

1272
01:14:01,565 --> 01:14:03,174
you have this notion of a stack.

1273
01:14:03,174 --> 01:14:05,817
So here, you do some
stuff, you do some stuff.

1274
01:14:05,817 --> 01:14:09,529
And then when you call bar,
your focus actually changes

1275
01:14:10,826 --> 01:14:13,013
to over here, bar.

1276
01:14:13,013 --> 01:14:15,973
But you retain, sort of in your mind

1277
01:14:15,973 --> 01:14:19,410
or in the memory of the
computer, where you were,

1278
01:14:19,410 --> 01:14:20,920
where you left from.

1279
01:14:20,920 --> 01:14:23,593
So yeah?
(distant indistinct muttering)

1280
01:14:29,795 --> 01:14:31,997
Goals, yeah exactly.

1281
01:14:31,997 --> 01:14:35,320
So that's why computer
programming is tough

1282
01:14:35,320 --> 01:14:37,044
because like you have a high level goal

1283
01:14:37,044 --> 01:14:38,943
but then to get to that
goal, just like you said,

1284
01:14:38,943 --> 01:14:40,527
you have other goals that you need to meet

1285
01:14:40,527 --> 01:14:42,785
and each of those goals
require some other goals.

1286
01:14:42,785 --> 01:14:44,590
So it's actually recursive.

1287
01:14:44,590 --> 01:14:46,389
Like it's crazy.

1288
01:14:48,180 --> 01:14:51,589
So when this program
executes, it does this stuff,

1289
01:14:51,589 --> 01:14:55,637
it puts this position a,
let's say, on the stack.

1290
01:14:55,637 --> 01:14:58,514
So this is a stack, a.

1291
01:14:58,514 --> 01:15:00,919
And then it goes into here
bar, blah, blah, blah,

1292
01:15:00,919 --> 01:15:02,459
does all this stuff and it calls g.

1293
01:15:02,459 --> 01:15:05,133
But to remember where this is,
let's call this position b,

1294
01:15:05,133 --> 01:15:07,347
it puts be on the stack

1295
01:15:07,347 --> 01:15:10,768
and it calls g and then
does all this stuff.

1296
01:15:10,768 --> 01:15:12,458
And then after this it returns.

1297
01:15:12,458 --> 01:15:15,087
And when it returns, it
asks where was I last time?

1298
01:15:16,249 --> 01:15:18,761
And this is what the stack is for.

1299
01:15:18,761 --> 01:15:20,038
So where was I last time?

1300
01:15:20,038 --> 01:15:21,110
I was at b.

1301
01:15:21,110 --> 01:15:24,815
So we pop, putting something
on the stack is pushing.

1302
01:15:24,815 --> 01:15:26,642
Taking off is called popping.

1303
01:15:26,642 --> 01:15:28,370
We pop it and say okay, here's b,

1304
01:15:28,370 --> 01:15:31,402
b is where we were, we go back
to there and we finish this.

1305
01:15:31,402 --> 01:15:34,509
Once we finish this, we say oh
where we were the last time?

1306
01:15:34,509 --> 01:15:38,600
So that's a, and then
go back to a and finish.

1307
01:15:38,600 --> 01:15:40,572
(distant indistinct muttering)

1308
01:15:48,075 --> 01:15:49,483
Yeah, sure, yeah, exactly.

1309
01:15:49,483 --> 01:15:51,193
(distant indistinct muttering)

1310
01:15:52,713 --> 01:15:55,791
Yeah, yeah, so the dialogue which reflects

1311
01:15:55,791 --> 01:15:58,288
Little Harmonic Labyrinvth

1312
01:15:58,288 --> 01:15:59,925
has this sort of structure.

1313
01:15:59,925 --> 01:16:01,890
It goes inside something,
inside yet another thing

1314
01:16:01,890 --> 01:16:03,517
then back out and then back out.

1315
01:16:03,517 --> 01:16:05,299
So it's five o'clock, I'm finished.