1 00:00:05,500 --> 00:00:10,600 ok so we're gonna talk now about a namespace and more about scope because 2 00:00:10,600 --> 00:00:14,940 there are some unusual aspects of scope and name space in Python and that can be 3 00:00:14,940 --> 00:00:19,870 a little bit confusing especially if you've cross from another programming 4 00:00:19,870 --> 00:00:25,060 language so largely things behave as you would expect them to do so what 5 00:00:25,060 --> 00:00:28,630 I'm gonna do here is review some of the basics and then discuss the behavior 6 00:00:28,630 --> 00:00:33,470 that may be strange compared to other languages so Python allows functions 7 00:00:33,470 --> 00:00:37,570 to be nested in other functions which also has an impact on scope in a 8 00:00:37,570 --> 00:00:43,470 possibly unexpected way now one reason for nesting a function within another one is 9 00:00:43,470 --> 00:00:47,820 to perform initialization before a recursive function call so we are gonna start 10 00:00:47,820 --> 00:00:53,340 up explaining a useful programming technique called recursion so a recursive 11 00:00:53,340 --> 00:00:58,030 function is a function that calls itself and they can be very useful in dealing 12 00:00:58,030 --> 00:01:02,800 with structures that contain themselves such as directories in a computer file 13 00:01:02,800 --> 00:01:07,020 system now for computing mathematical functions that are defined recursively 14 00:01:07,020 --> 00:01:12,290 so the mathematical factorial function is a product of all the numbers from one 15 00:01:12,290 --> 00:01:18,030 up to and including in so a function to calculate the factorial for any number can 16 00:01:18,030 --> 00:01:23,670 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:23,670 --> 00:01:29,280 project here a new Python file so do that as well to follow along so let's 18 00:01:29,280 --> 00:01:37,220 create our factorial function so... 19 00:01:37,220 --> 00:01:46,300 ...... 20 00:01:49,110 --> 00:01:59,260 .... 21 00:01:59,260 --> 00:02:08,789 .....again this is the factorial algorithm that we are putting it together 22 00:02:08,789 --> 00:02:22,700 here so we are gonna put.... 23 00:02:22,700 --> 00:02:35,280 ...so that's the function so now can test this so far I in range.... 24 00:02:35,280 --> 00:02:40,030 .... 25 00:02:44,640 --> 00:02:48,470 the n factorial btw is generally written as n! 26 00:02:48,470 --> 00:02:54,030 you can see I've done that in the comments on line 2 and by convention 0 so 0! 27 00:02:54,030 --> 00:02:59,520 is 1 so the functions going to return 1 if n is 0 otherwise it actually 28 00:02:59,520 --> 00:03:04,460 multiplies all the numbers from 1 to n so the range starts at 2 because their's 29 00:03:04,460 --> 00:03:10,360 little point multiplying anything by one and it stops at n + 1 to include the value n so remember 30 00:03:10,360 --> 00:03:15,060 that the last value on our range includes is one less than the stock value and note 31 00:03:15,060 --> 00:03:19,780 here that we're assuming positive\values for any of our function so the loop 32 00:03:19,780 --> 00:03:23,080 at the end of the program calls the fact function for all the numbers from 0 to 130 33 00:03:23,080 --> 00:03:27,560 which you probably gathered by the range that I've got on line 10 and 34 00:03:27,560 --> 00:03:31,970 this is probably the most efficient way to calculate a factorial but it's also good 35 00:03:31,970 --> 00:03:37,120 examples demonstrate recursion but we're going to do first is to run it to see if it does work 36 00:03:37,120 --> 00:03:42,610 and look at making some changes so we are going to run it and you can see that we've 37 00:03:42,610 --> 00:03:45,610 actually got the results 38 00:03:49,530 --> 00:03:56,690 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:56,690 --> 00:04:03,520 larger as you can see it is quite a huge numbers ok so as I mentioned this is probably 40 00:04:03,520 --> 00:04:06,710 the most efficient way to calculate a factorial but it's also a good example 41 00:04:06,710 --> 00:04:12,450 to demonstrate recursion so let's have a look at the recursive equivalent so from 42 00:04:12,450 --> 00:04:15,760 the definition of a factorial and by looking at the output from the program 43 00:04:15,760 --> 00:04:20,709 which I showed on the screen we can see that for example 6 factorials is 6 x 5 44 00:04:20,709 --> 00:04:25,960 factorial or will just run it again rather than me talking about the numbers you 45 00:04:25,960 --> 00:04:34,120 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:34,120 --> 00:04:39,490 x 5 factorial and factorial is 5 x 4 factorial etc so in 47 00:04:39,490 --> 00:04:46,040 fact for any value of n n factorial can be calculated as n take 1 48 00:04:46,040 --> 00:04:50,290 effectively so what we are gonna do is write another function a recursive 49 00:04:50,290 --> 00:04:55,820 equivalent of this so let's do that so I'm gonna star that on line 9 50 00:04:55,820 --> 00:04:59,900 not on line 10 because we need to two spaces between functions two lines between 51 00:04:59,900 --> 00:05:10,010 them so this one will call this one factorial.... 52 00:05:10,010 --> 00:05:24,240 .... 53 00:05:24,240 --> 00:05:42,450 ..... 54 00:05:43,000 --> 00:05:55,490 .... 55 00:05:55,490 --> 00:05:59,400 ..... 56 00:05:59,400 --> 00:06:05,550 ....so we just run it to 57 00:06:05,550 --> 00:06:12,360 make sure it does work so it looks to me that it's producing the same results as 58 00:06:12,360 --> 00:06:17,120 before but obviously its now using recursive function so I'm just going to close this 59 00:06:17,120 --> 00:06:21,130 so I'm just gonna bring up an image on the screen so lets bring up this image 60 00:06:21,130 --> 00:06:28,030 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:28,030 --> 00:06:32,890 the program produces the same result as before but it is now using this 62 00:06:32,890 --> 00:06:38,310 recursive function with the name factorial that we created on line 10 now the factorial 63 00:06:38,310 --> 00:06:43,380 function first checks if n is less than or equal to 1 and if it is it returns 64 00:06:43,380 --> 00:06:49,680 one but for any other value of n it calls itself with a value n -1 then 65 00:06:49,680 --> 00:06:55,520 multiply the result by n it can come a bit confusing to get your head around recursion but 66 00:06:55,520 --> 00:06:59,640 its helpful to think of the successive function calls stacking up and you can 67 00:06:59,640 --> 00:07:03,750 see this image will hopefully help you understand that with anyone called 68 00:07:03,750 --> 00:07:09,460 not returning until the function that n is called returns that sort of makes sense so 69 00:07:09,460 --> 00:07:14,610 when we start an n = 4 factorial 4 can't return until factorial 3 70 00:07:14,610 --> 00:07:17,060 is finish so then 71 00:07:17,060 --> 00:07:20,990 multiplies the result of factorial 3 by 4 and returns then of course 72 00:07:20,990 --> 00:07:25,110 factorial 3 can't return until the call to factorial 2 is finished and so 73 00:07:25,110 --> 00:07:30,210 on so in actual fact the mechanism is a really no different from a function 74 00:07:30,210 --> 00:07:34,480 calling any other function when a function does call another function it 75 00:07:34,480 --> 00:07:37,660 has to wait for that function to finish and the same things actually happening 76 00:07:37,660 --> 00:07:43,880 here so people sometimes find it confusing because the function is calling itself but 77 00:07:43,880 --> 00:07:47,250 as long as their some condition that causes the function at the end of the chain to 78 00:07:47,250 --> 00:07:54,330 return everything ultimately works fine so another recurisve pattern in mathematics is the 79 00:07:54,330 --> 00:07:55,910 Fibonacci series 80 00:07:55,910 --> 00:08:00,610 this crops up remarkably often in nature actually the petals on flowers 81 00:08:00,610 --> 00:08:04,920 and the way they are plant and way the plants grow are often follows a Fibonacci 82 00:08:04,920 --> 00:08:08,690 pattern if you want to know more there's some really interesting links from the 83 00:08:08,690 --> 00:08:11,200 Wikipedia entry and I'm going to bring that up on the screen 84 00:08:11,200 --> 00:08:25,190 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:25,190 --> 00:08:32,230 in nature is quite interesting down here in nature now is linked up here 86 00:08:32,230 --> 00:08:36,669 arrangements of leaves on a stem is quite interesting to look at as well because it 87 00:08:36,669 --> 00:08:41,440 shows many occurrences of Fibonacci numbers in plant growth so each 88 00:08:41,440 --> 00:08:46,780 successive Fibonacci numbers is obtained by adding the two previous numbers if f0 89 00:08:46,780 --> 00:08:52,620 0 being 0 and f1 being 1 and the numbers are really easy to calculate recursively so let's have a 90 00:08:52,620 --> 00:08:55,970 go at creating a Fibonacci method back in our code 91 00:08:57,070 --> 00:09:09,640 Fibonacci function so going to start it on line 19 so..... 92 00:09:09,640 --> 00:09:23,280 .....that's really what we're 93 00:09:23,280 --> 00:09:27,340 trying to achieve so we're going to start this again we are using a some so we are using 94 00:09:27,340 --> 00:09:31,850 recursion here we are gonna put... 95 00:09:31,850 --> 00:09:43,160 .... 96 00:09:43,160 --> 00:09:54,650 ..and lets change the code here on line 26 97 00:09:54,650 --> 00:10:01,590 so we will change the range to.... 98 00:10:03,830 --> 00:10:07,180 and the reason I've done that is I've reduce the range to 36 because the 99 00:10:07,180 --> 00:10:11,940 function takes a while to run once n gets above thirty and in fact 100 00:10:11,940 --> 00:10:16,620 this is a very inefficient way to calculate Fibonacci numbers because it has to 101 00:10:16,620 --> 00:10:20,420 call itself twice for each number and when it comes to Fib n - 1 102 00:10:20,420 --> 00:10:25,840 it has to calculate the value for fib n-2 which it then recalculates in order to add them 103 00:10:25,840 --> 00:10:31,410 together so I just run this to make sure it does work and see how the 104 00:10:31,410 --> 00:10:36,380 thirties above is quite slow to process so its chugging a way we got 105 00:10:36,380 --> 00:10:42,490 quite a fast computer their we go so 0 to 35 is basically done so recursive 106 00:10:42,490 --> 00:10:47,510 functions can certainly be useful but it theirs a simple interactive approach then that 107 00:10:47,510 --> 00:10:51,880 will almost always be better so having seen how long that recursive function took to 108 00:10:51,880 --> 00:10:57,500 calculate the first 35 Fibonacci numbers let's look at a iterative approached that runs 109 00:10:57,500 --> 00:11:10,580 a lot faster so gonna create another method here and will call this one Fibonacci so... 110 00:11:10,580 --> 00:11:30,980 ..... 111 00:11:30,980 --> 00:11:47,300 ... 112 00:11:47,300 --> 00:11:58,960 .... 113 00:11:59,540 --> 00:12:10,950 .... 114 00:12:10,950 --> 00:12:21,820 ...so that is our Fibonacci method that is not using 115 00:12:21,820 --> 00:12:26,330 recursion so let's actually have a run of that just to see if it's any quicker 116 00:12:26,330 --> 00:12:34,640 so we will actually run the Fibonacci method this time instead of the fib method we created so 117 00:12:34,640 --> 00:12:42,270 lets run that so you could see that running it was significantly faster 118 00:12:42,270 --> 00:12:49,060 compared to the fib function that we created so again if you just go back and check the fib 119 00:12:49,060 --> 00:12:59,390 function again using recursion and run that it it takes a significant amount of 120 00:12:59,390 --> 00:13:04,360 time once it gets to around 30 to process those numbers its still processing now as I'm 121 00:13:04,360 --> 00:13:09,970 talking and that's finally finish so the last one was last time was 9227465 122 00:13:09,970 --> 00:13:18,180 compare that to Fibonacci using the other method the other way of doing it without 123 00:13:18,180 --> 00:13:22,330 recursion will run that you can see that's much much faster 124 00:13:23,300 --> 00:13:27,610 actually I think we may have a bit of an issue here with this method because I 125 00:13:27,610 --> 00:13:35,320 think the other one ended on number 35 was 9227465 which I believe is correct and 126 00:13:35,320 --> 00:13:40,690 this one is one out so probably I've made mistakes but what we can do just to confirm 127 00:13:40,690 --> 00:13:50,780 that lets actually print both out so...... 128 00:13:50,780 --> 00:13:53,430 .... 129 00:13:53,430 --> 00:13:58,680 ...just to checked they're actually the same results so lets 130 00:13:58,680 --> 00:14:03,510 just try running that to see whether they are the same as you can see that they're actually 131 00:14:03,510 --> 00:14:08,070 different they're so obviously something that's going on there you can see from number 132 00:14:08,070 --> 00:14:10,060 seven onwards 133 00:14:10,060 --> 00:14:16,500 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:16,500 --> 00:14:21,010 done is I've got the wrong range in the Fibonacci method so in other words calculating one too many 135 00:14:21,010 --> 00:14:27,900 numbers I think that should probably be n not n + 1....so we are actually going through the 136 00:14:27,900 --> 00:14:34,180 range one too many times so run that again that's better we are now getting the same 137 00:14:34,180 --> 00:14:38,760 results for both and as I quickly open a browser will just confirm that these 138 00:14:38,760 --> 00:14:43,180 are actually the correct results you can see we get the right results so what I was doing was just 139 00:14:43,180 --> 00:14:46,700 going to one too many numbers and the calculation was sort of moving on to the 140 00:14:46,700 --> 00:14:56,030 next number if that made sense so that fix that bug up so lets have a quick look at the browser..... 141 00:14:56,030 --> 00:15:08,650 ....the first 300 numbers that is what we want so if we just look 142 00:15:08,650 --> 00:15:15,500 at say 35 is 9227465 and 34 5702887 143 00:15:16,760 --> 00:15:22,340 bit of a spot check their 9227465 5702887 so we've actually got the right 144 00:15:22,340 --> 00:15:27,630 results so that is the bugs fixed but again if we just go through and when we ran it 145 00:15:27,630 --> 00:15:31,140 initially when we did run initially you saw that the recursive routine was 146 00:15:31,140 --> 00:15:36,910 significantly slower than the regular routine that sort of went through and 147 00:15:36,910 --> 00:15:41,130 calculated by actually going through to a range so recursions not 148 00:15:41,130 --> 00:15:45,250 always the go to so it does really depend on what you're trying to achieve and 149 00:15:45,250 --> 00:15:50,430 just in some cases you might wanna make sure you try an alternative way to see 150 00:15:50,430 --> 00:15:55,590 which is the best way of achieving the result but there are useful 151 00:15:55,590 --> 00:15:59,690 applications for recursive functions and we're gonna look at one in the next 152 00:15:59,690 --> 00:16:03,970 video and this is one that is dealing with directory listings of a computer 153 00:16:03,970 --> 00:16:06,210 file systems so let's work on that in the next video