1 00:00:00,000 --> 00:00:03,110 >> SPEAKER 1: In that last version of sigma, I implemented what I would call 2 00:00:03,110 --> 00:00:06,570 an iterative solution, whereby I used a forward loop to count up all of the 3 00:00:06,570 --> 00:00:09,720 numbers between 1 and m, thereafter returning the sum. 4 00:00:09,720 --> 00:00:12,560 >> But it turns out we can use another technique to implement that same 5 00:00:12,560 --> 00:00:15,120 function, a technique known as recursion. 6 00:00:15,120 --> 00:00:19,360 A recursive function, so to speak, is simply one that calls itself. 7 00:00:19,360 --> 00:00:21,290 Now, in and of itself, that might be a problem. 8 00:00:21,290 --> 00:00:24,500 If a function simply calls itself which calls itself which calls itself, 9 00:00:24,500 --> 00:00:26,080 that process might bot ever end. 10 00:00:26,080 --> 00:00:30,490 But so long as we include a so-called base case, a condition that ensures 11 00:00:30,490 --> 00:00:34,930 that in some situations we don't call ourselves, that process of otherwise 12 00:00:34,930 --> 00:00:37,070 infinite looping should cease. 13 00:00:37,070 --> 00:00:39,180 >> Let's now reimplement sigma as follows. 14 00:00:39,180 --> 00:00:43,810 If n is less than or equal to 0, I'm simply, and somewhat arbitrarily, 15 00:00:43,810 --> 00:00:45,670 going to return 0. 16 00:00:45,670 --> 00:00:49,370 Else what I'm going to do is actually compute sigma for the positive int 17 00:00:49,370 --> 00:00:50,460 that I've been handed. 18 00:00:50,460 --> 00:00:52,050 >> Now, what is sigma of m? 19 00:00:52,050 --> 00:00:55,480 Well, sigma of m is, of course, the sum of 1 up through m. 20 00:00:55,480 --> 00:00:58,820 But if we think about it the other way, it's simply the sum of m plus m 21 00:00:58,820 --> 00:01:02,560 minus 1 plus m minus 2 and so forth, all the way down to 1. 22 00:01:02,560 --> 00:01:08,080 So in that sense, it seems that I could simply return m plus. 23 00:01:08,080 --> 00:01:10,210 >> And then I need m minus 1 plus m minus 2. 24 00:01:10,210 --> 00:01:13,470 But I have a function that can give me precisely that answer, namely 25 00:01:13,470 --> 00:01:16,340 sigma of m minus 1. 26 00:01:16,340 --> 00:01:19,670 >> Now, calling myself in this way doesn't seem like the best idea. 27 00:01:19,670 --> 00:01:22,610 Because if sigma calls sigma which calls sigma which calls sigma, you 28 00:01:22,610 --> 00:01:24,480 would think that this process might not ever end. 29 00:01:24,480 --> 00:01:27,720 But that's why we had the so-called base case at the top of this function. 30 00:01:27,720 --> 00:01:31,540 The if condition that checks if m is less than or equal to 0 I'm not going 31 00:01:31,540 --> 00:01:32,610 to call myself. 32 00:01:32,610 --> 00:01:37,010 I'm instead going to return 0, which in turn is going to be added to the 33 00:01:37,010 --> 00:01:39,950 previous numbers that I've been summing up, thereby stopping this 34 00:01:39,950 --> 00:01:41,740 otherwise infinite process. 35 00:01:41,740 --> 00:01:43,710 >> Let's now see if this new implementation works. 36 00:01:43,710 --> 00:01:46,510 Let's save, compile, and run this program. 37 00:01:46,510 --> 00:01:50,640 Make sigma 1 dot slash sigma 1. 38 00:01:50,640 --> 00:01:52,900 And let's provide it with the same numbers as before. 39 00:01:52,900 --> 00:01:55,520 2, which should hopefully give me 3. 40 00:01:55,520 --> 00:01:58,970 Let's provide it with 3, which should hopefully give me 6. 41 00:01:58,970 --> 00:02:03,480 And let's finally provide it with 50, which indeed gives me 1,275. 42 00:02:03,480 --> 00:02:06,130