Would you like to inspect the original subtitles? These are the user uploaded subtitles that are being translated: 1 1 00:00:00,211 --> 00:00:05,211 (lively music) (keyboard clacking) 2 2 00:00:05,320 --> 00:00:07,970 The next couple of algorithms we'll look at 3 3 00:00:07,970 --> 00:00:09,610 can be written recursively 4 4 00:00:09,610 --> 00:00:11,710 and they're often written recursively, 5 5 00:00:11,710 --> 00:00:14,092 so let's take a brief timeout 6 6 00:00:14,092 --> 00:00:16,020 and talk about recursion 7 7 00:00:16,020 --> 00:00:18,360 to make sure we're all on the same page. 8 8 00:00:18,360 --> 00:00:22,100 A method is a recursive method when it calls itself, 9 9 00:00:22,100 --> 00:00:25,420 so we're gonna take a look at calculating the factorial 10 10 00:00:25,420 --> 00:00:26,420 for a number. 11 11 00:00:26,420 --> 00:00:28,800 As a reminder to calculate the factorial, 12 12 00:00:28,800 --> 00:00:30,120 you start with the number 13 13 00:00:30,120 --> 00:00:33,350 and then you multiply it by number minus one 14 14 00:00:33,350 --> 00:00:36,210 and then you multiply the result by number minus two 15 15 00:00:36,210 --> 00:00:40,300 and you multiply that result by number minus three et cetera 16 16 00:00:40,300 --> 00:00:43,150 until you hit zero and then you stop. 17 17 00:00:43,150 --> 00:00:47,990 So, three factorial would be three times two times one 18 18 00:00:47,990 --> 00:00:49,340 which equals six. 19 19 00:00:49,340 --> 00:00:54,340 100 factorial would 100 times 99 times 98 20 20 00:00:54,370 --> 00:00:58,260 times 97, all the way down to times one 21 21 00:00:58,260 --> 00:01:03,260 and the result of that is 9.332622 to the power of 157 22 22 00:01:05,300 --> 00:01:06,840 which is a pretty large number. 23 23 00:01:06,840 --> 00:01:08,890 Now, how about zero factorial? 24 24 00:01:08,890 --> 00:01:11,520 Well, by definition that's equal to one. 25 25 00:01:11,520 --> 00:01:13,950 So, zero factorial is one. 26 26 00:01:13,950 --> 00:01:15,950 If you're wondering about negative numbers, 27 27 00:01:15,950 --> 00:01:19,370 the factorials for negative numbers are undefined. 28 28 00:01:19,370 --> 00:01:23,600 So, I have on the screen the factorial algorithm, 29 29 00:01:23,600 --> 00:01:25,810 the steps for calculating the factorial. 30 30 00:01:25,810 --> 00:01:28,870 We start out by saying if num is equal to zero, 31 31 00:01:28,870 --> 00:01:31,240 so if we're taking num factorial, 32 32 00:01:31,240 --> 00:01:32,700 if num is equal to zero, 33 33 00:01:32,700 --> 00:01:34,080 then the factorial is one 34 34 00:01:34,080 --> 00:01:36,200 and we stop, we have the result. 35 35 00:01:36,200 --> 00:01:38,910 Otherwise we set the multiplier to one 36 36 00:01:38,910 --> 00:01:41,160 and we set the factorial to one 37 37 00:01:41,160 --> 00:01:44,440 and then while the multiplier is not equal to num, 38 38 00:01:44,440 --> 00:01:46,420 we do steps five and six. 39 39 00:01:46,420 --> 00:01:49,750 We multiply factorial by multiplier 40 40 00:01:49,750 --> 00:01:51,950 and we assign the result to factorial 41 41 00:01:51,950 --> 00:01:54,130 and then we add one to multiplier 42 42 00:01:54,130 --> 00:01:57,060 and so, we'll say one times one, 43 43 00:01:57,060 --> 00:02:00,120 add one to multiplier, so multiplier will become two, 44 44 00:02:00,120 --> 00:02:02,770 so we'll have one times one times two 45 45 00:02:02,770 --> 00:02:05,370 and then we'll assign two to factorial 46 46 00:02:05,370 --> 00:02:07,200 and then we'll multiply that by three 47 47 00:02:07,200 --> 00:02:09,320 and so, we'll assign six to factorial, 48 48 00:02:09,320 --> 00:02:10,740 we'll multiply that by four, 49 49 00:02:10,740 --> 00:02:13,220 assign 24 to factorial et cetera 50 50 00:02:13,220 --> 00:02:15,640 and we keep going until multiplier 51 51 00:02:15,640 --> 00:02:18,020 is equal to num at which point we stop. 52 52 00:02:18,020 --> 00:02:19,380 So, that's another way of looking at it 53 53 00:02:19,380 --> 00:02:23,030 instead of counting down and going three times two times one 54 54 00:02:23,030 --> 00:02:24,450 for six factorial, 55 55 00:02:24,450 --> 00:02:27,270 we can also say one times two times three. 56 56 00:02:27,270 --> 00:02:28,800 It'll give us the same result. 57 57 00:02:28,800 --> 00:02:30,050 So, in this algorithm, 58 58 00:02:30,050 --> 00:02:32,360 we basically have a rinse-and-repeat step 59 59 00:02:32,360 --> 00:02:33,924 which is step number four. 60 60 00:02:33,924 --> 00:02:36,890 Step number four says that while the multiplier 61 61 00:02:36,890 --> 00:02:40,440 is not equal to num, do steps five to six. 62 62 00:02:40,440 --> 00:02:42,273 So, how would we code this? 63 63 00:02:42,273 --> 00:02:44,800 Let's go out to IntelliJ 64 64 00:02:44,800 --> 00:02:45,960 and we'll write the function 65 65 00:02:45,960 --> 00:02:49,840 that calculates the factorial in an iterative way. 66 66 00:02:49,840 --> 00:02:51,483 So, we'll use a for loop. 67 67 00:02:57,250 --> 00:03:00,370 So, here I am in IntelliJ and I've created a project, 68 68 00:03:00,370 --> 00:03:03,890 the package is academy.learnprogramming.recursion 69 69 00:03:03,890 --> 00:03:06,268 and I'm going to write a method 70 70 00:03:06,268 --> 00:03:09,950 to calculate the factorial in an iterative fashion 71 71 00:03:09,950 --> 00:03:13,060 and that means we're not going to use recursion. 72 72 00:03:13,060 --> 00:03:15,260 So, I'm gonna say public static, 73 73 00:03:15,260 --> 00:03:18,060 static because we'll be calling it from the main method, 74 74 00:03:18,060 --> 00:03:19,360 it's gonna return an integer, 75 75 00:03:19,360 --> 00:03:23,200 the factorial and I'll call it iterativeFactorial 76 76 00:03:23,200 --> 00:03:25,313 and of course we wanna pass in num. 77 77 00:03:27,150 --> 00:03:30,010 So, the first thing we'll check is whether num equals zero 78 78 00:03:30,010 --> 00:03:31,530 because if num equals zero, 79 79 00:03:31,530 --> 00:03:34,523 we know that the result is one. 80 80 00:03:36,050 --> 00:03:37,600 And so, we'll just return one. 81 81 00:03:37,600 --> 00:03:39,410 If num doesn't equal zero, 82 82 00:03:39,410 --> 00:03:43,520 we'll set a field called factorial to one 83 83 00:03:43,520 --> 00:03:46,720 and then we'll say for int i equals one, 84 84 00:03:46,720 --> 00:03:50,220 i less than or equal to num, i++ 85 85 00:03:54,030 --> 00:03:57,363 factorial is assigned factorial times i. 86 86 00:04:01,330 --> 00:04:02,650 And when we drop out of the loop, 87 87 00:04:02,650 --> 00:04:05,600 we have the factorial, so we'll just return that. 88 88 00:04:05,600 --> 00:04:06,790 So, what's happening here, 89 89 00:04:06,790 --> 00:04:09,580 let's say we wanted to calculate three factorial 90 90 00:04:09,580 --> 00:04:10,870 'cause we know that that's six, 91 91 00:04:10,870 --> 00:04:12,760 so num is not equal to zero, 92 92 00:04:12,760 --> 00:04:16,130 so we don't return, we'll set factorial to one, 93 93 00:04:16,130 --> 00:04:18,080 i has to be less than or equal to three, 94 94 00:04:18,080 --> 00:04:19,730 'cause we're passing in three, 95 95 00:04:19,730 --> 00:04:22,916 so on the first iteration, the loop factorial 96 96 00:04:22,916 --> 00:04:26,280 will be assigned factorial times one 97 97 00:04:26,280 --> 00:04:28,690 and we start out with factorial being one, 98 98 00:04:28,690 --> 00:04:31,630 so factorial will get one times one which is one, 99 99 00:04:31,630 --> 00:04:34,830 i will become two, so factorial gets one times two 100 100 00:04:34,830 --> 00:04:37,490 which is two and then i becomes three, 101 101 00:04:37,490 --> 00:04:40,810 so factorial gets two times three which six 102 102 00:04:40,810 --> 00:04:41,730 and then at this point, 103 103 00:04:41,730 --> 00:04:45,310 i becomes four, it's no longer less than or equal to num, 104 104 00:04:45,310 --> 00:04:46,300 so we drop out 105 105 00:04:46,300 --> 00:04:48,690 and so, we return six. 106 106 00:04:48,690 --> 00:04:51,330 So, that means three factorial is six. 107 107 00:04:51,330 --> 00:04:54,480 And so, this an iterative implementation. 108 108 00:04:54,480 --> 00:04:55,567 We're not using recursion, 109 109 00:04:55,567 --> 00:04:57,880 the method does not call itself. 110 110 00:04:57,880 --> 00:05:00,820 So, what about a recursive implementation? 111 111 00:05:00,820 --> 00:05:02,330 Well, instead of using the loop, 112 112 00:05:02,330 --> 00:05:04,190 we can have the method call itself 113 113 00:05:04,190 --> 00:05:05,890 because think about it, 114 114 00:05:05,890 --> 00:05:09,820 two factorial is one factorial times two, 115 115 00:05:09,820 --> 00:05:13,910 three factorial is two factorial times three, 116 116 00:05:13,910 --> 00:05:17,720 four factorial is three factorial times four. 117 117 00:05:17,720 --> 00:05:20,043 I'm gonna write these out in a comment 118 118 00:05:20,043 --> 00:05:22,060 so you can see what I mean, 119 119 00:05:22,060 --> 00:05:25,570 so one factorial and usually we write factorial 120 120 00:05:25,570 --> 00:05:26,810 using exclamation marks, 121 121 00:05:26,810 --> 00:05:30,710 so one factorial equals zero factorial 122 122 00:05:30,710 --> 00:05:33,420 which we know is one times one 123 123 00:05:33,420 --> 00:05:36,150 which equals one, right? 124 124 00:05:36,150 --> 00:05:39,840 Two factorial equals two times one 125 125 00:05:40,780 --> 00:05:45,780 and this is actually two times one factorial 126 126 00:05:46,350 --> 00:05:49,063 because we know that one factorial is one. 127 127 00:05:50,570 --> 00:05:55,570 Three factorial equals three times two 128 128 00:05:56,460 --> 00:06:00,880 times one and that's equivalent to three 129 129 00:06:02,330 --> 00:06:04,730 times two factorial 130 130 00:06:04,730 --> 00:06:07,970 because two factorial is two times one, 131 131 00:06:07,970 --> 00:06:10,233 so that's three times two factorial. 132 132 00:06:11,420 --> 00:06:14,880 Four factorial is equal to four 133 133 00:06:14,880 --> 00:06:18,630 times three times two times one. 134 134 00:06:18,630 --> 00:06:21,454 And that's equivalent to four 135 135 00:06:21,454 --> 00:06:25,070 times three factorial because three factorial 136 136 00:06:25,070 --> 00:06:27,290 is equal to three times two times one. 137 137 00:06:27,290 --> 00:06:29,190 So, you can see the pattern now. 138 138 00:06:29,190 --> 00:06:32,210 So, one factorial is I guess I should reverse that 139 139 00:06:32,210 --> 00:06:36,220 for consistency, so one times zero factorial, 140 140 00:06:36,220 --> 00:06:38,280 two factorial is two times one 141 141 00:06:38,280 --> 00:06:41,200 which is two times one factorial, 142 142 00:06:41,200 --> 00:06:44,030 three factorial is three times two times one 143 143 00:06:44,030 --> 00:06:47,080 which is equivalent to three times two factorial, 144 144 00:06:47,080 --> 00:06:49,410 four factorial is four times three 145 145 00:06:49,410 --> 00:06:51,090 times two times one 146 146 00:06:51,090 --> 00:06:53,860 which is equivalent to four times three factorial. 147 147 00:06:53,860 --> 00:06:56,750 Five factorial would be five times four 148 148 00:06:56,750 --> 00:06:59,000 times three times two times one 149 149 00:06:59,000 --> 00:07:02,430 which is equivalent to five times four factorial. 150 150 00:07:02,430 --> 00:07:05,240 And so, to calculate each factorial, 151 151 00:07:05,240 --> 00:07:08,070 we can use a factorial. 152 152 00:07:08,070 --> 00:07:11,770 Basically we multiply the num, the number 153 153 00:07:11,770 --> 00:07:15,070 by n minus one factorial. 154 154 00:07:15,070 --> 00:07:16,790 So, basically we're doing the following. 155 155 00:07:16,790 --> 00:07:21,790 To get n factorial, that equals n minus one factorial 156 156 00:07:23,010 --> 00:07:25,230 times n, right? 157 157 00:07:25,230 --> 00:07:26,280 I'll do it like that 158 158 00:07:26,280 --> 00:07:29,011 because that's how I wrote it above. 159 159 00:07:29,011 --> 00:07:32,720 So, basically this is the formula we can use 160 160 00:07:32,720 --> 00:07:34,480 to get the factorial of n, 161 161 00:07:34,480 --> 00:07:38,140 it's equal to n times n minus one factorial. 162 162 00:07:38,140 --> 00:07:39,470 And so, let's write a method 163 163 00:07:39,470 --> 00:07:41,120 that uses this information. 164 164 00:07:41,120 --> 00:07:43,870 So, we'll say public static int 165 165 00:07:43,870 --> 00:07:46,443 and we'll call this one recursiveFactorial 166 166 00:07:47,770 --> 00:07:50,020 and we'll pass in num as we did before 167 167 00:07:51,330 --> 00:07:52,810 and we'll start out the same way. 168 168 00:07:52,810 --> 00:07:54,593 If num equals zero, 169 169 00:07:56,150 --> 00:07:57,390 then we return one. 170 170 00:07:57,390 --> 00:08:00,080 We know that zero factorial is one. 171 171 00:08:00,080 --> 00:08:02,030 Otherwise what are we gonna return? 172 172 00:08:02,030 --> 00:08:07,030 Num times recursiveFactorial of num minus one. 173 173 00:08:08,250 --> 00:08:11,040 Because we've just said that we can calculate 174 174 00:08:11,040 --> 00:08:14,180 the factorial of n by multiplying n 175 175 00:08:14,180 --> 00:08:16,930 by n minus one factorial 176 176 00:08:16,930 --> 00:08:20,380 and so, here we're calling the same method, 177 177 00:08:20,380 --> 00:08:22,300 we're calling the method itself 178 178 00:08:22,300 --> 00:08:25,070 to get the value and here you can notice in the gutter, 179 179 00:08:25,070 --> 00:08:27,570 IntelliJ has added this icon here 180 180 00:08:27,570 --> 00:08:29,960 to tell us that we're making a recursive call. 181 181 00:08:29,960 --> 00:08:32,100 But how does this actually work? 182 182 00:08:32,100 --> 00:08:33,280 Let me move this up. 183 183 00:08:33,280 --> 00:08:35,990 So, let's say we call recursiveFactorial 184 184 00:08:35,990 --> 00:08:37,570 with a value of three. 185 185 00:08:37,570 --> 00:08:40,160 Well, we're going to say does num equal zero? 186 186 00:08:40,160 --> 00:08:41,770 No, it doesn't, so we'll come down 187 187 00:08:41,770 --> 00:08:42,603 and we'll say okay, 188 188 00:08:42,603 --> 00:08:47,240 we want to return three times recursiveFactorial of two. 189 189 00:08:47,240 --> 00:08:49,040 Now, this doesn't return right away 190 190 00:08:49,040 --> 00:08:50,530 because what's gonna happen 191 191 00:08:50,530 --> 00:08:54,730 is we have to wait until we get the value 192 192 00:08:54,730 --> 00:08:57,780 of recursiveFactorial num minus one, 193 193 00:08:57,780 --> 00:08:58,970 and so, what will happen 194 194 00:08:58,970 --> 00:09:02,200 is the call to recursiveFactorial 195 195 00:09:02,200 --> 00:09:04,930 with a value of three is going to pushed 196 196 00:09:04,930 --> 00:09:07,380 onto what's called the call stack 197 197 00:09:07,380 --> 00:09:09,830 and then recursiveFactorial two 198 198 00:09:09,830 --> 00:09:11,780 is going to be executed. 199 199 00:09:11,780 --> 00:09:15,220 So, we haven't returned from recursiveFactorial three 200 200 00:09:15,220 --> 00:09:17,200 'cause we have to wait for this result 201 201 00:09:17,200 --> 00:09:19,350 and then we come into recursiveFactorial 202 202 00:09:19,350 --> 00:09:21,300 with two into this call, 203 203 00:09:21,300 --> 00:09:24,250 num isn't zero, so this time we're going to want 204 204 00:09:24,250 --> 00:09:27,680 to return two times recursiveFactorial 205 205 00:09:27,680 --> 00:09:29,670 of two minus one which is one, 206 206 00:09:29,670 --> 00:09:32,080 so now the recursiveFactorial call 207 207 00:09:32,080 --> 00:09:34,280 with the value two has to wait 208 208 00:09:34,280 --> 00:09:36,060 and so, it's going to get pushed 209 209 00:09:36,060 --> 00:09:37,760 onto the call stack 210 210 00:09:37,760 --> 00:09:41,090 and recursiveFactorial one is going to be called. 211 211 00:09:41,090 --> 00:09:43,980 So, basically at this point, we have two calls 212 212 00:09:43,980 --> 00:09:46,310 to recursiveFactorial that are waiting 213 213 00:09:46,310 --> 00:09:47,760 for a return value, 214 214 00:09:47,760 --> 00:09:50,303 we call recursiveFactorial one, 215 215 00:09:50,303 --> 00:09:53,600 one isn't zero, so we're gonna come down here 216 216 00:09:53,600 --> 00:09:56,880 and return one times recursiveFactorial 217 217 00:09:56,880 --> 00:09:58,530 of one minus one which is zero. 218 218 00:09:58,530 --> 00:10:02,040 So, now the recursiveFactorial call with one 219 219 00:10:02,040 --> 00:10:03,610 is gonna get pushed on the stack 220 220 00:10:03,610 --> 00:10:07,610 because it's waiting and we call recursiveFactorial zero, 221 221 00:10:07,610 --> 00:10:09,020 so we're gonna come in here, 222 222 00:10:09,020 --> 00:10:11,140 ah, this time num is zero, 223 223 00:10:11,140 --> 00:10:14,950 so we return one and this call is finished, 224 224 00:10:14,950 --> 00:10:16,650 it doesn't get pushed onto the stack 225 225 00:10:16,650 --> 00:10:20,720 but now the recursiveFactorial call with zero returns 226 226 00:10:20,720 --> 00:10:23,520 and that's the call that recursiveFactorial 227 227 00:10:23,520 --> 00:10:25,910 with the value one is waiting for. 228 228 00:10:25,910 --> 00:10:28,320 So, now that call can resume 229 229 00:10:28,320 --> 00:10:31,010 and it gets the return value of one 230 230 00:10:31,010 --> 00:10:33,240 and so, it multiplies one by one 231 231 00:10:33,240 --> 00:10:34,610 and it returns one 232 232 00:10:34,610 --> 00:10:37,900 and now the call to recursiveFactorial two 233 233 00:10:37,900 --> 00:10:39,600 can resume because it was waiting 234 234 00:10:39,600 --> 00:10:42,980 for the return value of recursiveFactorial one. 235 235 00:10:42,980 --> 00:10:45,420 And so, it multiplies two by one, 236 236 00:10:45,420 --> 00:10:47,790 to get two, it returns two 237 237 00:10:47,790 --> 00:10:51,540 and now the call to recursiveFactorial three can resume 238 238 00:10:51,540 --> 00:10:53,980 because it was waiting for the return value 239 239 00:10:53,980 --> 00:10:56,260 of recursiveFactorial two. 240 240 00:10:56,260 --> 00:10:58,580 And so, it multiplies three by two, 241 241 00:10:58,580 --> 00:11:01,540 it gets six, it returns and we have finished, 242 242 00:11:01,540 --> 00:11:04,520 there's no more calls to recursiveFactorial 243 243 00:11:04,520 --> 00:11:05,830 waiting on the call stack 244 244 00:11:05,830 --> 00:11:07,970 and so, six gets returned 245 245 00:11:07,970 --> 00:11:09,680 but you'll notice that the order 246 246 00:11:09,680 --> 00:11:12,120 in which the recursive calls are made, 247 247 00:11:12,120 --> 00:11:14,840 they return in the reverse order. 248 248 00:11:14,840 --> 00:11:17,963 So, basically the situation that we have, 249 249 00:11:19,060 --> 00:11:23,650 so we start out with calling recursiveFactorial three 250 250 00:11:23,650 --> 00:11:25,180 and when it hits this line, 251 251 00:11:25,180 --> 00:11:27,100 it calls recursiveFactorial two. 252 252 00:11:27,100 --> 00:11:30,010 So, it can't return until it gets the value 253 253 00:11:30,010 --> 00:11:32,640 of recursiveFactorial two and so, the call 254 254 00:11:32,640 --> 00:11:35,280 to recursiveFactorial three 255 255 00:11:36,520 --> 00:11:38,770 gets pushed onto the call stack. 256 256 00:11:38,770 --> 00:11:41,340 Then recursiveFactorial two is called. 257 257 00:11:41,340 --> 00:11:44,040 It can't return until it gets the result 258 258 00:11:44,040 --> 00:11:45,893 of recursiveFactorial one. 259 259 00:11:47,260 --> 00:11:50,843 And so, it gets pushed onto the call stack. 260 260 00:11:53,120 --> 00:11:57,150 And then recursiveFactorial one 261 261 00:11:57,150 --> 00:11:59,090 will get pushed onto the call stack 262 262 00:11:59,090 --> 00:12:02,080 and recursiveFactorial zero 263 263 00:12:02,080 --> 00:12:04,080 will actually return right away, 264 264 00:12:04,080 --> 00:12:07,510 so when recursiveFactorial zero returns, 265 265 00:12:07,510 --> 00:12:10,480 this gets popped off the call stack 266 266 00:12:10,480 --> 00:12:12,080 and it continues executing 267 267 00:12:12,080 --> 00:12:13,500 and it will return one 268 268 00:12:13,500 --> 00:12:15,960 and when that returns, this gets popped up 269 269 00:12:15,960 --> 00:12:19,170 off the call stack, it continues executing 270 270 00:12:19,170 --> 00:12:20,760 and returns the value two 271 271 00:12:20,760 --> 00:12:24,270 and finally this gets popped off the call stack 272 272 00:12:24,270 --> 00:12:26,850 and it returns the value six. 273 273 00:12:26,850 --> 00:12:28,740 That's how recursion works. 274 274 00:12:28,740 --> 00:12:31,150 And it's important to see that when you enter 275 275 00:12:31,150 --> 00:12:33,390 a recursive method, it might be a while 276 276 00:12:33,390 --> 00:12:34,860 before it returns. 277 277 00:12:34,860 --> 00:12:36,580 You can go down the rabbit hole 278 278 00:12:36,580 --> 00:12:39,390 and you can go down, so when you see recursion 279 279 00:12:39,390 --> 00:12:41,240 in the upcoming sort algorithms 280 280 00:12:41,240 --> 00:12:42,630 that we're going to look at, 281 281 00:12:42,630 --> 00:12:46,150 keep in mind that the call to a recursive method 282 282 00:12:46,150 --> 00:12:48,570 may result in many more calls 283 283 00:12:48,570 --> 00:12:51,760 before it returns, so it's important to understand 284 284 00:12:51,760 --> 00:12:54,300 that a three-line recursive method 285 285 00:12:54,300 --> 00:12:57,250 could result in hundreds of recursive calls. 286 286 00:12:57,250 --> 00:12:59,150 The code might look simple 287 287 00:12:59,150 --> 00:13:01,440 but it can lead to a tonne of processing. 288 288 00:13:01,440 --> 00:13:03,440 And it's really important to understand 289 289 00:13:03,440 --> 00:13:06,630 that none of the recursive calls return 290 290 00:13:06,630 --> 00:13:09,120 until they receive the result 291 291 00:13:09,120 --> 00:13:11,720 from the method that they invoked recursively, 292 292 00:13:11,720 --> 00:13:15,080 so as we saw, recursiveFactorial three 293 293 00:13:15,080 --> 00:13:16,263 invoked recursiveFactorial two, 294 294 00:13:17,506 --> 00:13:20,830 so recursiveFactorial three is not going to return, 295 295 00:13:20,830 --> 00:13:24,690 it can't return until recursiveFactorial two 296 296 00:13:24,690 --> 00:13:26,233 has finished executing. 297 297 00:13:27,890 --> 00:13:32,350 You'll notice here that the recursive calls 298 298 00:13:32,350 --> 00:13:35,260 are ended when we pass num equals zero 299 299 00:13:35,260 --> 00:13:37,330 because when we pass in num equals zero, 300 300 00:13:37,330 --> 00:13:40,590 we don't make a recursive call, we just return one. 301 301 00:13:40,590 --> 00:13:42,640 If we didn't have this condition, 302 302 00:13:42,640 --> 00:13:46,120 we'd never end, we'd just keep making recursive call 303 303 00:13:46,120 --> 00:13:48,710 after recursive call after recursive call. 304 304 00:13:48,710 --> 00:13:51,210 So, in order for recursion to work properly, 305 305 00:13:51,210 --> 00:13:53,010 you need some condition 306 306 00:13:53,010 --> 00:13:54,937 that's going to end the recursion. 307 307 00:13:54,937 --> 00:13:58,930 And that condition is known as the breaking condition 308 308 00:13:58,930 --> 00:14:01,160 and it's also called the base case. 309 309 00:14:01,160 --> 00:14:03,870 So, in the recursiveFactorial method, 310 310 00:14:03,870 --> 00:14:06,630 this if num equals zero condition 311 311 00:14:06,630 --> 00:14:09,960 is the base case or the breaking condition. 312 312 00:14:09,960 --> 00:14:12,570 At that point, when num equals zero, 313 313 00:14:12,570 --> 00:14:15,746 we say that the recursion starts to unwind, 314 314 00:14:15,746 --> 00:14:18,800 so at that point it's gonna return a value 315 315 00:14:18,800 --> 00:14:21,520 and the method that invoked it recursively 316 316 00:14:21,520 --> 00:14:23,630 will now be able to continue executing 317 317 00:14:23,630 --> 00:14:25,230 and then it will return a value 318 318 00:14:25,230 --> 00:14:27,250 and the method that invoked it recursively 319 319 00:14:27,250 --> 00:14:30,580 will be able to continue executing et cetera. 320 320 00:14:30,580 --> 00:14:32,070 So, when you use recursion, 321 321 00:14:32,070 --> 00:14:33,800 you need a breaking condition. 322 322 00:14:33,800 --> 00:14:35,045 If you don't have one, 323 323 00:14:35,045 --> 00:14:36,870 what will happen is the method 324 324 00:14:36,870 --> 00:14:38,710 will keep calling itself recursively 325 325 00:14:38,710 --> 00:14:41,780 and eventually you'll get a stack overflow exception 326 326 00:14:41,780 --> 00:14:44,590 because the call stack only has a certain amount 327 327 00:14:44,590 --> 00:14:46,410 of memory allocated to it. 328 328 00:14:46,410 --> 00:14:48,530 And so, eventually you'll blow that memory. 329 329 00:14:48,530 --> 00:14:50,700 So, let's run our recursive code. 330 330 00:14:50,700 --> 00:14:52,450 Well, we'll run them both actually. 331 331 00:14:57,090 --> 00:14:59,690 Let's System.out.print line 332 332 00:14:59,690 --> 00:15:03,090 and we'll print out iterativeFactorial of three 333 333 00:15:04,837 --> 00:15:08,920 and we'll do the same thing for recursiveFactorial three 334 334 00:15:08,920 --> 00:15:11,650 and we should see six in both cases. 335 335 00:15:11,650 --> 00:15:12,483 Let's run. 336 336 00:15:15,330 --> 00:15:17,900 And sure enough, we get two sixes. 337 337 00:15:17,900 --> 00:15:20,420 For fun, for fun and giggles, 338 338 00:15:20,420 --> 00:15:25,180 let's remove the or just comment out this breaking condition 339 339 00:15:25,180 --> 00:15:26,840 and you're gonna see what happens here, 340 340 00:15:26,840 --> 00:15:28,090 it's not gonna be pretty. 341 341 00:15:31,130 --> 00:15:32,480 And look at that. 342 342 00:15:32,480 --> 00:15:34,980 We get all these recursive calls 343 343 00:15:34,980 --> 00:15:39,250 until eventually we get a stack overflow error. 344 344 00:15:39,250 --> 00:15:42,210 And so, we just keep, this method just keeps calling itself 345 345 00:15:42,210 --> 00:15:43,760 and calling itself and calling itself 346 346 00:15:43,760 --> 00:15:46,010 and there's nothing to stop it from doing that 347 347 00:15:46,010 --> 00:15:48,410 and so, we have all these, 348 348 00:15:48,410 --> 00:15:50,740 you're actually looking here at the call stack here, 349 349 00:15:50,740 --> 00:15:52,830 so you're looking at all of the methods 350 350 00:15:52,830 --> 00:15:53,880 that are on the call stack 351 351 00:15:53,880 --> 00:15:57,330 and as you can see, it just keeps invoking itself 352 352 00:15:57,330 --> 00:16:00,570 until we blow the call stack space. 353 353 00:16:00,570 --> 00:16:02,033 I'll uncomment that now. 354 354 00:16:03,558 --> 00:16:05,430 So, that's recursion. 355 355 00:16:05,430 --> 00:16:07,770 Now, here's something interesting. 356 356 00:16:07,770 --> 00:16:11,810 The iterative implementation usually runs faster 357 357 00:16:11,810 --> 00:16:13,920 and it doesn't use as much memory 358 358 00:16:13,920 --> 00:16:18,920 because there's overhead involved with pushing method calls 359 359 00:16:18,990 --> 00:16:20,640 onto the call stack 360 360 00:16:20,640 --> 00:16:23,810 and each stack frame uses some memory 361 361 00:16:23,810 --> 00:16:26,850 but sometimes the iterative way isn't as intuitive 362 362 00:16:26,850 --> 00:16:28,940 or if you write the algorithm 363 363 00:16:28,940 --> 00:16:32,890 in an iterative way, it'll be like a 500-line method 364 364 00:16:32,890 --> 00:16:34,250 or something like that, 365 365 00:16:34,250 --> 00:16:36,870 so developers still use recursion 366 366 00:16:36,870 --> 00:16:38,740 because it's often the most elegant 367 367 00:16:38,740 --> 00:16:41,760 and more easier to understand solution. 368 368 00:16:41,760 --> 00:16:43,897 Now, when we're dealing with the recursive method, 369 369 00:16:43,897 --> 00:16:45,840 the call stack can also be referred 370 370 00:16:45,840 --> 00:16:47,850 to as the recursion stack 371 371 00:16:47,850 --> 00:16:50,340 and we saw that when we don't have a breaking condition, 372 372 00:16:50,340 --> 00:16:52,320 we'll get a stack overflow exception. 373 373 00:16:52,320 --> 00:16:54,470 It's possible to get that exception 374 374 00:16:54,470 --> 00:16:56,960 even when you do have a breaking condition. 375 375 00:16:56,960 --> 00:16:58,900 If you write a recursive method 376 376 00:16:58,900 --> 00:17:01,910 and it invokes itself 1,000 times, 377 377 00:17:01,910 --> 00:17:03,330 you're still possibly going 378 378 00:17:03,330 --> 00:17:05,210 to get a stack overflow exception 379 379 00:17:05,210 --> 00:17:07,700 because you're not hitting that breaking condition. 380 380 00:17:07,700 --> 00:17:10,100 So, even if you have a breaking condition, 381 381 00:17:10,100 --> 00:17:11,883 if you call the recursive method 382 382 00:17:11,883 --> 00:17:14,400 with something that's going to cause the method 383 383 00:17:14,400 --> 00:17:16,650 to invoke itself a million times, 384 384 00:17:16,650 --> 00:17:18,450 you're gonna get a stack overflow error. 385 385 00:17:18,450 --> 00:17:20,080 So, just keep that in mind. 386 386 00:17:20,080 --> 00:17:23,280 Now, this is a way around this potential blowing 387 387 00:17:23,280 --> 00:17:25,620 of the stack, it's called tail recursion 388 388 00:17:25,620 --> 00:17:27,840 but we're not going to see that for two reasons. 389 389 00:17:27,840 --> 00:17:30,620 First of all, none of the algorithms we look at, 390 390 00:17:30,620 --> 00:17:33,810 none of the implementations use tail recursion 391 391 00:17:33,810 --> 00:17:36,410 but the second and perhaps more important reason 392 392 00:17:36,410 --> 00:17:38,700 for Java is that the Java compiler 393 393 00:17:38,700 --> 00:17:40,710 doesn't use tail recursion, 394 394 00:17:40,710 --> 00:17:43,400 so we can use that type of recursion in Java. 395 395 00:17:43,400 --> 00:17:45,310 I'm just mentioning it to make you aware 396 396 00:17:45,310 --> 00:17:48,170 that it exists and if you wanna read up on it yourself, 397 397 00:17:48,170 --> 00:17:50,420 I've linked to a Dr. Dobbs article 398 398 00:17:50,420 --> 00:17:52,150 in the Resources section, 399 399 00:17:52,150 --> 00:17:54,660 so if you're interested in reading about tail recursion 400 400 00:17:54,660 --> 00:17:57,900 in Java, you can go ahead and take a look at that article. 401 401 00:17:57,900 --> 00:18:00,830 Anyway, I hope that this has refreshed your memory 402 402 00:18:00,830 --> 00:18:03,300 about recursion and now that we're all on the same page, 403 403 00:18:03,300 --> 00:18:06,830 we're gonna move on and look at a recursive sort algorithm 404 404 00:18:06,830 --> 00:18:08,100 called merge sort. 405 405 00:18:08,100 --> 00:18:09,650 I'll see you in the next video. 34570