WEBVTT

1
00:00:01.920 --> 00:00:07.020
ok so we're gonna talk now about a
namespace and more about scope because

2
00:00:07.020 --> 00:00:11.360
there are some unusual aspects of scope and name space in Python and that can be

3
00:00:11.360 --> 00:00:16.299
a little bit confusing especially if you've cross from another programming

4
00:00:16.299 --> 00:00:21.480
language so largely things behave as you would expect them to do so what

5
00:00:21.480 --> 00:00:25.050
I'm gonna do here is review some of the
basics and then discuss the behavior

6
00:00:25.050 --> 00:00:29.890
that may be strange compared to other
languages so Python allows functions

7
00:00:29.890 --> 00:00:33.999
to be nested in other functions which
also has an impact on scope in a

8
00:00:33.999 --> 00:00:39.899
possibly unexpected way now one reason
for nesting a function within another one is

9
00:00:39.899 --> 00:00:44.249
to perform initialization before a
recursive function call so  we are gonna start

10
00:00:44.249 --> 00:00:49.769
up explaining a useful programming
technique called recursion so a recursive

11
00:00:49.769 --> 00:00:54.459
function is a function that calls itself
and they can be very useful in dealing

12
00:00:54.459 --> 00:00:59.229
with structures that contain themselves
such as directories in a computer file

13
00:00:59.229 --> 00:01:03.440
system now for computing mathematical
functions that are defined recursively

14
00:01:03.440 --> 00:01:08.710
so the mathematical factorial function
is a product of all the numbers from one

15
00:01:08.710 --> 00:01:14.450
up to and including in so a function to
calculate the factorial for any number can

16
00:01:14.450 --> 00:01:20.090
be written as a very simple loop we're gonna do that now so lets make a start and I've created a new

17
00:01:20.090 --> 00:01:25.700
project here a new Python file so do that as well to follow along so let's

18
00:01:25.700 --> 00:01:33.640
create our factorial function so...

19
00:01:33.640 --> 00:01:42.729
......

20
00:01:45.530 --> 00:01:55.680
....

21
00:01:55.680 --> 00:02:05.210
.....again this is
the factorial algorithm that we are putting it together

22
00:02:05.210 --> 00:02:19.120
here so we are gonna put....

23
00:02:19.120 --> 00:02:31.709
...so that's the function so now can test this so
far I in range....

24
00:02:31.709 --> 00:02:36.459
....

25
00:02:41.060 --> 00:02:44.890
the n factorial btw is generally
written as n!

26
00:02:44.890 --> 00:02:50.459
you can see I've done that in the
comments on line 2 and by convention 0 so 0!

27
00:02:50.459 --> 00:02:55.940
is 1 so the functions
going to return 1 if n is 0 otherwise it actually

28
00:02:55.940 --> 00:03:00.880
multiplies all the numbers from 1 to n so
the range starts at 2 because their's

29
00:03:00.880 --> 00:03:06.780
little point multiplying anything by one and it stops at n + 1 to include the value n so remember

30
00:03:06.780 --> 00:03:11.480
that the last value on our range includes
is one less than the stock value and note

31
00:03:11.480 --> 00:03:16.200
here that we're assuming positive\values for any of our function so the loop

32
00:03:16.200 --> 00:03:19.500
at the end of the program calls the fact 
function for all the numbers from 0 to 130

33
00:03:19.500 --> 00:03:23.980
which you probably gathered by the range
that I've got on line 10 and

34
00:03:23.980 --> 00:03:28.390
this is probably the most efficient way
to calculate a factorial but it's also good

35
00:03:28.390 --> 00:03:33.549
examples demonstrate recursion but we're
going to do first is to run it to see if it does work

36
00:03:33.549 --> 00:03:39.030
and look at making some changes so we are going to
run it and you can see that we've

37
00:03:39.030 --> 00:03:42.030
actually got the results

38
00:03:45.950 --> 00:03:53.110
and their is our results their 0 returns 1 1 returns 1 2 6 24 and
so on and the numbers get progressively

39
00:03:53.110 --> 00:03:59.940
larger as you can see it is quite a huge numbers
ok so as I mentioned this is probably

40
00:03:59.940 --> 00:04:03.130
the most efficient way to calculate
a factorial but it's also a good example

41
00:04:03.130 --> 00:04:08.870
to demonstrate recursion so let's have a
look at the recursive equivalent so from

42
00:04:08.870 --> 00:04:12.180
the definition of a factorial and by
looking at the output from the program

43
00:04:12.180 --> 00:04:17.130
which I showed on the screen we can see that for
example 6 factorials is 6 x 5

44
00:04:17.130 --> 00:04:22.389
factorial or will just run it again
rather than me talking about the numbers you

45
00:04:22.389 --> 00:04:30.540
not seeing on the screens so lets go back and have a look you can see on the screen now so 6 factorial is 6

46
00:04:30.540 --> 00:04:35.919
x 5 factorial and factorial is 5 x 4 factorial etc so in

47
00:04:35.919 --> 00:04:42.460
fact for any value of n n factorial can
be calculated as n take 1

48
00:04:42.460 --> 00:04:46.710
effectively so what we are gonna do is write
another function a recursive

49
00:04:46.710 --> 00:04:52.240
equivalent of this so let's do that so I'm gonna star that on line 9

50
00:04:52.240 --> 00:04:56.320
not on line 10 because we need to two spaces
between functions two lines between

51
00:04:56.320 --> 00:05:06.430
them so this one will call this one factorial....

52
00:05:06.430 --> 00:05:20.669
....

53
00:05:20.669 --> 00:05:38.870
.....

54
00:05:39.420 --> 00:05:51.910
....

55
00:05:51.910 --> 00:05:55.820
.....

56
00:05:55.820 --> 00:06:01.970
....so we just run it to

57
00:06:01.970 --> 00:06:08.780
make sure it does work so it looks to me that
it's producing the same results as

58
00:06:08.780 --> 00:06:13.540
before but obviously its now using recursive
function so I'm just going to close this

59
00:06:13.540 --> 00:06:17.550
so I'm just gonna bring up an image on the
screen so lets bring up this image

60
00:06:17.550 --> 00:06:24.450
on the screen so you can see a little
bit and I'll put it here so that you can see the code so

61
00:06:24.450 --> 00:06:29.310
the program produces the same result as
before but it is now using this

62
00:06:29.310 --> 00:06:34.730
recursive function with the name factorial that we created on line 10 now the factorial

63
00:06:34.730 --> 00:06:39.800
function first checks if n is less than
or equal to 1 and if it is it returns

64
00:06:39.800 --> 00:06:46.100
one but for any other value of n it calls
itself with a value n -1 then

65
00:06:46.100 --> 00:06:51.940
multiply the result by n it can come a bit
confusing to get your head around recursion but

66
00:06:51.940 --> 00:06:56.060
its helpful to think of the successive
function calls stacking up and you can

67
00:06:56.060 --> 00:07:00.170
see this image will hopefully help you
understand that with anyone called

68
00:07:00.170 --> 00:07:05.880
not returning until the function that n
is called returns that sort of makes sense so

69
00:07:05.880 --> 00:07:11.030
when we start an n = 4 factorial
4 can't return until factorial 3

70
00:07:11.030 --> 00:07:13.480
is finish so then

71
00:07:13.480 --> 00:07:17.410
multiplies the result of factorial 3
by 4 and returns then of course

72
00:07:17.410 --> 00:07:21.530
factorial 3 can't return until the call to factorial 2 is finished and so

73
00:07:21.530 --> 00:07:26.630
on so in actual fact the mechanism is a
really no different from a function

74
00:07:26.630 --> 00:07:30.900
calling any other function when a
function does call another function it

75
00:07:30.900 --> 00:07:34.080
has to wait for that function to finish
and the same things actually happening

76
00:07:34.080 --> 00:07:40.300
here so people sometimes find it confusing
because the function is calling itself but

77
00:07:40.300 --> 00:07:43.670
as long as their some condition that causes the
function at the end of the chain to

78
00:07:43.670 --> 00:07:50.750
return everything ultimately works fine
so another recurisve pattern in mathematics is the

79
00:07:50.750 --> 00:07:52.330
Fibonacci series

80
00:07:52.330 --> 00:07:57.030
this crops up remarkably often in
nature actually the petals on flowers

81
00:07:57.030 --> 00:08:01.340
and the way they are plant and way the
plants grow are often follows a Fibonacci

82
00:08:01.340 --> 00:08:05.110
pattern if you want to know more there's
some really interesting links from the

83
00:08:05.110 --> 00:08:07.620
Wikipedia entry and I'm going to bring
that up on the screen

84
00:08:07.620 --> 00:08:21.610
you wanna know more about to Fibonacci and the link will be in the resources section that maths get a bit heavy but section 15

85
00:08:21.610 --> 00:08:28.659
in nature is quite interesting down here in nature now is linked up here

86
00:08:28.659 --> 00:08:33.099
arrangements of leaves on a stem is quite
interesting to look at as well because it

87
00:08:33.099 --> 00:08:37.860
shows many occurrences of Fibonacci numbers in plant growth so each

88
00:08:37.860 --> 00:08:43.209
successive Fibonacci numbers is obtained by
adding the two previous numbers if f0

89
00:08:43.209 --> 00:08:49.040
0 being 0 and f1 being 1 and the numbers are really easy to calculate recursively so let's have a

90
00:08:49.040 --> 00:08:52.390
go at creating a Fibonacci method back in our code

91
00:08:53.490 --> 00:09:06.060
Fibonacci function so going to start it on line 19 so.....

92
00:09:06.060 --> 00:09:19.709
.....that's really what we're

93
00:09:19.709 --> 00:09:23.769
trying to achieve so we're going to start
this again we are using a some so we are using

94
00:09:23.769 --> 00:09:28.279
recursion here we are gonna put...

95
00:09:28.279 --> 00:09:39.589
....

96
00:09:39.589 --> 00:09:51.079
..and lets change the code here on line 26

97
00:09:51.079 --> 00:09:58.019
so we will change the range to....

98
00:10:00.250 --> 00:10:03.600
and the reason I've done that is
I've reduce the range to 36 because the

99
00:10:03.600 --> 00:10:08.360
function takes a while to run once
n gets above thirty and in fact

100
00:10:08.360 --> 00:10:13.040
this is a very inefficient way
to calculate Fibonacci numbers because it has to

101
00:10:13.040 --> 00:10:16.840
call itself twice for each number and
when it comes to Fib n - 1

102
00:10:16.840 --> 00:10:22.260
it has to calculate the value for fib n-2 which it then recalculates in order to add them

103
00:10:22.260 --> 00:10:27.830
together so I just run this to make sure it
does work and see how the

104
00:10:27.830 --> 00:10:32.800
thirties above is quite slow to process so its chugging a way we got

105
00:10:32.800 --> 00:10:38.910
quite a fast computer their we go so 0 to 35 is basically done so recursive

106
00:10:38.910 --> 00:10:43.930
functions can certainly be useful but it
theirs a simple interactive approach then that

107
00:10:43.930 --> 00:10:48.300
will almost always be better so having
seen how long that recursive function took to

108
00:10:48.300 --> 00:10:53.920
calculate the first 35 Fibonacci numbers let's
look at a iterative approached that runs

109
00:10:53.920 --> 00:11:07.000
a lot faster so gonna create another
method here and will call this one Fibonacci so...

110
00:11:07.000 --> 00:11:27.400
.....

111
00:11:27.400 --> 00:11:43.720
...

112
00:11:43.720 --> 00:11:55.380
....

113
00:11:55.960 --> 00:12:07.379
....

114
00:12:07.379 --> 00:12:18.249
...so that is our 
Fibonacci method that is not using

115
00:12:18.249 --> 00:12:22.759
recursion so let's actually have a run
of that just to see if it's any quicker

116
00:12:22.759 --> 00:12:31.069
so we will actually run the Fibonacci method
this time instead of the fib method we created so

117
00:12:31.069 --> 00:12:38.699
lets run that so you could see that
running it was significantly faster

118
00:12:38.699 --> 00:12:45.489
compared to the fib function that we created
so again if you just go back and check the fib

119
00:12:45.489 --> 00:12:55.819
function again using recursion and run
that it it takes a significant amount of

120
00:12:55.819 --> 00:13:00.789
time once it gets to around 30 to process those numbers its still processing now as I'm

121
00:13:00.789 --> 00:13:06.399
talking and that's finally finish so the last one was last time was 9227465

122
00:13:06.399 --> 00:13:14.600
compare that to Fibonacci using the other method the other way of doing it without

123
00:13:14.600 --> 00:13:18.759
recursion will run that you can see that's much much faster

124
00:13:19.720 --> 00:13:24.039
actually I think we may have a bit of an
issue here with this method because I

125
00:13:24.039 --> 00:13:31.749
think the other one ended on number 35 was
9227465 which I believe is correct and

126
00:13:31.749 --> 00:13:37.119
this one is one out so probably I've
made mistakes but what we can do just to confirm

127
00:13:37.119 --> 00:13:47.209
that lets actually print both out so......

128
00:13:47.209 --> 00:13:49.850
....

129
00:13:49.850 --> 00:13:55.109
...just to checked
they're actually the same results so lets

130
00:13:55.109 --> 00:13:59.939
just try running that to see whether they are the same as
you can see that they're actually

131
00:13:59.939 --> 00:14:04.499
different they're so obviously something
that's going on there you can see from number

132
00:14:04.499 --> 00:14:06.480
seven onwards

133
00:14:06.480 --> 00:14:12.920
they are pretty much all out as you can see clearly only 0 and 1 are the same but the rest are actually out so what I think I've

134
00:14:12.920 --> 00:14:17.430
done is I've got the wrong range in the
Fibonacci method so in other words calculating one too many

135
00:14:17.430 --> 00:14:24.320
numbers I think that should probably be n not n + 1....so we are actually going through the

136
00:14:24.320 --> 00:14:30.600
range one too many times so run that again that's better we are now getting the same

137
00:14:30.600 --> 00:14:35.180
results for both and as I quickly open
a browser will just confirm that these

138
00:14:35.180 --> 00:14:39.600
are actually the correct results you can see we get the
right results so what I was doing was just

139
00:14:39.600 --> 00:14:43.120
going to one too many numbers and the
calculation was sort of moving on to the

140
00:14:43.120 --> 00:14:52.459
next number if that made sense so that fix that bug up so lets have a quick look at the browser.....

141
00:14:52.459 --> 00:15:05.070
....the first 300
numbers that is what we want so if we just look

142
00:15:05.070 --> 00:15:11.920
at say 35 is 9227465 and 34 5702887

143
00:15:13.180 --> 00:15:18.769
bit of a spot check their 9227465 5702887 so we've actually got the right

144
00:15:18.769 --> 00:15:24.050
results so that is the bugs fixed but again if we
just go through and when we ran it

145
00:15:24.050 --> 00:15:27.569
initially when we did run initially
you saw that the recursive routine was

146
00:15:27.569 --> 00:15:33.339
significantly slower than the regular
routine that sort of went through and

147
00:15:33.339 --> 00:15:37.550
calculated by actually going through
to a range so recursions not

148
00:15:37.550 --> 00:15:41.670
always the go to so it does really depend
on what you're trying to achieve and

149
00:15:41.670 --> 00:15:46.850
just in some cases you might wanna make
sure you try an alternative way to see

150
00:15:46.850 --> 00:15:52.019
which is the best way of achieving the result but there are useful

151
00:15:52.019 --> 00:15:56.110
applications for recursive functions and
we're gonna look at one in the next

152
00:15:56.110 --> 00:16:00.399
video and this is one that is dealing
with directory listings of a computer

153
00:16:00.399 --> 00:16:02.630
file systems so let's work on that in the
next video