WEBVTT X-TIMESTAMP-MAP=LOCAL:00:00:00.000,MPEGTS:900000 00:00:03.430 --> 00:00:05.290 CARTER ZENKE: OK, well, hello one and all. 00:00:05.290 --> 00:00:07.520 It is so good to see you here over Zoom today. 00:00:07.520 --> 00:00:08.710 My name is Carter Zenke. 00:00:08.710 --> 00:00:11.080 I am CS50's preceptor here on campus. 00:00:11.080 --> 00:00:12.610 I'd love to see you all over Zoom. 00:00:12.610 --> 00:00:15.730 I thought we'd do is beginning with a bit of an unusual thing for Zoom, 00:00:15.730 --> 00:00:19.360 which is on, the count of three, everyone unmute and say hello. 00:00:19.360 --> 00:00:23.450 We'll hear a chorus of voices, and we'll all be here together in this Zoom room. 00:00:23.450 --> 00:00:26.830 So again, on the count of three, feel free to unmute and you all say hello. 00:00:26.830 --> 00:00:31.030 1, 2, 3, unmute and say, hello. 00:00:31.030 --> 00:00:32.940 AUDIENCE: Hello. 00:00:32.940 --> 00:00:34.930 CARTER ZENKE: Hello. 00:00:34.930 --> 00:00:38.770 All right, it's so good to hear your wonderful chorus of voices. 00:00:38.770 --> 00:00:42.130 We're here today for a CS50 section, and the goal of sections 00:00:42.130 --> 00:00:46.390 will be to review lecture content interactively, to ask questions, 00:00:46.390 --> 00:00:47.800 to dive into exercises. 00:00:47.800 --> 00:00:50.090 And so today what we'll do is do exactly that. 00:00:50.090 --> 00:00:51.660 We'll dive into algorithms. 00:00:51.660 --> 00:00:53.410 We're doing some things more interactively 00:00:53.410 --> 00:00:55.827 and talking amongst each other for how we might solve some 00:00:55.827 --> 00:00:57.730 of these problems in computer science. 00:01:00.280 --> 00:01:01.030 All right, sorry. 00:01:01.030 --> 00:01:03.700 Hello, everyone, I was unmuted. 00:01:03.700 --> 00:01:04.370 I was muted. 00:01:04.370 --> 00:01:07.870 So here what we're going to do is talk about CS50 section. 00:01:07.870 --> 00:01:10.240 So the goal of section is really to dive into lecture 00:01:10.240 --> 00:01:14.530 content interactively, to review content, to ask questions, 00:01:14.530 --> 00:01:17.120 to do so through exercises and through each other. 00:01:17.120 --> 00:01:20.230 And so today we'll be diving into algorithms and data structures 00:01:20.230 --> 00:01:23.630 and a little bit more in terms of recursion as well. 00:01:23.630 --> 00:01:27.530 So let's begin, and let's see a few questions for today. 00:01:27.530 --> 00:01:31.840 So here, our first question is going to be, how can we compare algorithms? 00:01:31.840 --> 00:01:34.240 In lecture, we saw binary search. 00:01:34.240 --> 00:01:36.220 We saw linear search. 00:01:36.220 --> 00:01:39.280 We also saw things like selection sort and bubble sort. 00:01:39.280 --> 00:01:41.650 So how should we compare algorithms and figure out 00:01:41.650 --> 00:01:44.615 which one's better than the other for which case. 00:01:44.615 --> 00:01:46.240 We're also going to talk about structs. 00:01:46.240 --> 00:01:47.890 Why are structs useful? 00:01:47.890 --> 00:01:49.330 When would we even use them? 00:01:49.330 --> 00:01:51.310 And we'll then talk about recursion. 00:01:51.310 --> 00:01:52.480 What is recursion? 00:01:52.480 --> 00:01:54.550 How do we build our own recursive algorithms, 00:01:54.550 --> 00:01:56.530 and have an exercise for ourselves and actually 00:01:56.530 --> 00:01:59.390 write our own recursive algorithm here. 00:01:59.390 --> 00:02:02.980 So let's dive first into this idea of how do we compare algorithms. 00:02:02.980 --> 00:02:07.560 So we saw in lecture this idea of trying to search for some value. 00:02:07.560 --> 00:02:11.830 So here I have maybe an array of different colors from this white color 00:02:11.830 --> 00:02:14.050 here to this dark green color. 00:02:14.050 --> 00:02:18.230 And let's say I want to find the color white in this array. 00:02:18.230 --> 00:02:21.210 Now, knowing we have some indices here, like 0, 00:02:21.210 --> 00:02:27.400 1, 2, 3, 4, 5, and 6, where is this white color in this array? 00:02:27.400 --> 00:02:30.460 If you have to type in the chat, where is the white color in this array? 00:02:30.460 --> 00:02:32.850 What index is it at? 00:02:32.850 --> 00:02:35.310 OK, so I'm seeing 2, right? 00:02:35.310 --> 00:02:37.020 And it seems pretty obvious here. 00:02:37.020 --> 00:02:39.780 We can just see that this white color is right here 00:02:39.780 --> 00:02:42.870 in this third spot but index 2. 00:02:42.870 --> 00:02:46.050 And maybe, how would we know that this is there? 00:02:46.050 --> 00:02:48.120 We eyeball it as humans. 00:02:48.120 --> 00:02:50.490 But a computer doesn't necessarily have access 00:02:50.490 --> 00:02:52.470 to this entire array of information. 00:02:52.470 --> 00:02:54.820 It can only look at one thing at a time. 00:02:54.820 --> 00:02:57.720 And so going metaphorically, we might think of the computer 00:02:57.720 --> 00:03:00.780 as shining a spotlight on some numbers as we go through 00:03:00.780 --> 00:03:03.190 and try to find this white color. 00:03:03.190 --> 00:03:06.030 So if we're doing linear search here, trying 00:03:06.030 --> 00:03:10.080 to search this array from start to back, we might start on, 00:03:10.080 --> 00:03:12.120 let's say, the left side of this array, right? 00:03:12.120 --> 00:03:14.700 We might go to that very first location, index 0. 00:03:14.700 --> 00:03:17.550 So we'd shine our spotlight on that color there. 00:03:17.550 --> 00:03:18.450 Is this white? 00:03:18.450 --> 00:03:21.660 Have we found our color? 00:03:21.660 --> 00:03:23.850 I'm seeing some head nods. 00:03:23.850 --> 00:03:25.290 Maybe in the chat, I'm seeing no. 00:03:25.290 --> 00:03:28.270 This is not the color white, so what are we going to do next? 00:03:28.270 --> 00:03:32.370 Which number should we go to after 0, if we're doing linear search? 00:03:32.370 --> 00:03:33.725 I'm seeing some 1's, right? 00:03:33.725 --> 00:03:35.350 OK, let's go to 1 and see what's there. 00:03:35.350 --> 00:03:36.930 So let's shine our spotlight there. 00:03:36.930 --> 00:03:39.510 And that is not white either. 00:03:39.510 --> 00:03:41.100 Maybe we're getting closer. 00:03:41.100 --> 00:03:41.850 Maybe not. 00:03:41.850 --> 00:03:42.930 We don't quite know. 00:03:42.930 --> 00:03:44.910 What's the next one to go to though? 00:03:44.910 --> 00:03:45.990 Index 2. 00:03:45.990 --> 00:03:47.070 So let's go to 2 now. 00:03:47.070 --> 00:03:49.650 So let's go from 1 to 2, adding 1 to our index. 00:03:49.650 --> 00:03:51.780 And oh, there is the color white. 00:03:51.780 --> 00:03:53.490 So we found it here. 00:03:53.490 --> 00:03:57.450 Now, how many steps did it take us to do this linear search to find 00:03:57.450 --> 00:03:59.100 the color white? 00:03:59.100 --> 00:04:00.150 I'm seeing three steps. 00:04:00.150 --> 00:04:01.483 OK, so keep that number in mind. 00:04:01.483 --> 00:04:04.860 It took us three steps to find white using linear search here. 00:04:04.860 --> 00:04:08.070 All right, so that's one algorithm we could use 00:04:08.070 --> 00:04:10.770 to find this color white in this array. 00:04:10.770 --> 00:04:13.780 But now let's say this array is sorted. 00:04:13.780 --> 00:04:17.130 So we're going from maybe light to dark green now. 00:04:17.130 --> 00:04:19.920 And we want to, again, find the color white. 00:04:19.920 --> 00:04:22.890 But now that the array is sorted, it enables 00:04:22.890 --> 00:04:27.450 this new algorithm called binary search we saw in lecture and through a phone 00:04:27.450 --> 00:04:28.920 book example, right? 00:04:28.920 --> 00:04:31.322 So if we're going to dim the lights again, 00:04:31.322 --> 00:04:33.030 we have to shine our spotlight somewhere. 00:04:33.030 --> 00:04:36.060 Now, where should we first shine our light 00:04:36.060 --> 00:04:41.010 if we're looking for this first element in binary search now? 00:04:41.010 --> 00:04:43.770 I'm seeing this idea of the middle, OK. 00:04:43.770 --> 00:04:46.300 We're trying to find the middle of this array. 00:04:46.300 --> 00:04:49.440 And if we know that we have-- let's go back a little bit-- 00:04:49.440 --> 00:04:54.810 index 6, all the way on this side, maybe our middle index 00:04:54.810 --> 00:04:57.060 would be 6 divided by 2. 00:04:57.060 --> 00:04:58.230 So 3, right? 00:04:58.230 --> 00:05:00.130 That will be the middle index here. 00:05:00.130 --> 00:05:00.900 So let's go to 3. 00:05:00.900 --> 00:05:02.610 So we'll dim the lights. 00:05:02.610 --> 00:05:04.850 We'll then look at 3. 00:05:04.850 --> 00:05:08.830 Now, is 3 white? 00:05:08.830 --> 00:05:10.950 I'm seeing no, right? 00:05:10.950 --> 00:05:12.800 So where should we look now? 00:05:12.800 --> 00:05:16.910 If we know that we're sorting our array from light to dark, 00:05:16.910 --> 00:05:18.350 we might want to look left, right? 00:05:18.350 --> 00:05:21.020 But at what index should we look now? 00:05:21.020 --> 00:05:22.890 We might divide 3 in half again. 00:05:22.890 --> 00:05:26.300 So 3 divided by 2 is-- well, it's 1.5. 00:05:26.300 --> 00:05:29.010 Maybe we round down and go to one, right? 00:05:29.010 --> 00:05:31.730 So let's go from 3 down to 1. 00:05:31.730 --> 00:05:33.530 And we're not quite there. 00:05:33.530 --> 00:05:39.970 Where do we go again now if we're sorting from light to dark green? 00:05:39.970 --> 00:05:41.400 I'm seeing some left in the chat. 00:05:41.400 --> 00:05:42.608 OK, let's go one on the left. 00:05:42.608 --> 00:05:46.210 1 divided by 2 is 0.5, but we can't go to index 0.5. 00:05:46.210 --> 00:05:48.130 Let's round down, and let's go to 0. 00:05:48.130 --> 00:05:53.110 So we found white here now at this 0th index. 00:05:53.110 --> 00:05:58.150 And now, again, how many steps did this binary search take in this case? 00:05:58.150 --> 00:06:00.100 Again, took us three steps, right? 00:06:00.100 --> 00:06:03.130 So if we're trying to compare these two algorithms, 00:06:03.130 --> 00:06:05.140 we might talk about their running time, which 00:06:05.140 --> 00:06:10.270 is how many steps they take for us to find the number or color that we're 00:06:10.270 --> 00:06:12.430 looking for in this case. 00:06:12.430 --> 00:06:15.760 Well, we might compare linear search in binary search like this. 00:06:15.760 --> 00:06:18.590 How many steps did they take us in this case? 00:06:18.590 --> 00:06:21.220 And so again, linear search, how many steps does that 00:06:21.220 --> 00:06:25.080 take us for this particular case here? 00:06:25.080 --> 00:06:26.610 I'm seeing some 3s. 00:06:26.610 --> 00:06:28.770 So linear search took us three steps. 00:06:28.770 --> 00:06:33.480 And binary search, how many steps did that take us again? 00:06:33.480 --> 00:06:35.850 Also took us three. 00:06:35.850 --> 00:06:39.695 OK, so which algorithm is better than the other? 00:06:39.695 --> 00:06:41.820 Anyone want to raise their hand, we can call on you 00:06:41.820 --> 00:06:44.850 and maybe tell us which algorithm you think is better here? 00:06:50.120 --> 00:06:52.220 Or maybe type in the chat if you'd like. 00:06:52.220 --> 00:06:53.915 Which algorithm would you choose? 00:06:56.510 --> 00:07:00.040 So I'm seeing some binary. 00:07:00.040 --> 00:07:02.680 And now my question here is, why would we choose binary, right? 00:07:02.680 --> 00:07:06.530 Each one, linear search and binary search, took three steps. 00:07:06.530 --> 00:07:10.680 So is one really better than the other? 00:07:10.680 --> 00:07:13.480 Maybe on the chat, what do you think? 00:07:13.480 --> 00:07:15.620 So I'm seeing binary search is more dynamic. 00:07:18.555 --> 00:07:19.805 It depends on the arrangement. 00:07:19.805 --> 00:07:23.450 So there's this idea that the input we had right now 00:07:23.450 --> 00:07:25.400 was a very particular input. 00:07:25.400 --> 00:07:28.790 And for this single input, linear search and binary search 00:07:28.790 --> 00:07:30.530 did take the same number of steps. 00:07:30.530 --> 00:07:32.780 But this isn't quite the question we want 00:07:32.780 --> 00:07:36.650 to be asking when we're talking about running time for algorithms. 00:07:36.650 --> 00:07:39.650 Often, what we want to ask instead is not 00:07:39.650 --> 00:07:42.150 how many steps we take for a single input 00:07:42.150 --> 00:07:47.000 but, in general, for any input, what is the most number of steps 00:07:47.000 --> 00:07:49.580 my algorithm will ever take, right? 00:07:49.580 --> 00:07:52.190 And another way of asking this question is, for maybe 00:07:52.190 --> 00:07:55.070 the worst case input, if I were to give my algorithm 00:07:55.070 --> 00:08:02.060 a completely unsorted list, what number of steps would always run faster then? 00:08:02.060 --> 00:08:03.740 So let's take a look at this. 00:08:03.740 --> 00:08:06.530 If we call this the upper bound for our algorithm, 00:08:06.530 --> 00:08:11.360 meaning that this algorithm will never run slower than this number of steps, 00:08:11.360 --> 00:08:14.840 we might say that linear search takes how many steps? 00:08:14.840 --> 00:08:18.980 Let's assume we have maybe n elements in our array. 00:08:18.980 --> 00:08:22.010 In this case, this most recent example, we had seven. 00:08:22.010 --> 00:08:26.150 How many steps would linear search take in this case? 00:08:26.150 --> 00:08:30.080 So I'm seeing about n steps, right? 00:08:30.080 --> 00:08:33.500 Let's say we have seven elements, it would take us maybe seven steps 00:08:33.500 --> 00:08:35.960 in the worst case to find that number if it's all 00:08:35.960 --> 00:08:38.190 the way at the very end of our array. 00:08:38.190 --> 00:08:40.700 So linear search might take 7 steps in the worst case. 00:08:40.700 --> 00:08:42.740 Or in general, if we have n elements, it might 00:08:42.740 --> 00:08:47.540 take n steps, one step for every element in that array. 00:08:47.540 --> 00:08:50.930 But binary search though might be a little different 00:08:50.930 --> 00:08:53.420 because we're dividing the problem in 1/2 and 1/2 and 1/2. 00:08:53.420 --> 00:08:56.690 And so what are we seeing now? 00:08:56.690 --> 00:09:02.210 So I'm seeing maybe it takes n over two steps, and that's a little close. 00:09:02.210 --> 00:09:08.488 Any other ideas for how many steps binary search might take in this case? 00:09:08.488 --> 00:09:11.320 I'm seeing n minus 1. 00:09:11.320 --> 00:09:13.450 I'm seeing log n. 00:09:13.450 --> 00:09:17.140 And indeed, so binary search would take about log n steps 00:09:17.140 --> 00:09:20.620 if we had n number of elements to search for here. 00:09:20.620 --> 00:09:23.890 And people who said n over 2, you're not quite wrong, right, 00:09:23.890 --> 00:09:28.300 because what we can do is we can take our array of seven elements. 00:09:28.300 --> 00:09:30.460 We can divide it in 1/2. 00:09:30.460 --> 00:09:31.810 We've looked at one element. 00:09:31.810 --> 00:09:35.650 Let's divide it in 1/2 again and divide it in 1/2 again. 00:09:35.650 --> 00:09:38.470 And this idea of dividing things in 1/2, in 1/2, in 1/2 00:09:38.470 --> 00:09:43.390 is a logarithm that we need twice as many elements to do one more 00:09:43.390 --> 00:09:45.040 step in our algorithm now. 00:09:45.040 --> 00:09:48.790 So binary search in this case, in the very worst case, the upper bound 00:09:48.790 --> 00:09:51.550 of the binary search algorithm is log of n steps. 00:09:51.550 --> 00:09:54.640 And now the question becomes, which one would you rather do? 00:09:54.640 --> 00:09:59.900 Would you rather do linear search, or would you rather do binary search? 00:09:59.900 --> 00:10:01.760 And so I'm seeing binary, right, because we 00:10:01.760 --> 00:10:05.030 know that, for these really worst case inputs, 00:10:05.030 --> 00:10:08.120 binary search might, in fact, be better. 00:10:08.120 --> 00:10:12.560 And this is OK for now, and we can talk about things in terms 00:10:12.560 --> 00:10:14.030 of the number of steps they take. 00:10:14.030 --> 00:10:16.940 But in computer science, to be a little more precise, 00:10:16.940 --> 00:10:19.850 we try to say that something is in the running time, 00:10:19.850 --> 00:10:21.742 on the order of something. 00:10:21.742 --> 00:10:23.450 And this is because, in computer science, 00:10:23.450 --> 00:10:26.480 we're often not trying to search an array of seven elements 00:10:26.480 --> 00:10:28.010 or an array of eight elements. 00:10:28.010 --> 00:10:31.160 We're often trying to search an array of maybe a billion elements 00:10:31.160 --> 00:10:32.420 or a million elements. 00:10:32.420 --> 00:10:34.940 And so who cares if something takes maybe a billion 00:10:34.940 --> 00:10:37.520 plus 1 steps or a billion minus 1 steps. 00:10:37.520 --> 00:10:40.970 It's on the order of about a billion steps, right? 00:10:40.970 --> 00:10:44.780 And so we saw in lecture this idea of these algorithms that can 00:10:44.780 --> 00:10:46.700 take a certain amount of running time. 00:10:46.700 --> 00:10:50.120 And here, if we look at the bottom of our graph here, 00:10:50.120 --> 00:10:55.430 we have the size of the problem going up as we go to this side and the time 00:10:55.430 --> 00:10:58.710 to solve that problem going up as we go up as well. 00:10:58.710 --> 00:11:03.110 So notice how maybe we have two different algorithms, this red line 00:11:03.110 --> 00:11:08.030 and this yellow line, one taking n steps, one taking n over 2 steps, 00:11:08.030 --> 00:11:13.590 this other one here taking log 2 of n steps here. 00:11:13.590 --> 00:11:15.990 Now, that's all fine and good. 00:11:15.990 --> 00:11:18.260 We can be that precise, but often, when working 00:11:18.260 --> 00:11:21.140 with a billion elements, a million elements, and so on, 00:11:21.140 --> 00:11:26.210 we might talk about things being on the order of some number here, 00:11:26.210 --> 00:11:32.390 often n or log n, removing those terms like divided by 2 or plus 2 or minus 2, 00:11:32.390 --> 00:11:33.420 and so on. 00:11:33.420 --> 00:11:36.350 So here, we might say that this is the upper bound, noting that 00:11:36.350 --> 00:11:38.450 with the big O notation. 00:11:38.450 --> 00:11:41.060 And when we do that, we get rid of that division. 00:11:41.060 --> 00:11:43.665 We say, OK, we don't need that divided by 2 there. 00:11:43.665 --> 00:11:46.040 And then similarly, we might also do something like this. 00:11:46.040 --> 00:11:50.690 We might say, if we zoom out, these n over 2 and the n, 00:11:50.690 --> 00:11:51.840 they look very similar. 00:11:51.840 --> 00:11:55.490 So let's maybe call those both O of n and the second one here that still 00:11:55.490 --> 00:11:59.280 looks very different log n over here. 00:11:59.280 --> 00:12:03.080 So we might then characterize linear search and binary search like this 00:12:03.080 --> 00:12:09.060 as being in big O of n and big O of log n, respectively. 00:12:09.060 --> 00:12:12.240 So what questions do you all have on this big O 00:12:12.240 --> 00:12:13.880 notation or these running times? 00:12:13.880 --> 00:12:15.710 Happy to help answer some of these. 00:12:25.380 --> 00:12:29.132 All right, seeing none so far. 00:12:29.132 --> 00:12:30.840 Oh, I'm seeing some question in the chat. 00:12:33.390 --> 00:12:36.580 Does binary look at all the possibilities? 00:12:36.580 --> 00:12:40.230 So binary search doesn't necessarily look at all of the possibilities. 00:12:40.230 --> 00:12:45.720 What it does instead is it takes for granted that a list is sorted. 00:12:45.720 --> 00:12:49.620 And because of that we don't need to look at every possible element. 00:12:49.620 --> 00:12:52.020 If we know that we go to the middle one and we 00:12:52.020 --> 00:12:55.920 find maybe a number that's too high or a color that's too dark, 00:12:55.920 --> 00:12:58.290 well, we know we should look to the left of that number. 00:12:58.290 --> 00:12:59.998 If though we're looking for a number that 00:12:59.998 --> 00:13:02.910 is greater than that number or darker than that color, 00:13:02.910 --> 00:13:05.820 we can look to the right and keep dividing in 1/2 and in 1/2 again. 00:13:05.820 --> 00:13:09.870 And so binary search doesn't take n steps, one for every element. 00:13:09.870 --> 00:13:14.235 It only takes log n of steps, dividing in 1/2 and in 1/2 and in 1/2 again. 00:13:18.070 --> 00:13:21.280 I'm also seeing what if it's an unordered list? 00:13:21.280 --> 00:13:23.870 What will be the running time of binary search? 00:13:23.870 --> 00:13:26.050 And by unordered perhaps we mean unsorted. 00:13:26.050 --> 00:13:30.100 So let's say maybe our list is not maybe sorted from light to dark 00:13:30.100 --> 00:13:32.350 or from lowest to highest, and so on. 00:13:32.350 --> 00:13:35.960 Well, in that case, binary search breaks down, doesn't quite work. 00:13:35.960 --> 00:13:39.610 So the prerequisite for binary search is that our list is indeed sorted. 00:13:39.610 --> 00:13:43.187 If it's not sorted, what will happen is it will go to that middle element, 00:13:43.187 --> 00:13:46.270 and we won't really know anything about where the other elements might be. 00:13:46.270 --> 00:13:48.340 We won't know if we can look left or look right. 00:13:48.340 --> 00:13:50.780 And so binary search really breaks down in that case. 00:13:50.780 --> 00:13:54.850 And we're forced to use linear search of looking at every element step by step 00:13:54.850 --> 00:13:58.240 by step here. 00:13:58.240 --> 00:14:00.790 And a question about what is the use of big O notation? 00:14:00.790 --> 00:14:03.830 Why would we even care about having this big O notation here? 00:14:03.830 --> 00:14:05.680 Well, one reason we might care about this 00:14:05.680 --> 00:14:08.230 is because we care about this question earlier about, 00:14:08.230 --> 00:14:12.790 for any input, what is the most number of steps my algorithm will ever take? 00:14:12.790 --> 00:14:15.670 What is the very worst case running time of this algorithm? 00:14:15.670 --> 00:14:17.860 And so this big O notation is saying, OK, this 00:14:17.860 --> 00:14:23.560 is going to be the number of steps your algorithm will always run faster than, 00:14:23.560 --> 00:14:26.440 so to speak, will never run more than this number of steps, 00:14:26.440 --> 00:14:31.580 in general, on the order of this many steps, so to speak. 00:14:31.580 --> 00:14:33.770 All right, so let's keep going. 00:14:33.770 --> 00:14:37.890 And we have this question of what is the most number of steps 00:14:37.890 --> 00:14:39.140 this algorithm will ever take? 00:14:39.140 --> 00:14:41.510 But also, we can ask another question of, 00:14:41.510 --> 00:14:44.810 what is the least number of tests my algorithm could ever take? 00:14:44.810 --> 00:14:47.780 So we answered this one already using big O notation. 00:14:47.780 --> 00:14:52.640 But using omega notation, this different Greek symbol, this other question. 00:14:52.640 --> 00:14:55.520 What is the least number of tests my algorithm will ever take? 00:14:55.520 --> 00:14:58.790 Or another way of saying this is, for the best case input, 00:14:58.790 --> 00:15:01.190 how many steps will my algorithm take? 00:15:01.190 --> 00:15:05.120 And so for example here, we could go to linear search and binary search, 00:15:05.120 --> 00:15:10.590 and each one maybe takes one step in the very best case. 00:15:10.590 --> 00:15:12.650 And what kind of case would this be where 00:15:12.650 --> 00:15:16.340 linear search takes one step and binary search takes one step? 00:15:16.340 --> 00:15:20.040 What kind of input would we give here? 00:15:20.040 --> 00:15:21.090 Anyone in the chat? 00:15:26.730 --> 00:15:30.220 Maybe another way of phrasing this is, at what point 00:15:30.220 --> 00:15:33.430 will we get lucky with linear search or binary search? 00:15:37.280 --> 00:15:41.180 Yeah, so maybe-- I'm seeing-- so maybe with linear search, 00:15:41.180 --> 00:15:44.540 maybe our element is that very first one at the zero index, right? 00:15:44.540 --> 00:15:46.550 In that case, linear search took one step. 00:15:46.550 --> 00:15:48.020 We can end early. 00:15:48.020 --> 00:15:51.502 And similarly, for binary search, maybe our element is right in the middle. 00:15:51.502 --> 00:15:54.210 So we can just go right to the middle and find the element there. 00:15:54.210 --> 00:15:57.920 So this is why, in the best case, our lower bound for linear search 00:15:57.920 --> 00:15:59.930 and binary search will be one step. 00:15:59.930 --> 00:16:05.750 These algorithms will, in effect, will never be, let's see, 00:16:05.750 --> 00:16:09.530 never be slower than-- 00:16:09.530 --> 00:16:11.930 well, let me think about that. 00:16:11.930 --> 00:16:15.960 In the very best case, lower bound will be one step and one step here. 00:16:15.960 --> 00:16:19.640 And so what we often use for this notation is this omega of 1. 00:16:19.640 --> 00:16:22.340 So we're saying this is on the order of about one step 00:16:22.340 --> 00:16:28.120 or a finite number of steps for linear search and binary search here. 00:16:28.120 --> 00:16:32.995 All right, so what questions do you all have on this omega notation? 00:16:44.280 --> 00:16:47.310 All right, so seeing no questions here, let's keep going. 00:16:47.310 --> 00:16:48.510 And let's try to find-- 00:16:48.510 --> 00:16:51.000 let's try to analyze the runtime of a new algorithm 00:16:51.000 --> 00:16:54.120 that we did see in lecture, of course, one called selection sort, right? 00:16:54.120 --> 00:16:57.900 So in selection sort, we want to basically go through every element 00:16:57.900 --> 00:16:59.290 and sort this list. 00:16:59.290 --> 00:17:02.520 And here we have an array that is currently unsorted. 00:17:02.520 --> 00:17:04.680 But we do want to sort it in the end. 00:17:04.680 --> 00:17:07.920 And selection sort has an algorithm that works like this. 00:17:07.920 --> 00:17:11.819 It will say, let's start by looking at that very first element, 00:17:11.819 --> 00:17:15.300 and let's go through and find the very smallest element in our list 00:17:15.300 --> 00:17:17.400 and put it at the very beginning now. 00:17:17.400 --> 00:17:23.348 So currently, if we can only look at one element, let's say this 5 here, 00:17:23.348 --> 00:17:25.140 well, that's currently the smallest number. 00:17:25.140 --> 00:17:27.119 But let's look at 3. 00:17:27.119 --> 00:17:28.500 Is 3 smaller than 5? 00:17:28.500 --> 00:17:29.685 Give me a yes or a no. 00:17:32.410 --> 00:17:33.790 Yeah, so 3 is smaller than 5. 00:17:33.790 --> 00:17:35.660 So 3 is our new smallest number. 00:17:35.660 --> 00:17:36.850 So let's go again. 00:17:36.850 --> 00:17:39.913 2 is certainly smaller than 3, and so is 1. 00:17:39.913 --> 00:17:41.830 And if we were to go through this entire list, 00:17:41.830 --> 00:17:46.850 we would see that 1 is indeed that smallest number here. 00:17:46.850 --> 00:17:51.660 So what do we do with 1 if we want to sort this list? 00:17:51.660 --> 00:17:53.160 We found the smallest one currently. 00:17:53.160 --> 00:17:54.390 Where do we put the 1? 00:17:57.100 --> 00:17:59.770 Move it to the very first element, or swap it with 5. 00:17:59.770 --> 00:18:04.660 So we'll say, let's put 1 where 5 is and 5 where 1 is. 00:18:04.660 --> 00:18:07.710 So now we know that 1 is in the right space. 00:18:07.710 --> 00:18:09.720 Now, our list is not quite sorted. 00:18:09.720 --> 00:18:11.760 We have 1, 3, 4, 8, 2, 5. 00:18:11.760 --> 00:18:13.770 That's not quite what we want yet. 00:18:13.770 --> 00:18:16.690 What we'll do instead is keep going through that list. 00:18:16.690 --> 00:18:20.310 We'll say, OK, well, let's find the smallest number in this list. 00:18:20.310 --> 00:18:22.590 3 seems pretty small. 00:18:22.590 --> 00:18:25.470 4 is higher, but 2 is smaller. 00:18:25.470 --> 00:18:29.230 And 2, right, as people are saying, is going to be our smallest number here. 00:18:29.230 --> 00:18:30.660 So what do we do with the 2 now? 00:18:33.520 --> 00:18:34.780 2 will swap with 3. 00:18:34.780 --> 00:18:38.530 So we'll put the 2 in the 3's place and the 3 in the 2's place. 00:18:38.530 --> 00:18:41.620 And now we're getting a little closer to having this list sorted. 00:18:41.620 --> 00:18:44.620 So what we'll do is we'll go ahead and find the next smallest 00:18:44.620 --> 00:18:46.610 number in the numbers that remain. 00:18:46.610 --> 00:18:49.810 We'll look at 4, 8, 3, 5, 7, and 6, and we'll 00:18:49.810 --> 00:18:52.115 find that ultimately 3 is that new smallest number. 00:18:52.115 --> 00:18:52.990 What do we do with 3? 00:18:52.990 --> 00:18:54.650 Swap it with 4, as people are saying. 00:18:54.650 --> 00:18:56.740 OK, now let's find the 4. 00:18:56.740 --> 00:18:58.930 Let's put that, top it with 8. 00:18:58.930 --> 00:19:02.530 Now, we'll find the next smallest, which will be 5. 00:19:02.530 --> 00:19:05.290 Then we'll find, in this case, 6. 00:19:05.290 --> 00:19:07.570 So 6 will go up here. 00:19:07.570 --> 00:19:10.570 And finally, we'll try to find the smallest again. 00:19:10.570 --> 00:19:11.320 That's 7. 00:19:11.320 --> 00:19:13.930 Smallest again, and that's 8. 00:19:13.930 --> 00:19:16.570 All right, so this is selection sort. 00:19:16.570 --> 00:19:20.830 And we might want to analyze the runtime of selection sort. 00:19:20.830 --> 00:19:24.550 How many steps does this take? 00:19:24.550 --> 00:19:29.470 If we were to give an upper bound in omega notation, or not omega, sorry, 00:19:29.470 --> 00:19:35.670 in big O notation, what would selection sort run in? 00:19:35.670 --> 00:19:41.770 If we're doing maybe a certain number of steps for every element, 00:19:41.770 --> 00:19:43.330 what might we do here? 00:19:45.900 --> 00:19:51.520 OK, so I'm seeing something like n squared. 00:19:51.520 --> 00:19:53.290 And let's get some intuition for this. 00:19:53.290 --> 00:19:56.220 So let's say, if we go back up to these slides here, 00:19:56.220 --> 00:20:00.560 notice how, if we go back to this unsorted list, 00:20:00.560 --> 00:20:06.380 we started by looking at the 5 and trying to find 00:20:06.380 --> 00:20:08.360 the very smallest element in this list. 00:20:08.360 --> 00:20:09.800 That took us n steps. 00:20:09.800 --> 00:20:12.450 We had to go through every element to find the smallest. 00:20:12.450 --> 00:20:14.310 That's n steps here. 00:20:14.310 --> 00:20:17.950 So n steps to put the 1 in the right place. 00:20:17.950 --> 00:20:20.820 But now we have to go through another about n steps 00:20:20.820 --> 00:20:23.400 to put the 2 in the right place. 00:20:23.400 --> 00:20:27.780 And have to go through another n steps put the 3 in the right place, 00:20:27.780 --> 00:20:30.430 and another n steps to put the 4 in the right place. 00:20:30.430 --> 00:20:35.510 And so we're doing n steps how many times? 00:20:35.510 --> 00:20:41.110 How many times are we doing n steps to find that smallest number? 00:20:41.110 --> 00:20:43.390 We're doing it n times or, in this case, 8, right? 00:20:43.390 --> 00:20:46.210 So if there are eight elements, we're doing it n times. 00:20:46.210 --> 00:20:51.670 So here, we're thinking of selection sort really is big O of n squared. 00:20:51.670 --> 00:20:59.310 For every element we're doing another n steps, n times n, about O of n squared. 00:20:59.310 --> 00:21:06.510 OK, now though, we need to figure out the omega notation, that lower bound. 00:21:06.510 --> 00:21:08.475 How could we figure that out? 00:21:11.680 --> 00:21:14.530 Or if we gave it maybe an already sorted list, in the best 00:21:14.530 --> 00:21:16.660 case, what might selection sort do? 00:21:20.400 --> 00:21:22.500 Yeah, so I'm seeing a few answers. 00:21:22.500 --> 00:21:24.120 I'm seeing O of 1. 00:21:24.120 --> 00:21:27.400 I'm seeing O of n, O of n squared. 00:21:27.400 --> 00:21:30.840 And in this case, if selection isn't optimized, 00:21:30.840 --> 00:21:34.080 selection sort will take an already sorted list, one 00:21:34.080 --> 00:21:36.780 that looks a bit like this, and still try to do those swaps, 00:21:36.780 --> 00:21:40.450 it'll take it a whole n steps to find that smallest number, 00:21:40.450 --> 00:21:42.840 put it in the right place, go to the next number, 00:21:42.840 --> 00:21:44.947 do another n steps to put it in the right place. 00:21:44.947 --> 00:21:48.030 And so selection sort isn't quite smart, at least as we've seen it so far. 00:21:48.030 --> 00:21:49.650 It isn't going to end early. 00:21:49.650 --> 00:21:53.130 And so selection sort will still be in omega of n 00:21:53.130 --> 00:21:57.630 squared, meaning that the upper bound and the lower bound for this algorithm 00:21:57.630 --> 00:21:59.140 are really the same. 00:21:59.140 --> 00:22:01.320 And that's where we might use this theta notation 00:22:01.320 --> 00:22:03.070 that I saw some people referencing earlier 00:22:03.070 --> 00:22:05.280 to say that these upper bounds and these lower bounds 00:22:05.280 --> 00:22:07.720 are the same in this instance. 00:22:07.720 --> 00:22:11.730 So what questions do you all have on upper bounds and lower bounds 00:22:11.730 --> 00:22:13.575 and selection sort in this case? 00:22:15.542 --> 00:22:17.500 So I'm seeing a question about how do we reason 00:22:17.500 --> 00:22:19.990 about spending time sorting a list in order to be 00:22:19.990 --> 00:22:21.740 able to use a faster search later on? 00:22:21.740 --> 00:22:22.700 It's a good question. 00:22:22.700 --> 00:22:27.010 So we saw that with binary search that's faster than linear search, 00:22:27.010 --> 00:22:29.560 but it takes time to sort something, right? 00:22:29.560 --> 00:22:31.010 So how do we reason about that? 00:22:31.010 --> 00:22:35.350 Well, we might do is figure out what are the upper bound and lower bound 00:22:35.350 --> 00:22:36.730 for our sorting algorithm? 00:22:36.730 --> 00:22:39.310 And are we willing to spend the amount of time 00:22:39.310 --> 00:22:43.280 to then get that much faster algorithm for searching later on? 00:22:43.280 --> 00:22:46.900 And if you are maybe often searching, maybe it 00:22:46.900 --> 00:22:51.400 makes sense to spend that time to sort first and then have that faster search. 00:22:51.400 --> 00:22:54.255 If though you're only searching occasionally or maybe 00:22:54.255 --> 00:22:56.380 you're not even really searching a data set at all, 00:22:56.380 --> 00:22:58.970 maybe it doesn't make sense to sort it in that case. 00:22:58.970 --> 00:23:01.150 So maybe it comes into play with what do you 00:23:01.150 --> 00:23:05.560 want to do with your list in that case. 00:23:05.560 --> 00:23:13.450 Yeah, and so I'm seeing what's the main difference between the big O notation 00:23:13.450 --> 00:23:14.750 and omega notation? 00:23:14.750 --> 00:23:18.530 So really, the main difference is that they're asking two different questions. 00:23:18.530 --> 00:23:22.180 The big O notation is asking, in the very worst case, 00:23:22.180 --> 00:23:25.450 how about how many steps will my algorithm take? 00:23:25.450 --> 00:23:29.530 The omega notation is asking, in the very best case, about how 00:23:29.530 --> 00:23:31.240 many steps of my algorithm take? 00:23:31.240 --> 00:23:34.600 And we often say that the big O notation symbolizes 00:23:34.600 --> 00:23:38.710 the upper bound for the algorithm, meaning that our algorithm will never 00:23:38.710 --> 00:23:40.780 run slower than this. 00:23:40.780 --> 00:23:43.420 And similarly, for the lower bound, we're 00:23:43.420 --> 00:23:46.870 saying that our algorithm will never run faster than this, 00:23:46.870 --> 00:23:52.080 will never run faster then, at least, the omega notation down here. 00:23:52.080 --> 00:23:55.550 Answer your question too about how do we use this in practice? 00:23:55.550 --> 00:23:57.560 Would we compare algorithms or things like that? 00:23:57.560 --> 00:23:58.640 And certainly, you would. 00:23:58.640 --> 00:24:01.800 So let's say you're working on an application and you want to figure out, 00:24:01.800 --> 00:24:05.390 is it worthwhile for me to use this algorithm or that algorithm? 00:24:05.390 --> 00:24:08.300 And often, what you'll do is, before you even write some code, 00:24:08.300 --> 00:24:10.770 you'll figure out what algorithm you want to use. 00:24:10.770 --> 00:24:14.450 And so these running times can be a clue to you what kind of algorithm 00:24:14.450 --> 00:24:16.468 is best for your particular data set. 00:24:16.468 --> 00:24:19.010 And once you know that, you can then go off and find the time 00:24:19.010 --> 00:24:20.370 to write that algorithm. 00:24:20.370 --> 00:24:22.760 But often, it's good to know which one to choose 00:24:22.760 --> 00:24:26.300 before you spend all that time writing the algorithm you want to write here. 00:24:29.340 --> 00:24:34.750 All right, so these are all really good questions. 00:24:34.750 --> 00:24:40.060 What we'll do now is spend just a bit of time on this idea of structs. 00:24:40.060 --> 00:24:44.980 So if we look at this idea of structs, we saw this newly in lecture this week 00:24:44.980 --> 00:24:49.330 where a struct is simply some combination of data types. 00:24:49.330 --> 00:24:52.360 And a question we might ask is, when would we even use structs? 00:24:52.360 --> 00:24:56.650 If we already have strings, we already have INTs, we already have Booleans, 00:24:56.650 --> 00:25:00.520 why do we need a struct, this new structure we could use in our program? 00:25:00.520 --> 00:25:04.690 And to that I might ask you, let's say, how would we represent maybe these two 00:25:04.690 --> 00:25:05.802 people in our program? 00:25:05.802 --> 00:25:07.510 Let's say we want to write a program that 00:25:07.510 --> 00:25:09.968 represents maybe political candidates, as you might work on 00:25:09.968 --> 00:25:11.350 in the problem set this week. 00:25:11.350 --> 00:25:13.090 How could we do this? 00:25:13.090 --> 00:25:18.870 Or what information would we store about these candidates? 00:25:18.870 --> 00:25:19.770 So I'm seeing names. 00:25:19.770 --> 00:25:21.463 We might want to store names. 00:25:21.463 --> 00:25:22.380 I'm seeing your party. 00:25:22.380 --> 00:25:24.030 Might want to store their party. 00:25:24.030 --> 00:25:28.640 Other things too I want to reference about these candidates here. 00:25:28.640 --> 00:25:34.370 Maybe gender, position, maybe their height, right? 00:25:34.370 --> 00:25:37.140 So there are lots of things we could store about these candidates 00:25:37.140 --> 00:25:39.120 to represent them in our data structure. 00:25:39.120 --> 00:25:42.200 And often, I would bet you that we can't represent a candidate 00:25:42.200 --> 00:25:43.940 with just a single data type. 00:25:43.940 --> 00:25:46.048 I could represent their name, but there's 00:25:46.048 --> 00:25:48.965 other information I want to couple with that or put together with that 00:25:48.965 --> 00:25:51.470 that I need to use a struct for. 00:25:51.470 --> 00:25:56.420 So for example, let's say we wanted to make this structure for candidates. 00:25:56.420 --> 00:26:01.760 We wanted to make this new type, so to speak, called candidate in our program. 00:26:01.760 --> 00:26:04.760 Well, what we could do is use this kind of syntax. 00:26:04.760 --> 00:26:09.758 We could say let's make ourselves, essentially, a new type, roughly 00:26:09.758 --> 00:26:12.050 a type, not necessarily a type like a string or an int, 00:26:12.050 --> 00:26:15.950 but a new combination data type we could use throughout our program. 00:26:15.950 --> 00:26:19.220 And this typedef is helpful because it's basically helping us define-- 00:26:19.220 --> 00:26:20.780 that's where the def comes from-- 00:26:20.780 --> 00:26:22.700 a new type, right? 00:26:22.700 --> 00:26:26.640 The next piece we see is this struct, that struct keyword at the very top 00:26:26.640 --> 00:26:27.140 there. 00:26:27.140 --> 00:26:31.070 And that's saying we're going to have some combination of basic types, 00:26:31.070 --> 00:26:35.610 like string and int, that will form our candidate here. 00:26:35.610 --> 00:26:39.840 So we'll have the name of that down below, our candidate right here. 00:26:39.840 --> 00:26:44.570 And then on the inside we'll say, what are the basic types that are inside 00:26:44.570 --> 00:26:45.480 of this structure? 00:26:45.480 --> 00:26:49.700 In this case, we'll have a candidate be maybe a string for their name 00:26:49.700 --> 00:26:51.770 and an integer for their votes. 00:26:51.770 --> 00:26:54.110 And these two pieces of data will be tied together 00:26:54.110 --> 00:26:58.290 in this new structure called a candidate. 00:26:58.290 --> 00:27:00.360 And this is helpful because we can actually 00:27:00.360 --> 00:27:05.100 have maybe a single variable that keeps track of both 00:27:05.100 --> 00:27:06.820 of these information at the same time. 00:27:06.820 --> 00:27:10.920 So let's say we want to make a new variable called president. 00:27:10.920 --> 00:27:14.430 Well, president has this type called candidate 00:27:14.430 --> 00:27:15.990 that we just defined earlier, right? 00:27:15.990 --> 00:27:20.280 And we know that a candidate has a name and a number of votes. 00:27:20.280 --> 00:27:23.313 So if we wanted to keep these two pieces of data together, their name 00:27:23.313 --> 00:27:24.730 and their votes, we could do this. 00:27:24.730 --> 00:27:28.110 We could say, maybe the president's name is Alyssa. 00:27:28.110 --> 00:27:30.280 And the president has maybe 10 votes. 00:27:30.280 --> 00:27:32.340 And so here we're using this new dot syntax, 00:27:32.340 --> 00:27:35.430 president.name gets the value Alyssa. 00:27:35.430 --> 00:27:38.530 And president.votes gets the value 10. 00:27:38.530 --> 00:27:43.470 And so in this single variable called president that is of type candidate, 00:27:43.470 --> 00:27:47.190 we are storing now a name and a number of votes 00:27:47.190 --> 00:27:50.570 close to each other in memory here. 00:27:50.570 --> 00:27:55.055 What questions do you all have on this syntax or what structs are so far? 00:27:58.490 --> 00:28:01.370 So your question about the maximum arguments for a struct, 00:28:01.370 --> 00:28:05.120 and maybe to go back here and show just some vocabulary. 00:28:05.120 --> 00:28:08.270 Here we often call this the attributes of a struct 00:28:08.270 --> 00:28:10.400 or the fields of the struct. 00:28:10.400 --> 00:28:14.630 And so here, there's really no limit to the number of fields we could define. 00:28:14.630 --> 00:28:18.680 But often want to keep things reasonable and compact for ourselves design-wise. 00:28:18.680 --> 00:28:21.797 It's a good question of design to figure out how many elements do we need 00:28:21.797 --> 00:28:23.630 or how many fields do we need in our struct. 00:28:23.630 --> 00:28:26.280 And so in this case, we might have 2, 3. 00:28:26.280 --> 00:28:30.530 And you can get up to maybe, I don't know, maybe tens of fields or so. 00:28:30.530 --> 00:28:35.363 But often, if you're doing that, your struct might be a little too complex. 00:28:35.363 --> 00:28:36.905 I'm seeing some other questions here. 00:28:39.958 --> 00:28:44.350 Is the C code we need to use in our code just key value pairs, 00:28:44.350 --> 00:28:46.420 like a dict in Python? 00:28:46.420 --> 00:28:49.270 This is maybe similar to a dictionary, if you're 00:28:49.270 --> 00:28:51.940 familiar with that, in Python in the sense 00:28:51.940 --> 00:28:55.720 that, when we say the president's name is Alyssa 00:28:55.720 --> 00:28:58.690 and the president's votes is 10, we can later on just 00:28:58.690 --> 00:29:03.400 get that same value by referencing president.name and president.vote, so 00:29:03.400 --> 00:29:07.210 similar in spirit to a dictionary where we're trying to have a key, like name, 00:29:07.210 --> 00:29:09.690 correspond to a value, like Alyssa. 00:29:12.160 --> 00:29:13.160 Question about the dots. 00:29:13.160 --> 00:29:17.332 Why do we have these dots, president dot name, president dot votes? 00:29:17.332 --> 00:29:19.040 Simply speaking, long ago, it was decided 00:29:19.040 --> 00:29:21.410 that we would have this dot syntax to reference 00:29:21.410 --> 00:29:25.190 the fields or the attributes of a struct, so president dot name, 00:29:25.190 --> 00:29:26.590 president dot votes. 00:29:26.590 --> 00:29:28.340 And as you get used to it, you'll probably 00:29:28.340 --> 00:29:30.257 see it's pretty handy just to type that little 00:29:30.257 --> 00:29:34.580 dot there to get access to that individual attribute of that struct 00:29:34.580 --> 00:29:37.033 there. 00:29:37.033 --> 00:29:38.950 A question, can we use struct without typedef? 00:29:38.950 --> 00:29:39.700 Indeed, you could. 00:29:39.700 --> 00:29:42.820 So if you go back to this syntax here, we 00:29:42.820 --> 00:29:47.620 saw that typedef was the very first syntax piece we typed here. 00:29:47.620 --> 00:29:51.310 But if you didn't want to maybe reuse this struct, 00:29:51.310 --> 00:29:55.000 you want to just use a struct once, no need to use typedef. 00:29:55.000 --> 00:29:59.410 Typedef lets you specify a candidate, in this case, 00:29:59.410 --> 00:30:02.530 define a name for this new structure that you're building, 00:30:02.530 --> 00:30:04.130 and then reuse that name. 00:30:04.130 --> 00:30:06.920 So let's say I wanted to do this at the top of my program. 00:30:06.920 --> 00:30:07.810 I could do that. 00:30:07.810 --> 00:30:10.150 Later on, I would then be able to reuse the name 00:30:10.150 --> 00:30:13.012 candidate to refer to this structure. 00:30:13.012 --> 00:30:14.470 But maybe I don't want to reuse it. 00:30:14.470 --> 00:30:16.000 Maybe I only want to use it once. 00:30:16.000 --> 00:30:19.900 In that case, you could just have the struct there and not the typedef 00:30:19.900 --> 00:30:24.760 and you could use it just once in your program there. 00:30:24.760 --> 00:30:30.830 All right, I'm seeing a question, are structs similar to objects? 00:30:30.830 --> 00:30:33.830 There are some distinctions between structs and objects. 00:30:33.830 --> 00:30:35.690 You're familiar with this idea of an object 00:30:35.690 --> 00:30:38.900 and maybe you've done Python programming or Java programming 00:30:38.900 --> 00:30:41.360 and you've seen this idea of an object. 00:30:41.360 --> 00:30:46.280 Structs are a bit like objects, but you cannot tie a function to a struct. 00:30:46.280 --> 00:30:51.830 So objects in Python and Java might have methods or functions tied to them. 00:30:51.830 --> 00:30:54.260 Structs, though, do not have that distinction. 00:30:54.260 --> 00:30:58.290 They don't have functions tied to them. 00:30:58.290 --> 00:31:02.740 All right, so let's keep going on with these structs here 00:31:02.740 --> 00:31:05.830 and figure out what else we can do with them. 00:31:05.830 --> 00:31:08.890 Let's actually do a little exercise here, work on this 00:31:08.890 --> 00:31:13.057 together, where we'll create our own get candidate function. 00:31:13.057 --> 00:31:14.890 So you maybe are familiar with this function 00:31:14.890 --> 00:31:17.950 get string or get float in the CSFD library 00:31:17.950 --> 00:31:21.808 where you can use those functions to get a string, get a float, 00:31:21.808 --> 00:31:24.100 get an integer, whatever you want to get from the user. 00:31:24.100 --> 00:31:26.860 And similarly, we'll actually write our own function 00:31:26.860 --> 00:31:31.870 called get candidate that will return to us a new candidate that the user has 00:31:31.870 --> 00:31:36.290 created for us by being prompted for some information about that candidate. 00:31:36.290 --> 00:31:38.507 So let's go on over to our code spaces. 00:31:38.507 --> 00:31:41.590 And if you're like me, you'll need to wait a little bit for yours to load. 00:31:41.590 --> 00:31:44.140 And once you get there, let's go ahead and open up 00:31:44.140 --> 00:31:47.650 this file called candidate.c. 00:31:47.650 --> 00:31:51.730 So once you get there, feel free to type maybe code candidate.c, 00:31:51.730 --> 00:31:56.870 or make a new file and title that one candidate.c. 00:31:56.870 --> 00:32:00.820 And once you do that, what are you going to include 00:32:00.820 --> 00:32:03.735 at the very top of your file? 00:32:03.735 --> 00:32:05.610 Can anyone tell me in the chat what you often 00:32:05.610 --> 00:32:12.660 want to include at the very top of your program 00:32:12.660 --> 00:32:13.970 So I'm seeing some-- 00:32:13.970 --> 00:32:18.530 yeah, some libraries, right, like standard io, cs50.h. 00:32:18.530 --> 00:32:22.810 Certainly, you want to use these libraries inside of our own program 00:32:22.810 --> 00:32:23.310 here. 00:32:23.310 --> 00:32:27.542 So all right, now I have my terminal up and running. 00:32:27.542 --> 00:32:29.750 So if you're following along with me, what you can do 00:32:29.750 --> 00:32:31.730 is simply type maybe code-- 00:32:31.730 --> 00:32:35.880 oops, let me go clear that. 00:32:35.880 --> 00:32:38.700 you do get rid of the activity bar there. 00:32:38.700 --> 00:32:43.920 What we'll do is do code candidate.c, and now we'll get to make a new file, 00:32:43.920 --> 00:32:45.810 again, called candidate.c up here. 00:32:45.810 --> 00:32:47.110 And that dot c is important. 00:32:47.110 --> 00:32:50.268 That means there's a c file here. 00:32:50.268 --> 00:32:52.060 So what we'll do, as people have suggested, 00:32:52.060 --> 00:32:54.530 we'll include some libraries up here. 00:32:54.530 --> 00:32:59.110 We'll say, include maybe the cs50 library to get access to functions, 00:32:59.110 --> 00:33:02.080 like get int and get string, and so on. 00:33:02.080 --> 00:33:05.530 Maybe we'll also include standard io.h to be able to print things 00:33:05.530 --> 00:33:07.700 to the screen, use printdef. 00:33:07.700 --> 00:33:11.570 All right, now often what we'll do is we'll 00:33:11.570 --> 00:33:15.350 declare our struct at the very top of our file 00:33:15.350 --> 00:33:20.310 below our includes or our libraries here. 00:33:20.310 --> 00:33:22.570 So what syntax would we need here? 00:33:22.570 --> 00:33:24.320 We might want to create a new type, right? 00:33:24.320 --> 00:33:27.860 So we'll type typedef, and we want to make a struct. 00:33:27.860 --> 00:33:30.080 So we'll say this is a new struct. 00:33:30.080 --> 00:33:33.662 And what are we going to put inside of this struct? 00:33:33.662 --> 00:33:35.120 What attribute did we have earlier? 00:33:35.120 --> 00:33:37.602 If you want to type in the chat. 00:33:37.602 --> 00:33:39.185 We're trying to make a candidate here. 00:33:42.362 --> 00:33:43.570 All right, so name and votes. 00:33:43.570 --> 00:33:46.480 So maybe name is a string. 00:33:46.480 --> 00:33:49.980 So let's say this attribute is called name. 00:33:49.980 --> 00:33:51.660 It's of type string. 00:33:51.660 --> 00:33:55.290 And then we'll also say, let's give a new attribute called votes, 00:33:55.290 --> 00:33:57.640 and that will be of type int. 00:33:57.640 --> 00:34:01.530 And now finally, we'll need to close this out with a name for our struct. 00:34:01.530 --> 00:34:06.050 So we'll call it candidate down here. 00:34:06.050 --> 00:34:10.116 All right, so now we can re-use this idea of a candidate 00:34:10.116 --> 00:34:12.199 throughout our program because we've used typedef. 00:34:12.199 --> 00:34:15.590 We can say, I want to create a new candidate using 00:34:15.590 --> 00:34:19.940 this new amalgamation of types that we're going to call candidate 00:34:19.940 --> 00:34:22.040 throughout our program here. 00:34:22.040 --> 00:34:26.780 All right, and now what is the main part of our program now? 00:34:26.780 --> 00:34:28.880 We have our libraries. 00:34:28.880 --> 00:34:30.770 We have our struct. 00:34:30.770 --> 00:34:33.929 What kind of function do we need now? 00:34:33.929 --> 00:34:36.690 Maybe in the chat, feel free to type. 00:34:36.690 --> 00:34:38.369 Yeah, we need our int main void. 00:34:38.369 --> 00:34:42.250 So we need the main function for our program. 00:34:42.250 --> 00:34:46.050 So we'll do int main void and have some space there for us 00:34:46.050 --> 00:34:49.760 to write our program. 00:34:49.760 --> 00:34:52.340 But here, if we go back to our slides, our goal 00:34:52.340 --> 00:34:55.610 is to make our own function called get candidate. 00:34:55.610 --> 00:35:00.170 So what we want to do is probably define that down below. 00:35:00.170 --> 00:35:03.020 And what you'll notice about defining new functions 00:35:03.020 --> 00:35:07.160 or declaring new functions is that their signature here, 00:35:07.160 --> 00:35:11.160 or we call this line here, has a few key elements to it. 00:35:11.160 --> 00:35:14.270 So it has the type that this function gives back 00:35:14.270 --> 00:35:16.070 to us, that it returns to us. 00:35:16.070 --> 00:35:20.700 It has the function's name, and it has the function's inputs. 00:35:20.700 --> 00:35:24.500 So if we're trying to write a function called get candidate, 00:35:24.500 --> 00:35:26.570 what name would we type in? 00:35:26.570 --> 00:35:30.560 Maybe an obvious answer here, if we type in the chat. 00:35:30.560 --> 00:35:33.755 What name would we type in for get candidate? 00:35:33.755 --> 00:35:35.630 We probably should type get candidate, right? 00:35:35.630 --> 00:35:38.570 Get candidate is the name of our function. 00:35:38.570 --> 00:35:40.445 And now, what type does it return to us? 00:35:43.570 --> 00:35:44.650 I'm seeing a few-- 00:35:44.650 --> 00:35:47.350 I'm seeing string, and I'm seeing candidate. 00:35:47.350 --> 00:35:50.590 So notice now, we're not going to return a string. 00:35:50.590 --> 00:35:54.700 We're actually going to return an entire candidate because we've 00:35:54.700 --> 00:35:58.810 defined a candidate as this combination of a string that is called name 00:35:58.810 --> 00:36:00.310 and an integer that is called votes. 00:36:00.310 --> 00:36:05.170 So here, we're going to give back to our program a whole candidate, 00:36:05.170 --> 00:36:08.500 not just a string, not just an int, but a whole candidate, those two types 00:36:08.500 --> 00:36:09.490 put together. 00:36:09.490 --> 00:36:12.020 And because we use typedef, we can say this down below. 00:36:12.020 --> 00:36:16.090 We can say get candidate. 00:36:16.090 --> 00:36:22.060 And now, we can go ahead and define this function called get candidate, 00:36:22.060 --> 00:36:23.590 but we need one more step now. 00:36:23.590 --> 00:36:28.100 We need to give some inputs or some arguments here. 00:36:28.100 --> 00:36:31.568 And if we're using our modeling off of get string, for example, 00:36:31.568 --> 00:36:32.860 we might want to take a prompt. 00:36:32.860 --> 00:36:37.480 We could say, maybe it takes a prompt that is a string here. 00:36:40.015 --> 00:36:42.265 All right, so what questions are there on this so far? 00:36:46.340 --> 00:36:49.520 All right, seeing none so far. 00:36:49.520 --> 00:36:53.160 Now, let's go ahead and try to fill in the rest of our get candidate function. 00:36:53.160 --> 00:36:55.670 So ideally, we want to be able to use it like this. 00:36:55.670 --> 00:37:00.350 We could say, within my main function, I want to create a new candidate. 00:37:00.350 --> 00:37:03.470 Maybe I'll call this one president. 00:37:03.470 --> 00:37:07.340 But to actually fill in that variable, to give it a value, 00:37:07.340 --> 00:37:13.700 I'll call get candidate, similar to what I did for get string, for example. 00:37:13.700 --> 00:37:17.645 Here, I could say maybe Enter a candidate is the prompt. 00:37:22.830 --> 00:37:24.140 And now I'm seeing a question. 00:37:24.140 --> 00:37:27.810 Is candidate a type because we've declared it above the main function? 00:37:27.810 --> 00:37:28.310 Indeed. 00:37:28.310 --> 00:37:32.810 So we've used typedef here, which is that key word that says, all of what 00:37:32.810 --> 00:37:36.540 follows should be considered reusable in our program. 00:37:36.540 --> 00:37:39.680 So here we're saying that this struct that we're going to call candidate 00:37:39.680 --> 00:37:44.000 is a bit similar to a type that we can use throughout our program. 00:37:44.000 --> 00:37:46.550 We can say that a function does indeed return 00:37:46.550 --> 00:37:49.580 an entire candidate and not just those basic data 00:37:49.580 --> 00:37:53.540 types, like a string or an int. 00:37:53.540 --> 00:37:57.170 All right, and so we're going to be able to use get candidate like this. 00:37:57.170 --> 00:38:00.110 We'll create a variable called president that is a candidate 00:38:00.110 --> 00:38:02.450 and then have get candidate returned to us 00:38:02.450 --> 00:38:07.620 that new candidate that we've created with get candidate down below. 00:38:07.620 --> 00:38:11.920 OK, so we now have this function get candidate, 00:38:11.920 --> 00:38:16.060 but we need first to be able to print out the prompt to the user 00:38:16.060 --> 00:38:17.570 so they know what to type in. 00:38:17.570 --> 00:38:23.960 So here I might say, OK, let me print out the prompt with a new line here. 00:38:23.960 --> 00:38:27.410 So I'll say, whatever the user gives to me as the prompt, 00:38:27.410 --> 00:38:31.210 let's say this string here, I'll then print it back 00:38:31.210 --> 00:38:36.200 out to the user when I run Get candidate, and I'll make a new line. 00:38:36.200 --> 00:38:39.340 Now though, I need to do the work of creating this new candidate 00:38:39.340 --> 00:38:41.890 and filling in its attributes and ultimately returning 00:38:41.890 --> 00:38:44.690 that candidate to my main function. 00:38:44.690 --> 00:38:49.720 So what we could do is we could say, I want to create a new candidate. 00:38:49.720 --> 00:38:51.400 And it's like a throwaway candidate. 00:38:51.400 --> 00:38:54.160 I'm just going to create it here, add some attributes 00:38:54.160 --> 00:38:56.300 and return it back to our main function. 00:38:56.300 --> 00:38:57.988 So I'll just call it candidate c. 00:38:57.988 --> 00:39:00.280 Maybe we can come up with a better name, but we'll just 00:39:00.280 --> 00:39:02.820 call it candidate c for now. 00:39:02.820 --> 00:39:06.870 This is a new candidate variable I've created in my get candidate function. 00:39:06.870 --> 00:39:08.715 And now what I could do is this. 00:39:08.715 --> 00:39:12.850 I could say c.name should be what? 00:39:12.850 --> 00:39:17.620 What kind of function could I use to fill in the value for name? 00:39:17.620 --> 00:39:19.700 Remember, it's a string. 00:39:19.700 --> 00:39:21.310 Ah, I could use get string, right? 00:39:21.310 --> 00:39:27.640 I could say get string and, let's say, Enter a name, right? 00:39:27.640 --> 00:39:30.100 So now the candidate's name will be filled 00:39:30.100 --> 00:39:34.690 in by the user when they enter in some text after get string. 00:39:34.690 --> 00:39:36.610 And now here we'll see c.votes. 00:39:36.610 --> 00:39:40.140 And how could I fill in the votes? 00:39:40.140 --> 00:39:43.960 What kind of function would I use here, maybe in the chat? 00:39:43.960 --> 00:39:44.740 Get int, right? 00:39:44.740 --> 00:39:49.680 So I could do get int and then enter a number of votes. 00:39:49.680 --> 00:39:50.970 Awesome. 00:39:50.970 --> 00:39:54.417 And now finally, I've created this new candidate called c. 00:39:54.417 --> 00:39:56.250 I've added in the name, the number of votes. 00:39:56.250 --> 00:39:59.720 What's left to do? 00:39:59.720 --> 00:40:01.710 I need to give it back to my main function. 00:40:01.710 --> 00:40:03.020 So what would let me do that? 00:40:03.020 --> 00:40:05.710 Return, so I'll return c. 00:40:05.710 --> 00:40:09.130 And now what will happen here, if we go back up to the very top, line 13, 00:40:09.130 --> 00:40:12.070 this new variable called president that is a candidate 00:40:12.070 --> 00:40:14.590 will first call get candidate. 00:40:14.590 --> 00:40:16.467 We'll go ahead and prompt the user. 00:40:16.467 --> 00:40:19.300 Then we'll create this new candidate, fill in the name of the votes, 00:40:19.300 --> 00:40:21.910 return that candidate, and ultimately, store it 00:40:21.910 --> 00:40:23.950 in this variable called President. 00:40:23.950 --> 00:40:27.070 So what I should be able to do is maybe type in, for example, 00:40:27.070 --> 00:40:29.900 print maybe the name. 00:40:29.900 --> 00:40:32.480 So I'll say president.name. 00:40:32.480 --> 00:40:36.800 And then what I'll do is I'll print, let's say, the votes. 00:40:36.800 --> 00:40:39.470 I'll say president.votes. 00:40:39.470 --> 00:40:42.630 And when I run this, I should be able to see that result there. 00:40:42.630 --> 00:40:45.410 So let's go ahead and go down to our terminal. 00:40:45.410 --> 00:40:48.780 I'll type make candidate. 00:40:48.780 --> 00:40:50.870 Oh, and I got an error. 00:40:50.870 --> 00:40:54.492 What did we forget to do? 00:40:54.492 --> 00:40:56.075 If you take a look at this error here. 00:40:59.460 --> 00:41:00.840 Seeing a few answers. 00:41:00.840 --> 00:41:03.390 What did we forget to do here? 00:41:03.390 --> 00:41:07.530 Implicit declaration of function get candidate is invalid in C99. 00:41:10.900 --> 00:41:13.880 Yeah, so I'm seeing I'm missing the prototype for this function. 00:41:13.880 --> 00:41:16.120 So notice how we got ahead of ourselves here. 00:41:16.120 --> 00:41:18.910 We went and defined our function down below, 00:41:18.910 --> 00:41:21.950 but we actually use it before it is defined. 00:41:21.950 --> 00:41:25.030 So what we should do is really go to line 10, 00:41:25.030 --> 00:41:28.107 after our definition of this candidate here. 00:41:28.107 --> 00:41:29.690 And we should say something like this. 00:41:29.690 --> 00:41:33.640 We should say, let's copy and paste the prototype for this function, 00:41:33.640 --> 00:41:38.260 the prototype being what it returns, its name, and any arguments it has, 00:41:38.260 --> 00:41:41.780 and put a semicolon to say that, look, this function will come up. 00:41:41.780 --> 00:41:44.830 I promise to you, I will define it later as this 00:41:44.830 --> 00:41:48.908 a compiler reads our code from top to bottom in this case. 00:41:48.908 --> 00:41:50.200 All right, so let's go back in. 00:41:50.200 --> 00:41:53.440 Let's go ahead and clear our terminal window. 00:41:53.440 --> 00:41:55.570 Type make candidate. 00:41:55.570 --> 00:41:57.110 Oop, and we still have an error. 00:41:57.110 --> 00:41:59.644 Let's see this one. 00:41:59.644 --> 00:42:00.850 Hmm. 00:42:00.850 --> 00:42:04.150 President.votes, this error is a little cryptic. 00:42:04.150 --> 00:42:08.233 But if the format code for a string, you'll 00:42:08.233 --> 00:42:10.150 know that this is maybe the wrong format code. 00:42:10.150 --> 00:42:12.400 I'm seeing we need %i right there. 00:42:12.400 --> 00:42:14.350 Good, so I'll click my terminal again. 00:42:14.350 --> 00:42:15.940 I'll type make candidate. 00:42:15.940 --> 00:42:17.630 And now, it seems to work. 00:42:17.630 --> 00:42:21.160 So what I can do is I can do dot/candidate. 00:42:21.160 --> 00:42:24.850 I now see the prompt Enter a candidate that I typed up above here. 00:42:24.850 --> 00:42:29.440 I can say maybe the candidate's name is Carter, and maybe the number of votes 00:42:29.440 --> 00:42:30.400 is 10. 00:42:30.400 --> 00:42:33.370 And I'll hit Enter, and now I see those same elements 00:42:33.370 --> 00:42:38.400 here in my program or my terminal. 00:42:38.400 --> 00:42:42.300 OK, so what questions are there on this program so far? 00:42:49.990 --> 00:42:54.750 All right, so seeing none right now. 00:42:54.750 --> 00:42:57.410 But what we might want to do at the very end 00:42:57.410 --> 00:43:00.580 is, maybe we don't just want one candidate. 00:43:00.580 --> 00:43:03.470 We want, actually, an array of candidates or a list of candidates. 00:43:03.470 --> 00:43:07.040 And you'll see this in the problem set for this week of CS50. 00:43:07.040 --> 00:43:12.230 What we can do is we can actually use this same type we've defined 00:43:12.230 --> 00:43:14.760 to create an array of that type. 00:43:14.760 --> 00:43:19.310 So we could say, I want an array of candidates 00:43:19.310 --> 00:43:21.380 that I'll call the candidates array. 00:43:21.380 --> 00:43:23.340 And I want to have three of them in there. 00:43:23.340 --> 00:43:25.490 So notice how, if I zoom in again, you'll 00:43:25.490 --> 00:43:28.910 see we're going to define an array called candidates array 00:43:28.910 --> 00:43:32.210 that is full of these candidate types that we've declared up above. 00:43:32.210 --> 00:43:35.567 And it has space for three of them, right? 00:43:35.567 --> 00:43:37.400 So what we could do in this case is actually 00:43:37.400 --> 00:43:39.530 go ahead and fill in the array. 00:43:39.530 --> 00:43:43.200 We could say, let's start at index 0. 00:43:43.200 --> 00:43:46.660 Let's go on up to but not including that third index. 00:43:46.660 --> 00:43:51.750 So we'll go 0, 1, and 2, and increase i by 1 as we go. 00:43:51.750 --> 00:43:56.210 And as we do that, we'll say, OK, maybe the candidates array at location i, 00:43:56.210 --> 00:44:02.130 first 0, then 1, then 2 is going to use Get candidate. 00:44:02.130 --> 00:44:07.420 So I'll say get candidate, and let's say, Enter a candidate. 00:44:07.420 --> 00:44:10.123 And now what I can do is, if I were to run this program, 00:44:10.123 --> 00:44:12.040 I would get prompted again and again and again 00:44:12.040 --> 00:44:17.520 to enter a candidate until my array is full. 00:44:17.520 --> 00:44:20.510 Now, if we were to do that and also to access 00:44:20.510 --> 00:44:22.730 some of these candidates inside that array, 00:44:22.730 --> 00:44:26.340 we need some combination of the syntax we've seen before. 00:44:26.340 --> 00:44:29.570 So what we might do is, in the problems that you'll 00:44:29.570 --> 00:44:34.340 see maybe an array of candidates like this, like name and number of vote. 00:44:34.340 --> 00:44:39.470 And to access the candidate as a whole, like Alice as well as Alice's votes, 00:44:39.470 --> 00:44:43.310 you would just type candidates bracket 0 to get that very first element 00:44:43.310 --> 00:44:45.380 in this array here. 00:44:45.380 --> 00:44:48.520 But if I wanted to get maybe just the candidate's name, 00:44:48.520 --> 00:44:49.730 I could do as follows. 00:44:49.730 --> 00:44:52.690 I could say candidates brackets 0 dot name, 00:44:52.690 --> 00:44:55.840 or, similarly, candidates brackets 0 dot votes. 00:44:55.840 --> 00:44:58.420 And that would allow me to get, not just the whole candidate 00:44:58.420 --> 00:45:04.210 at that array location, but the actual attribute I'm interested in here 00:45:04.210 --> 00:45:06.660 as well. 00:45:06.660 --> 00:45:08.985 All right, other questions on this. 00:45:19.260 --> 00:45:24.170 All right, so seeing none so far, that will 00:45:24.170 --> 00:45:27.950 conclude our little brief foray into structs her. 00:45:27.950 --> 00:45:30.650 And certainly, we can take a minute to go back 00:45:30.650 --> 00:45:32.760 if there are questions towards the end. 00:45:32.760 --> 00:45:36.800 But for now, with our last bit of time, what we want to do 00:45:36.800 --> 00:45:39.660 is figure out how we can use recursion. 00:45:39.660 --> 00:45:44.030 So recursion is not necessarily an algorithm. 00:45:44.030 --> 00:45:48.560 It's more so an approach to problem solving in computer science. 00:45:48.560 --> 00:45:51.350 There is no single recursive algorithm, but there 00:45:51.350 --> 00:45:53.250 are algorithms that use recursion. 00:45:53.250 --> 00:45:55.730 So recursion is simply a way of solving problems. 00:45:55.730 --> 00:46:01.430 And recursion, more specifically, is about taking a large problem, one 00:46:01.430 --> 00:46:04.910 that seems a little daunting, and breaking it up into smaller pieces 00:46:04.910 --> 00:46:07.230 that we know we can solve. 00:46:07.230 --> 00:46:11.150 And so one example of this is often used when teaching recursion 00:46:11.150 --> 00:46:12.690 is this idea of a factorial. 00:46:12.690 --> 00:46:17.390 So if we look at a factorial, if you're not familiar, we can say 1 factorial 00:46:17.390 --> 00:46:19.460 is 1, right? 00:46:19.460 --> 00:46:23.600 We can say 2 factorial is 2 times 1. 00:46:23.600 --> 00:46:27.650 And we can say 3 factorial is, well, 3 times 2 times 1. 00:46:27.650 --> 00:46:31.430 And if you're not getting the pattern, 4 factorial might be? 00:46:31.430 --> 00:46:34.070 Well, just 4 times 3 times 2 times 1. 00:46:34.070 --> 00:46:39.380 So a factorial is multiplying a number by 1 less than that number 00:46:39.380 --> 00:46:43.385 and moving down until we get to 1, right, so 4 times 3 times 2 times 00:46:43.385 --> 00:46:47.910 1 for 4 factorial, 3 factorial, 3 times 2 times 1, and so on. 00:46:47.910 --> 00:46:54.200 Now, what do you notice about this problem, particularly in 4 factorial? 00:46:54.200 --> 00:46:57.590 What do you notice, or what do you see if we're 00:46:57.590 --> 00:47:00.890 trying to use recursion on this problem, trying to find a smaller 00:47:00.890 --> 00:47:05.520 problem within 4 factorial? 00:47:05.520 --> 00:47:08.350 Maybe type in the chat if you'd like. 00:47:08.350 --> 00:47:15.962 What kind of pattern do you see when you look at 2 factorial, 3 factorial? 00:47:15.962 --> 00:47:17.170 So seeing a few ideas, right? 00:47:17.170 --> 00:47:20.170 I'm seeing it's repeating the same steps. 00:47:20.170 --> 00:47:22.330 It's a little repetitive. 00:47:22.330 --> 00:47:25.900 And I'm seeing, more particularly, if we look at 4 factorial, 00:47:25.900 --> 00:47:30.490 we actually see that 3 factorial is included in 4 factorial, right? 00:47:30.490 --> 00:47:32.680 3 factorial is 3 times 2 times 1. 00:47:32.680 --> 00:47:36.010 Well, that's actually right there in 4 factorial, 3 times 2 times 1. 00:47:36.010 --> 00:47:39.400 So if we were to look at the problem this way, 00:47:39.400 --> 00:47:41.320 we might make it a little more obvious, right? 00:47:41.320 --> 00:47:45.890 4 factorial really has the solution 3 factorial inside of it. 00:47:45.890 --> 00:47:49.127 And similarly, 3 factorial has 2 factorial inside of it. 00:47:49.127 --> 00:47:51.710 And then finally, 1 factorial, that's just kind of on its own. 00:47:51.710 --> 00:47:52.570 It's just 1, right? 00:47:52.570 --> 00:47:54.910 We know that for a fact. 00:47:54.910 --> 00:47:57.690 This is really a good place for recursion 00:47:57.690 --> 00:48:01.110 to come in because recursion is all about taking this larger problem, 00:48:01.110 --> 00:48:05.470 like 4 factorial, and breaking it down into smaller pieces. 00:48:05.470 --> 00:48:08.340 So let's look at it from a recursive standpoint. 00:48:08.340 --> 00:48:11.950 Let's go ahead and say we want to find 4 factorial. 00:48:11.950 --> 00:48:14.650 Well, what is 4 factorial? 00:48:14.650 --> 00:48:17.160 Well, it's 4 times what? 00:48:17.160 --> 00:48:19.920 What's the smaller problem within 4 factorial? 00:48:19.920 --> 00:48:22.020 4 times 3 factorial, I'm seeing in the chat. 00:48:22.020 --> 00:48:25.740 So 4 factorial is just 4 times 3 factorial. 00:48:25.740 --> 00:48:28.510 But what then is 3 factorial? 00:48:28.510 --> 00:48:32.010 So this is where what comes in as we call it a recursive call. 00:48:32.010 --> 00:48:36.120 This is saying we are going to solve this smaller problem before we 00:48:36.120 --> 00:48:38.490 can solve this larger problem, right? 00:48:38.490 --> 00:48:43.420 We can't solve 4 factorial until we know what 3 factorial is. 00:48:43.420 --> 00:48:45.610 So let's go ahead and solve 3 factorial. 00:48:45.610 --> 00:48:46.950 Well, what is 3 factorial? 00:48:46.950 --> 00:48:52.120 That is just 3 times what? 00:48:52.120 --> 00:48:54.550 3 times 2 factorial, right? 00:48:54.550 --> 00:48:58.190 So that's fine, but what is 2 factorial? 00:48:58.190 --> 00:49:00.520 Well, 2 factorial is? 00:49:00.520 --> 00:49:02.750 2 times 1 factorial. 00:49:02.750 --> 00:49:04.270 And what is 1 factorial? 00:49:04.270 --> 00:49:06.110 At some point, we do have to stop here. 00:49:06.110 --> 00:49:09.250 Otherwise, we'll keep finding smaller and smaller problems and never end. 00:49:09.250 --> 00:49:12.100 Well, 1 factorial, in this case, is just 1. 00:49:12.100 --> 00:49:14.350 We know that for a fact. 00:49:14.350 --> 00:49:18.550 And so this down at the bottom is what's called our base case. 00:49:18.550 --> 00:49:23.360 This is the problem that we know how to solve just for a fact. 00:49:23.360 --> 00:49:26.560 1 factorial is 1, no computation necessary, 00:49:26.560 --> 00:49:29.850 no need to break it down into a smaller problem. 00:49:29.850 --> 00:49:33.210 And now, once we've gone down to that base case, 00:49:33.210 --> 00:49:35.040 well, the rest follows, right? 00:49:35.040 --> 00:49:36.960 We know that 1 factorial is 1. 00:49:36.960 --> 00:49:40.390 So let's go ahead and make sure that we can solve 2 factorial. 00:49:40.390 --> 00:49:42.880 And we're going, what we call, back up the call stack, 00:49:42.880 --> 00:49:46.020 where we made a recursive call earlier to go ahead and solve a smaller 00:49:46.020 --> 00:49:46.980 problem. 00:49:46.980 --> 00:49:49.920 Now we've found our base case, so we'll go back up 00:49:49.920 --> 00:49:53.970 this stack of calls we made to find the answer here. 00:49:53.970 --> 00:49:57.150 What we'll do is say, OK, 2 factorial, that's actually just 2 times 1. 00:49:57.150 --> 00:49:59.370 We know that now because 1 factorial is 1. 00:49:59.370 --> 00:50:02.550 Well, 3 factorial, that's actually just 3 times 2 times 00:50:02.550 --> 00:50:05.430 1 because we know now that 2 factorial is 2 times 1. 00:50:05.430 --> 00:50:08.730 And similarly, for 4 factorial, we know that, in this case, 00:50:08.730 --> 00:50:11.400 3 factorial is just 3 times 2 times 1. 00:50:11.400 --> 00:50:15.720 So now we can say 4 factorial is just this expression, 4 times 3 times 00:50:15.720 --> 00:50:16.290 2 times 1. 00:50:16.290 --> 00:50:20.070 And that, as a whole, is 24. 00:50:20.070 --> 00:50:22.930 All right, and so I'm seeing in the chat, it's like backwards logic. 00:50:22.930 --> 00:50:24.222 It is a little backwards logic. 00:50:24.222 --> 00:50:28.082 We have to go down to the bottom first and then work our way back up. 00:50:28.082 --> 00:50:29.540 So let's work on this one together. 00:50:29.540 --> 00:50:32.490 Let's actually see what might be able to work on with here. 00:50:32.490 --> 00:50:35.840 And what we'll do is write our own function called factorial, 00:50:35.840 --> 00:50:40.400 where factorial should take an integer and return the factorial of whatever 00:50:40.400 --> 00:50:42.570 number we pass in as a parameter. 00:50:42.570 --> 00:50:45.410 So if we pass in 4, we should find 4 factorial, or 5, 00:50:45.410 --> 00:50:47.720 we should find 5 factorial here. 00:50:47.720 --> 00:50:52.098 All right, so let's go ahead and actually open up our own program. 00:50:52.098 --> 00:50:53.890 We'll go ahead and go back to our terminal. 00:50:53.890 --> 00:50:59.240 We'll type code factorial.c to open up this new file called factorial. 00:50:59.240 --> 00:51:01.810 And let's get the same template code in there. 00:51:01.810 --> 00:51:04.810 We need to make sure we have cs50 library. 00:51:04.810 --> 00:51:07.570 We need to have standard io.h. 00:51:07.570 --> 00:51:12.760 And we also need to have, of course, our int main void function, 00:51:12.760 --> 00:51:15.620 that main function in our program. 00:51:15.620 --> 00:51:19.320 And now we can also make sure we have our factorial function. 00:51:19.320 --> 00:51:21.830 So I'll zoom in just a little bit more. 00:51:21.830 --> 00:51:23.600 We might want to have a factorial. 00:51:23.600 --> 00:51:28.740 What type is factorial returning to us, do we know in this case? 00:51:28.740 --> 00:51:30.440 If you want to type a chime in the chat. 00:51:30.440 --> 00:51:31.190 An integer, right? 00:51:31.190 --> 00:51:35.420 So we'll say int, and then the name of this function, factorial. 00:51:35.420 --> 00:51:37.550 And then does it take any inputs? 00:51:37.550 --> 00:51:39.110 What kind of input does it take? 00:51:41.840 --> 00:51:44.130 Yeah, it takes a number that is also an integer. 00:51:44.130 --> 00:51:48.060 So I could say int, maybe, number in this case. 00:51:48.060 --> 00:51:50.210 So here we have this function, again, called 00:51:50.210 --> 00:51:56.000 factorial that takes a argument called number that is an integer. 00:51:56.000 --> 00:52:01.480 And it returns to us an integer, that number factorialized, right? 00:52:01.480 --> 00:52:04.450 And now we know from our past mistake we need to actually go ahead 00:52:04.450 --> 00:52:08.590 and include this prototype up at the very top of our file 00:52:08.590 --> 00:52:11.790 in order to use this function in our code. 00:52:11.790 --> 00:52:15.810 OK, and let's just go ahead and fill our main function here. 00:52:15.810 --> 00:52:19.750 Let's make sure we maybe prompt the user for a number. 00:52:19.750 --> 00:52:24.660 So we could say, let's give ourselves maybe int n is get int, 00:52:24.660 --> 00:52:29.760 and we'll say type a number to our user. 00:52:29.760 --> 00:52:33.690 And then what we'll do is maybe print the resulting 00:52:33.690 --> 00:52:36.990 integer that comes from running factorial 00:52:36.990 --> 00:52:40.600 in this case, so factorial of n. 00:52:40.600 --> 00:52:43.760 Now, it's up to us to actually implement factorial down here. 00:52:43.760 --> 00:52:47.050 And when we think about implementing recursive functions, 00:52:47.050 --> 00:52:50.380 we often want to start first with our base case. 00:52:50.380 --> 00:52:52.910 What is the thing we know to be a fact? 00:52:52.910 --> 00:52:58.990 And if we look at our factorial call stack here, what was our thing 00:52:58.990 --> 00:53:01.210 we know to be a factor down here? 00:53:01.210 --> 00:53:02.500 Feel free to type in the chat. 00:53:05.500 --> 00:53:06.130 Seeing 1. 00:53:06.130 --> 00:53:07.960 So yeah, 1 factorial is 1. 00:53:07.960 --> 00:53:08.920 We know that. 00:53:08.920 --> 00:53:10.610 That is always true. 00:53:10.610 --> 00:53:13.840 So what we should do is go back to our factorial function 00:53:13.840 --> 00:53:22.510 and then say, OK, well, if number is 1, if it's equal to 1, let's go ahead 00:53:22.510 --> 00:53:23.890 and just say the answer. 00:53:23.890 --> 00:53:26.590 Let's say the answer is 1. 00:53:26.590 --> 00:53:30.752 So now, if I were to type in 1 and pass it to factorial, 00:53:30.752 --> 00:53:31.960 I would get the right answer. 00:53:31.960 --> 00:53:34.720 1 factorial is 1. 00:53:34.720 --> 00:53:37.060 But there's more to do here. 00:53:37.060 --> 00:53:40.420 If I were to type in factorial of 3 or factorial of 4, 00:53:40.420 --> 00:53:43.060 that wouldn't quite work because I haven't figured out 00:53:43.060 --> 00:53:46.380 how to solve that piece yet. 00:53:46.380 --> 00:53:50.280 Now, if we go back to our diagram here, what 00:53:50.280 --> 00:53:55.020 did we notice about how each factorial problem is 00:53:55.020 --> 00:53:58.360 composed of some other problem? 00:53:58.360 --> 00:54:00.940 What should be our recursive step here? 00:54:04.270 --> 00:54:06.760 Yes, I'm seeing something like n minus 1. 00:54:06.760 --> 00:54:09.940 And if you notice, you'll look at maybe 4 factorial, and see, 00:54:09.940 --> 00:54:14.200 well, 4 factorial is really just 4 times 3 factorial. 00:54:14.200 --> 00:54:16.150 And 3 factorial is just 3 times 2 factorial. 00:54:16.150 --> 00:54:19.330 So it's really whatever number we're at times 00:54:19.330 --> 00:54:21.600 the factorial of a number minus 1. 00:54:21.600 --> 00:54:26.130 Now, there is a way to use a loop here, and that 00:54:26.130 --> 00:54:27.880 would be called what an iterative approach 00:54:27.880 --> 00:54:29.338 using a loop to solve this problem. 00:54:29.338 --> 00:54:32.560 But here we'll actually use a recursive solution, 00:54:32.560 --> 00:54:36.440 which is one that calls itself in the definition. 00:54:36.440 --> 00:54:39.940 So factorial will call the factorial function 00:54:39.940 --> 00:54:42.050 to try to solve this problem here. 00:54:42.050 --> 00:54:45.490 So if we know that we don't have the answer already, 00:54:45.490 --> 00:54:49.365 if we know that we aren't at 1 factorial, what we can do instead 00:54:49.365 --> 00:54:52.240 is try to solve this problem by breaking it down into smaller pieces. 00:54:52.240 --> 00:54:55.210 We could say, well, we know that a certain number factorial is really 00:54:55.210 --> 00:55:07.870 just that number times that number minus 1 factorialized like this. 00:55:07.870 --> 00:55:11.170 If I go full screen here, we'll see that really the solution is just 00:55:11.170 --> 00:55:17.680 number times the factorial of that number minus 1. 00:55:17.680 --> 00:55:20.800 And let's go ahead and try to get a visual here, 00:55:20.800 --> 00:55:22.480 but just first confirm it works. 00:55:22.480 --> 00:55:28.290 So I'll say make factorial and run./factorial. 00:55:28.290 --> 00:55:32.230 And maybe I'll type in 4, and I get 24. 00:55:32.230 --> 00:55:38.280 So let's type n factorial of 3, and I get 6 because 3 times 2 times 1 is 6. 00:55:38.280 --> 00:55:42.210 But why is this working? 00:55:42.210 --> 00:55:45.570 It seems a little odd that we can just solve this problem 00:55:45.570 --> 00:55:48.030 with only a single if statement and this expression 00:55:48.030 --> 00:55:51.780 down here that uses itself in the definition, right? 00:55:51.780 --> 00:55:55.282 So to visualize this, we actually want to use something called a debug50, 00:55:55.282 --> 00:55:56.490 if you're familiar with that. 00:55:56.490 --> 00:56:00.090 Debug50 lets you step through your code and go through 00:56:00.090 --> 00:56:01.990 and see how things are working here. 00:56:01.990 --> 00:56:05.910 So while we're at it, let's set a breakpoint right 00:56:05.910 --> 00:56:08.760 at this point in our code, meaning we'll stop at this point, 00:56:08.760 --> 00:56:11.460 and then we'll step through piece by piece 00:56:11.460 --> 00:56:13.990 to see what's happening in the computer's memory. 00:56:13.990 --> 00:56:19.100 So we'll go ahead and run this using debug50. 00:56:19.100 --> 00:56:22.040 And we'll wait for debug50 to pull itself up. 00:56:22.040 --> 00:56:24.680 And we'll step through our code in a minute here. 00:56:28.340 --> 00:56:31.780 All right, let me zoom out just a little bit. 00:56:31.780 --> 00:56:34.130 OK, so I'm seeing type a number in my prompt. 00:56:34.130 --> 00:56:37.580 So I'll go ahead and type in the number for, right? 00:56:37.580 --> 00:56:40.910 All right, so notice debug50 on the side here. 00:56:40.910 --> 00:56:44.570 We now have number 4, and what we've done 00:56:44.570 --> 00:56:46.940 is we've given our program a number. 00:56:46.940 --> 00:56:48.350 Now, we're at this stage. 00:56:48.350 --> 00:56:52.850 We've called factorial with n is 4, which 00:56:52.850 --> 00:56:55.940 means that number here is equal to 4. 00:56:55.940 --> 00:56:58.610 And if we look down at our call stack, that vocabulary 00:56:58.610 --> 00:57:01.850 term we learned earlier, we see that we first called main, 00:57:01.850 --> 00:57:04.490 and then we called factorial, right? 00:57:04.490 --> 00:57:08.030 But we still need to call probably factorial again 00:57:08.030 --> 00:57:11.450 because, if we go in here, we see that number is not 1. 00:57:11.450 --> 00:57:12.830 Number is 4 right now. 00:57:12.830 --> 00:57:15.110 It's not 1, so we can't return 1. 00:57:15.110 --> 00:57:18.060 We will instead need to do this line of code. 00:57:18.060 --> 00:57:22.440 But we can't solve this line of code until we run the factorial function 00:57:22.440 --> 00:57:24.550 again with number 1 less than that. 00:57:24.550 --> 00:57:29.590 So what we'll do is we'll step into this function factorial. 00:57:29.590 --> 00:57:32.310 And now, see in our call stack, factorial shows up again. 00:57:32.310 --> 00:57:34.560 We call factorial once, we're calling it again. 00:57:34.560 --> 00:57:36.970 But now, what's going to happen? 00:57:36.970 --> 00:57:39.310 Number is 3, so we're getting closer. 00:57:39.310 --> 00:57:40.380 We're not quite there. 00:57:40.380 --> 00:57:44.190 3 is not 1, so we're going to continue down again. 00:57:44.190 --> 00:57:47.280 We'll go ahead, and we can't return 1 there, 00:57:47.280 --> 00:57:49.630 but we can figure out what is 3 factorial? 00:57:49.630 --> 00:57:52.560 Well, to find 3 factorial, we've got to find 2 factorial. 00:57:52.560 --> 00:57:53.730 So we'll dive in again. 00:57:53.730 --> 00:57:57.150 We'll say, OK, let's go deeper in our call stack. 00:57:57.150 --> 00:58:00.360 Notice how if we scroll down, factorial is being called yet again. 00:58:00.360 --> 00:58:02.130 we've called it the third time now. 00:58:02.130 --> 00:58:04.380 Now, number is 2. 00:58:04.380 --> 00:58:05.310 OK, let's keep going. 00:58:05.310 --> 00:58:06.960 Number is not 1 yet. 00:58:06.960 --> 00:58:09.720 To find 2 factorial, we got to find 1 factorial. 00:58:09.720 --> 00:58:12.122 Let's go dive in again. 00:58:12.122 --> 00:58:13.080 Look at our call stack. 00:58:13.080 --> 00:58:15.700 We've called factorial four times now. 00:58:15.700 --> 00:58:19.830 But at this point, we know number is 1, and so we 00:58:19.830 --> 00:58:23.040 can simply and safely return 1. 00:58:23.040 --> 00:58:25.440 We know the answer now, right? 00:58:25.440 --> 00:58:28.320 So we'll do that, and then, that's correct, 00:58:28.320 --> 00:58:29.910 we called this number 1 our base case. 00:58:29.910 --> 00:58:31.530 We've hit our base case now. 00:58:31.530 --> 00:58:34.530 We can start going back up our call stack. 00:58:34.530 --> 00:58:39.040 So we can say let's finish that call of factorial. 00:58:39.040 --> 00:58:44.001 Now, we're back at our third factorial call where number is 2. 00:58:44.001 --> 00:58:45.850 Well, we solved that problem. 00:58:45.850 --> 00:58:49.530 We know that 2 factorial is just 2 times 1. 00:58:49.530 --> 00:58:52.650 And now we can return that 2 times 1. 00:58:52.650 --> 00:58:55.260 Now, we're at that later version of factorial, 00:58:55.260 --> 00:58:58.050 that second call where number is 3. 00:58:58.050 --> 00:59:01.230 We know 3 factorial now is 3 times 2 times 1 based 00:59:01.230 --> 00:59:03.330 on the earlier calls of factorial. 00:59:03.330 --> 00:59:04.560 We're going to go again. 00:59:04.560 --> 00:59:07.670 Now, we're at that very first call a factorial, number is 4. 00:59:07.670 --> 00:59:11.640 Well, the answer here we now know is 4 times 3 times 2 times 00:59:11.640 --> 00:59:13.950 1 based on this call stack we've done. 00:59:13.950 --> 00:59:17.625 And now we can finish that program and type out 24. 00:59:20.410 --> 00:59:25.600 So a bit of a leap of faith wherein you're trying to take for 00:59:25.600 --> 00:59:28.930 granted that your program knows exactly what to do. 00:59:28.930 --> 00:59:30.970 And it will eventually hit this base case. 00:59:30.970 --> 00:59:33.130 If it doesn't hit that base case, we'll know 00:59:33.130 --> 00:59:35.350 that maybe our program will keep running, keep running, keep running. 00:59:35.350 --> 00:59:36.517 And that's not a good thing. 00:59:36.517 --> 00:59:38.410 So we always need this base case here to stop 00:59:38.410 --> 00:59:41.493 the call stack from growing and growing and growing and growing and always 00:59:41.493 --> 00:59:44.138 finding that end case there. 00:59:44.138 --> 00:59:46.930 But certainly, feel free to take some time thinking about this one. 00:59:46.930 --> 00:59:49.750 So what questions do you all have about how this works 00:59:49.750 --> 00:59:52.195 or how the recursion is working here? 00:59:56.570 --> 01:00:00.050 Yes, so your question about, you know how recursion works, 01:00:00.050 --> 01:00:03.930 but how do you know if a recursion is a good approach to a problem? 01:00:03.930 --> 01:00:07.250 And what I encourage you to do is really try to draw things out 01:00:07.250 --> 01:00:10.950 before you end up trying to code a recursive function. 01:00:10.950 --> 01:00:17.120 So similarly, if we go back here, we saw that factorial was we drew things out. 01:00:17.120 --> 01:00:23.430 We saw, hey, I notice that 3 factorial is embedded inside of 4 factorial. 01:00:23.430 --> 01:00:26.630 So maybe it's a good use of a recursive algorithm here. 01:00:26.630 --> 01:00:30.650 If you can find a problem and you find that problem 01:00:30.650 --> 01:00:33.920 is made of a smaller problem that can be solved in the same way, 01:00:33.920 --> 01:00:36.725 that's a hint you might want to use recursion in that instance. 01:00:41.040 --> 01:00:43.685 What other questions are there on recursion in this case? 01:00:54.430 --> 01:00:55.120 Let's see. 01:00:59.118 --> 01:01:01.410 I'm seeing, what do we call the thing we did on line 4? 01:01:01.410 --> 01:01:05.370 So if you scroll up to the top here in our program, 01:01:05.370 --> 01:01:09.180 we'll see on line 4 we declared the function. 01:01:09.180 --> 01:01:11.680 We gave the compiler our prototype. 01:01:11.680 --> 01:01:14.250 So this right here is called our function prototype 01:01:14.250 --> 01:01:16.950 and, more specifically, putting this piece right here 01:01:16.950 --> 01:01:18.690 is declaring our function. 01:01:18.690 --> 01:01:22.950 We're telling c, hey, we have this function that returns an integer. 01:01:22.950 --> 01:01:25.410 It is named factorial and takes an argument 01:01:25.410 --> 01:01:26.880 called number that is an integer. 01:01:26.880 --> 01:01:30.330 And that in respect we're declaring our function there. 01:01:33.550 --> 01:01:35.680 Is there a way to make this code shorter? 01:01:35.680 --> 01:01:36.400 Perhaps. 01:01:36.400 --> 01:01:38.525 I won't go out on a limb and say that this is maybe 01:01:38.525 --> 01:01:40.150 the most short you can make it. 01:01:40.150 --> 01:01:42.350 Maybe there is a way to do it. 01:01:42.350 --> 01:01:45.085 But certainly, if it seems well designed for us here. 01:01:47.760 --> 01:01:51.510 And another question is, can we use a loop here? 01:01:51.510 --> 01:01:53.050 We actually could use a loop here. 01:01:53.050 --> 01:01:55.380 So let's say we didn't want to use recursion. 01:01:55.380 --> 01:01:57.690 Maybe it feels a little too much like a leap of faith. 01:01:57.690 --> 01:02:01.300 So what we'll do is we'll, maybe instead of this, we'll say, 01:02:01.300 --> 01:02:05.670 OK, we know that, when number is 1, we'll go ahead and return 1. 01:02:05.670 --> 01:02:10.350 But otherwise, we know that factorial is really just that number times 1 01:02:10.350 --> 01:02:12.270 less than it times 1 less than it. 01:02:12.270 --> 01:02:13.330 So we could do this. 01:02:13.330 --> 01:02:15.540 We could say something like a for loop. 01:02:15.540 --> 01:02:17.370 We could take for. 01:02:17.370 --> 01:02:24.180 Maybe we'll start at i is equal to our number and go until i is-- 01:02:24.180 --> 01:02:29.510 maybe, let's say, as long as i is greater than 0, 01:02:29.510 --> 01:02:33.290 and then keep subtracting from i as we go through. 01:02:33.290 --> 01:02:38.990 So what we could do is maybe say that our solution is going 01:02:38.990 --> 01:02:45.260 to be first probably equal to number. 01:02:45.260 --> 01:02:52.970 And then we could say solution is equal to that solution times some other-- 01:02:52.970 --> 01:02:54.178 times i, I believe. 01:02:54.178 --> 01:02:56.720 And feel free to correct me if I'm doing anything wrong here. 01:02:56.720 --> 01:02:59.750 I think what might happen though, is we have solution times number. 01:02:59.750 --> 01:03:04.650 Something like this, number minus 1, and so on and so forth. 01:03:04.650 --> 01:03:07.760 But basically what we're doing here is trying to make a loop out 01:03:07.760 --> 01:03:11.660 of this, trying to say, OK, let's start with 4 and multiply 3 to it 01:03:11.660 --> 01:03:14.300 and then 2 to it and then 1 to it through a loop. 01:03:14.300 --> 01:03:15.950 And we could do that. 01:03:15.950 --> 01:03:19.560 But often what happens is that maybe recursion is more elegant solution 01:03:19.560 --> 01:03:20.060 here. 01:03:20.060 --> 01:03:21.840 This seems like much more lines of code. 01:03:21.840 --> 01:03:27.880 So maybe, in this case, we could use our recursive solution that we had before. 01:03:27.880 --> 01:03:32.920 And a question related to this is, can all recursions be rewritten as loops? 01:03:32.920 --> 01:03:35.030 It's a good question. 01:03:35.030 --> 01:03:38.260 I would say that at least some of them could be, as we demonstrated here. 01:03:38.260 --> 01:03:41.350 I think there are some problems though where recursion is really 01:03:41.350 --> 01:03:44.380 going to be helpful for you because what recursion does 01:03:44.380 --> 01:03:47.920 is it allows you to have a whole new smaller 01:03:47.920 --> 01:03:51.100 problem to work with and take a big chunk out of that problem 01:03:51.100 --> 01:03:52.540 and work with that smaller one. 01:03:52.540 --> 01:03:55.750 So often, in computer science, we want to solve bigger problems 01:03:55.750 --> 01:03:57.370 by first solving smaller ones. 01:03:57.370 --> 01:04:00.687 And a loop might not always give you that same leverage 01:04:00.687 --> 01:04:02.770 that you might have by breaking down a big problem 01:04:02.770 --> 01:04:04.910 and making it into a smaller one. 01:04:04.910 --> 01:04:05.785 But a great question. 01:04:09.060 --> 01:04:11.300 Other questions to you on this recursion here? 01:04:20.310 --> 01:04:26.670 All right, so that does just about bring us to the very end of our section. 01:04:26.670 --> 01:04:29.110 We talked about algorithms, how we compare them. 01:04:29.110 --> 01:04:31.260 We talked about structs and how we might use them. 01:04:31.260 --> 01:04:34.980 We talked about recursion, how we can identify recursion and ultimately write 01:04:34.980 --> 01:04:37.200 our own recursive functions. 01:04:37.200 --> 01:04:39.900 As you go off into this week, you will, in fact, 01:04:39.900 --> 01:04:42.570 do your own kind of algorithms that involve structs, 01:04:42.570 --> 01:04:46.060 that might involve recursion, that might involve all these different elements. 01:04:46.060 --> 01:04:48.685 And so I wish you the very best as you're going off and working 01:04:48.685 --> 01:04:49.838 on your own work this week. 01:04:49.838 --> 01:04:51.630 Thank you so much for joining us over Zoom. 01:04:51.630 --> 01:04:53.205 It was wonderful to see you all here. 01:04:53.205 --> 01:04:55.080 Hope to see you in the coming weeks, and I'll 01:04:55.080 --> 01:04:56.955 be happy to stay around and answer questions. 01:04:56.955 --> 01:04:58.490 Thank you all.