WEBVTT 00:00.650 --> 00:09.690 In this lecture I want to go over another way to you by using functions and it's called recursion. 00:09.930 --> 00:17.320 So you may have seen in one of your math classes the function defined by using itself. 00:17.340 --> 00:21.660 So an example of that is factorial. 00:21.660 --> 00:25.300 So if you had five factorial. 00:25.650 --> 00:37.190 What that really means is five times four times three times two times what. 00:37.470 --> 00:47.760 Or you may have seen it like five times four factorial. 00:48.370 --> 00:50.520 And these are the same. 00:50.530 --> 00:56.760 So this is equivalent to this. 00:57.000 --> 01:01.850 Well we can actually do this in C++ as well. 01:01.860 --> 01:11.780 So say we have this factorial function that I wrote here and right now it's not implemented. 01:11.830 --> 01:18.760 This is called Stebbing by the way by actually having kind of a default sort of implementation which 01:18.770 --> 01:30.920 we're turning zero here in Maine we have this x and we're outputting the factorial of whatever the integer 01:30.920 --> 01:39.960 is in the actual factorial value right now it's is going to print out the factorial 5 0 is obviously 01:39.960 --> 01:40.940 wrong. 01:41.700 --> 01:50.830 But let's actually use recursion which means rushy going to call ourselves in this function. 01:50.850 --> 01:55.870 So how you do that is we'll say. 01:55.980 --> 02:00.540 So factorial in this case is just the number. 02:00.540 --> 02:04.330 So it be five in this case time. 02:04.350 --> 02:13.110 The factorial of the number minus 1 or 8. 02:13.120 --> 02:16.180 So just like here. 02:16.240 --> 02:23.480 So it's the number multiplied by the next lower number. 02:23.530 --> 02:28.160 So for in this case factorial. 02:28.190 --> 02:31.100 So that's exactly what we did here. 02:31.100 --> 02:38.110 However there's somewhat of a problem here because how do you know when to stop. 02:38.150 --> 02:46.730 So we still need to have a condition that says here's when you stop calling yourself. 02:46.760 --> 02:56.070 So this is kind of you'll see recursion in the following form you always have kind of general case which 02:56.070 --> 02:59.940 is this is just return. 03:00.020 --> 03:10.700 Then in this case the number times itself and given the parameter the number minus one and you always 03:10.700 --> 03:13.520 have the base case so in the base case. 03:13.550 --> 03:15.800 So what is one factorial. 03:16.010 --> 03:18.580 Well one factorials just one right. 03:18.590 --> 03:24.900 So here our base case will be the number if the number is 1. 03:25.100 --> 03:32.400 Then we're just going to return 1. 03:32.420 --> 03:34.800 So that's kind of it. 03:34.800 --> 03:40.770 So we have the base case is if that number is 1 we just return 1. 03:40.770 --> 03:46.650 Because 1 factorial is just one in fact zero factorial is also one. 03:46.690 --> 03:54.850 But we're going to stop here at 1 and you have the general case right here which is what actually does 03:54.850 --> 03:55.950 the recursion. 03:56.170 --> 04:02.220 Recursion and that actually calls itself with a lower number. 04:02.260 --> 04:14.390 So if we run this so we see the factorial of 5 is 120. 04:14.400 --> 04:16.650 So how did this work. 04:16.650 --> 04:19.820 There's no loop it's a while loop right. 04:20.290 --> 04:26.820 Or for loop or do while loop and it's because it's sort of stacks. 04:26.820 --> 04:30.090 So the first time it gets called. 04:30.300 --> 04:36.290 So you're safe factorial of in this case 5 and then come here. 04:37.260 --> 04:43.090 And say five times vectorial four and they'll call it again. 04:43.170 --> 04:47.490 And now the number is four four is not equal to 1. 04:47.490 --> 04:52.460 So to say four times factorial of three. 04:52.500 --> 04:53.980 So the number minus. 04:54.080 --> 04:55.070 Right. 04:55.310 --> 04:57.040 Then go back up here. 04:57.130 --> 05:03.730 Three three is not equal to one so three times the factorial of two. 05:03.840 --> 05:10.220 And then again two times vectorial 1 One is is equal to one. 05:10.240 --> 05:17.070 Now we kind of return off this giant stack that we've been making. 05:17.330 --> 05:21.620 And then finally the base case is really the stopping point. 05:21.650 --> 05:28.390 So now it stops everything kind of returns back and then it sort of unravels like this one. 05:28.460 --> 05:32.210 And then times two times three times four times five. 05:32.270 --> 05:35.870 All in all in here. 05:36.300 --> 05:38.970 So this is very confusing at first. 05:38.980 --> 05:48.000 And I remember having kind of a problem with recursion for and I find that when I tutor students a lot 05:48.000 --> 05:55.330 of universities really emphasize looping by recursion or the bigger universities often. 05:55.470 --> 06:05.460 And I think that's usually because there are a lot of applications of it in many theories but I tend 06:05.460 --> 06:11.920 not to ever use recursion because in practice it really doesn't come up that often actually. 06:12.060 --> 06:21.500 And not only that I find it like I said it's quite confusing and it's it's also actually painfully inefficient. 06:22.190 --> 06:29.810 It's not it's not very fast if you really start diving deep into your current stack. 06:29.820 --> 06:32.900 But Allah you make up your own mind about it. 06:33.010 --> 06:37.700 And we really present this here to you for completeness sake. 06:38.190 --> 06:41.390 So in the next lecture we're going to do some practice.