1 00:00:00,000 --> 00:00:03,430 2 00:00:03,430 --> 00:00:05,290 CARTER ZENKE: OK, well, hello one and all. 3 00:00:05,290 --> 00:00:07,520 It is so good to see you here over Zoom today. 4 00:00:07,520 --> 00:00:08,710 My name is Carter Zenke. 5 00:00:08,710 --> 00:00:11,080 I am CS50's preceptor here on campus. 6 00:00:11,080 --> 00:00:12,610 I'd love to see you all over Zoom. 7 00:00:12,610 --> 00:00:15,730 I thought we'd do is beginning with a bit of an unusual thing for Zoom, 8 00:00:15,730 --> 00:00:19,360 which is on, the count of three, everyone unmute and say hello. 9 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. 10 00:00:23,450 --> 00:00:26,830 So again, on the count of three, feel free to unmute and you all say hello. 11 00:00:26,830 --> 00:00:31,030 1, 2, 3, unmute and say, hello. 12 00:00:31,030 --> 00:00:32,940 AUDIENCE: Hello. 13 00:00:32,940 --> 00:00:34,930 CARTER ZENKE: Hello. 14 00:00:34,930 --> 00:00:38,770 All right, it's so good to hear your wonderful chorus of voices. 15 00:00:38,770 --> 00:00:42,130 We're here today for a CS50 section, and the goal of sections 16 00:00:42,130 --> 00:00:46,390 will be to review lecture content interactively, to ask questions, 17 00:00:46,390 --> 00:00:47,800 to dive into exercises. 18 00:00:47,800 --> 00:00:50,090 And so today what we'll do is do exactly that. 19 00:00:50,090 --> 00:00:51,660 We'll dive into algorithms. 20 00:00:51,660 --> 00:00:53,410 We're doing some things more interactively 21 00:00:53,410 --> 00:00:55,827 and talking amongst each other for how we might solve some 22 00:00:55,827 --> 00:00:57,730 of these problems in computer science. 23 00:00:57,730 --> 00:01:00,280 24 00:01:00,280 --> 00:01:01,030 All right, sorry. 25 00:01:01,030 --> 00:01:03,700 Hello, everyone, I was unmuted. 26 00:01:03,700 --> 00:01:04,370 I was muted. 27 00:01:04,370 --> 00:01:07,870 So here what we're going to do is talk about CS50 section. 28 00:01:07,870 --> 00:01:10,240 So the goal of section is really to dive into lecture 29 00:01:10,240 --> 00:01:14,530 content interactively, to review content, to ask questions, 30 00:01:14,530 --> 00:01:17,120 to do so through exercises and through each other. 31 00:01:17,120 --> 00:01:20,230 And so today we'll be diving into algorithms and data structures 32 00:01:20,230 --> 00:01:23,630 and a little bit more in terms of recursion as well. 33 00:01:23,630 --> 00:01:27,530 So let's begin, and let's see a few questions for today. 34 00:01:27,530 --> 00:01:31,840 So here, our first question is going to be, how can we compare algorithms? 35 00:01:31,840 --> 00:01:34,240 In lecture, we saw binary search. 36 00:01:34,240 --> 00:01:36,220 We saw linear search. 37 00:01:36,220 --> 00:01:39,280 We also saw things like selection sort and bubble sort. 38 00:01:39,280 --> 00:01:41,650 So how should we compare algorithms and figure out 39 00:01:41,650 --> 00:01:44,615 which one's better than the other for which case. 40 00:01:44,615 --> 00:01:46,240 We're also going to talk about structs. 41 00:01:46,240 --> 00:01:47,890 Why are structs useful? 42 00:01:47,890 --> 00:01:49,330 When would we even use them? 43 00:01:49,330 --> 00:01:51,310 And we'll then talk about recursion. 44 00:01:51,310 --> 00:01:52,480 What is recursion? 45 00:01:52,480 --> 00:01:54,550 How do we build our own recursive algorithms, 46 00:01:54,550 --> 00:01:56,530 and have an exercise for ourselves and actually 47 00:01:56,530 --> 00:01:59,390 write our own recursive algorithm here. 48 00:01:59,390 --> 00:02:02,980 So let's dive first into this idea of how do we compare algorithms. 49 00:02:02,980 --> 00:02:07,560 So we saw in lecture this idea of trying to search for some value. 50 00:02:07,560 --> 00:02:11,830 So here I have maybe an array of different colors from this white color 51 00:02:11,830 --> 00:02:14,050 here to this dark green color. 52 00:02:14,050 --> 00:02:18,230 And let's say I want to find the color white in this array. 53 00:02:18,230 --> 00:02:21,210 Now, knowing we have some indices here, like 0, 54 00:02:21,210 --> 00:02:27,400 1, 2, 3, 4, 5, and 6, where is this white color in this array? 55 00:02:27,400 --> 00:02:30,460 If you have to type in the chat, where is the white color in this array? 56 00:02:30,460 --> 00:02:32,850 What index is it at? 57 00:02:32,850 --> 00:02:35,310 OK, so I'm seeing 2, right? 58 00:02:35,310 --> 00:02:37,020 And it seems pretty obvious here. 59 00:02:37,020 --> 00:02:39,780 We can just see that this white color is right here 60 00:02:39,780 --> 00:02:42,870 in this third spot but index 2. 61 00:02:42,870 --> 00:02:46,050 And maybe, how would we know that this is there? 62 00:02:46,050 --> 00:02:48,120 We eyeball it as humans. 63 00:02:48,120 --> 00:02:50,490 But a computer doesn't necessarily have access 64 00:02:50,490 --> 00:02:52,470 to this entire array of information. 65 00:02:52,470 --> 00:02:54,820 It can only look at one thing at a time. 66 00:02:54,820 --> 00:02:57,720 And so going metaphorically, we might think of the computer 67 00:02:57,720 --> 00:03:00,780 as shining a spotlight on some numbers as we go through 68 00:03:00,780 --> 00:03:03,190 and try to find this white color. 69 00:03:03,190 --> 00:03:06,030 So if we're doing linear search here, trying 70 00:03:06,030 --> 00:03:10,080 to search this array from start to back, we might start on, 71 00:03:10,080 --> 00:03:12,120 let's say, the left side of this array, right? 72 00:03:12,120 --> 00:03:14,700 We might go to that very first location, index 0. 73 00:03:14,700 --> 00:03:17,550 So we'd shine our spotlight on that color there. 74 00:03:17,550 --> 00:03:18,450 Is this white? 75 00:03:18,450 --> 00:03:21,660 Have we found our color? 76 00:03:21,660 --> 00:03:23,850 I'm seeing some head nods. 77 00:03:23,850 --> 00:03:25,290 Maybe in the chat, I'm seeing no. 78 00:03:25,290 --> 00:03:28,270 This is not the color white, so what are we going to do next? 79 00:03:28,270 --> 00:03:32,370 Which number should we go to after 0, if we're doing linear search? 80 00:03:32,370 --> 00:03:33,725 I'm seeing some 1's, right? 81 00:03:33,725 --> 00:03:35,350 OK, let's go to 1 and see what's there. 82 00:03:35,350 --> 00:03:36,930 So let's shine our spotlight there. 83 00:03:36,930 --> 00:03:39,510 And that is not white either. 84 00:03:39,510 --> 00:03:41,100 Maybe we're getting closer. 85 00:03:41,100 --> 00:03:41,850 Maybe not. 86 00:03:41,850 --> 00:03:42,930 We don't quite know. 87 00:03:42,930 --> 00:03:44,910 What's the next one to go to though? 88 00:03:44,910 --> 00:03:45,990 Index 2. 89 00:03:45,990 --> 00:03:47,070 So let's go to 2 now. 90 00:03:47,070 --> 00:03:49,650 So let's go from 1 to 2, adding 1 to our index. 91 00:03:49,650 --> 00:03:51,780 And oh, there is the color white. 92 00:03:51,780 --> 00:03:53,490 So we found it here. 93 00:03:53,490 --> 00:03:57,450 Now, how many steps did it take us to do this linear search to find 94 00:03:57,450 --> 00:03:59,100 the color white? 95 00:03:59,100 --> 00:04:00,150 I'm seeing three steps. 96 00:04:00,150 --> 00:04:01,483 OK, so keep that number in mind. 97 00:04:01,483 --> 00:04:04,860 It took us three steps to find white using linear search here. 98 00:04:04,860 --> 00:04:08,070 All right, so that's one algorithm we could use 99 00:04:08,070 --> 00:04:10,770 to find this color white in this array. 100 00:04:10,770 --> 00:04:13,780 But now let's say this array is sorted. 101 00:04:13,780 --> 00:04:17,130 So we're going from maybe light to dark green now. 102 00:04:17,130 --> 00:04:19,920 And we want to, again, find the color white. 103 00:04:19,920 --> 00:04:22,890 But now that the array is sorted, it enables 104 00:04:22,890 --> 00:04:27,450 this new algorithm called binary search we saw in lecture and through a phone 105 00:04:27,450 --> 00:04:28,920 book example, right? 106 00:04:28,920 --> 00:04:31,322 So if we're going to dim the lights again, 107 00:04:31,322 --> 00:04:33,030 we have to shine our spotlight somewhere. 108 00:04:33,030 --> 00:04:36,060 Now, where should we first shine our light 109 00:04:36,060 --> 00:04:41,010 if we're looking for this first element in binary search now? 110 00:04:41,010 --> 00:04:43,770 I'm seeing this idea of the middle, OK. 111 00:04:43,770 --> 00:04:46,300 We're trying to find the middle of this array. 112 00:04:46,300 --> 00:04:49,440 And if we know that we have-- let's go back a little bit-- 113 00:04:49,440 --> 00:04:54,810 index 6, all the way on this side, maybe our middle index 114 00:04:54,810 --> 00:04:57,060 would be 6 divided by 2. 115 00:04:57,060 --> 00:04:58,230 So 3, right? 116 00:04:58,230 --> 00:05:00,130 That will be the middle index here. 117 00:05:00,130 --> 00:05:00,900 So let's go to 3. 118 00:05:00,900 --> 00:05:02,610 So we'll dim the lights. 119 00:05:02,610 --> 00:05:04,850 We'll then look at 3. 120 00:05:04,850 --> 00:05:08,830 Now, is 3 white? 121 00:05:08,830 --> 00:05:10,950 I'm seeing no, right? 122 00:05:10,950 --> 00:05:12,800 So where should we look now? 123 00:05:12,800 --> 00:05:16,910 If we know that we're sorting our array from light to dark, 124 00:05:16,910 --> 00:05:18,350 we might want to look left, right? 125 00:05:18,350 --> 00:05:21,020 But at what index should we look now? 126 00:05:21,020 --> 00:05:22,890 We might divide 3 in half again. 127 00:05:22,890 --> 00:05:26,300 So 3 divided by 2 is-- well, it's 1.5. 128 00:05:26,300 --> 00:05:29,010 Maybe we round down and go to one, right? 129 00:05:29,010 --> 00:05:31,730 So let's go from 3 down to 1. 130 00:05:31,730 --> 00:05:33,530 And we're not quite there. 131 00:05:33,530 --> 00:05:39,970 Where do we go again now if we're sorting from light to dark green? 132 00:05:39,970 --> 00:05:41,400 I'm seeing some left in the chat. 133 00:05:41,400 --> 00:05:42,608 OK, let's go one on the left. 134 00:05:42,608 --> 00:05:46,210 1 divided by 2 is 0.5, but we can't go to index 0.5. 135 00:05:46,210 --> 00:05:48,130 Let's round down, and let's go to 0. 136 00:05:48,130 --> 00:05:53,110 So we found white here now at this 0th index. 137 00:05:53,110 --> 00:05:58,150 And now, again, how many steps did this binary search take in this case? 138 00:05:58,150 --> 00:06:00,100 Again, took us three steps, right? 139 00:06:00,100 --> 00:06:03,130 So if we're trying to compare these two algorithms, 140 00:06:03,130 --> 00:06:05,140 we might talk about their running time, which 141 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 142 00:06:10,270 --> 00:06:12,430 looking for in this case. 143 00:06:12,430 --> 00:06:15,760 Well, we might compare linear search in binary search like this. 144 00:06:15,760 --> 00:06:18,590 How many steps did they take us in this case? 145 00:06:18,590 --> 00:06:21,220 And so again, linear search, how many steps does that 146 00:06:21,220 --> 00:06:25,080 take us for this particular case here? 147 00:06:25,080 --> 00:06:26,610 I'm seeing some 3s. 148 00:06:26,610 --> 00:06:28,770 So linear search took us three steps. 149 00:06:28,770 --> 00:06:33,480 And binary search, how many steps did that take us again? 150 00:06:33,480 --> 00:06:35,850 Also took us three. 151 00:06:35,850 --> 00:06:39,695 OK, so which algorithm is better than the other? 152 00:06:39,695 --> 00:06:41,820 Anyone want to raise their hand, we can call on you 153 00:06:41,820 --> 00:06:44,850 and maybe tell us which algorithm you think is better here? 154 00:06:44,850 --> 00:06:50,120 155 00:06:50,120 --> 00:06:52,220 Or maybe type in the chat if you'd like. 156 00:06:52,220 --> 00:06:53,915 Which algorithm would you choose? 157 00:06:53,915 --> 00:06:56,510 158 00:06:56,510 --> 00:07:00,040 So I'm seeing some binary. 159 00:07:00,040 --> 00:07:02,680 And now my question here is, why would we choose binary, right? 160 00:07:02,680 --> 00:07:06,530 Each one, linear search and binary search, took three steps. 161 00:07:06,530 --> 00:07:10,680 So is one really better than the other? 162 00:07:10,680 --> 00:07:13,480 Maybe on the chat, what do you think? 163 00:07:13,480 --> 00:07:15,620 So I'm seeing binary search is more dynamic. 164 00:07:15,620 --> 00:07:18,555 165 00:07:18,555 --> 00:07:19,805 It depends on the arrangement. 166 00:07:19,805 --> 00:07:23,450 So there's this idea that the input we had right now 167 00:07:23,450 --> 00:07:25,400 was a very particular input. 168 00:07:25,400 --> 00:07:28,790 And for this single input, linear search and binary search 169 00:07:28,790 --> 00:07:30,530 did take the same number of steps. 170 00:07:30,530 --> 00:07:32,780 But this isn't quite the question we want 171 00:07:32,780 --> 00:07:36,650 to be asking when we're talking about running time for algorithms. 172 00:07:36,650 --> 00:07:39,650 Often, what we want to ask instead is not 173 00:07:39,650 --> 00:07:42,150 how many steps we take for a single input 174 00:07:42,150 --> 00:07:47,000 but, in general, for any input, what is the most number of steps 175 00:07:47,000 --> 00:07:49,580 my algorithm will ever take, right? 176 00:07:49,580 --> 00:07:52,190 And another way of asking this question is, for maybe 177 00:07:52,190 --> 00:07:55,070 the worst case input, if I were to give my algorithm 178 00:07:55,070 --> 00:08:02,060 a completely unsorted list, what number of steps would always run faster then? 179 00:08:02,060 --> 00:08:03,740 So let's take a look at this. 180 00:08:03,740 --> 00:08:06,530 If we call this the upper bound for our algorithm, 181 00:08:06,530 --> 00:08:11,360 meaning that this algorithm will never run slower than this number of steps, 182 00:08:11,360 --> 00:08:14,840 we might say that linear search takes how many steps? 183 00:08:14,840 --> 00:08:18,980 Let's assume we have maybe n elements in our array. 184 00:08:18,980 --> 00:08:22,010 In this case, this most recent example, we had seven. 185 00:08:22,010 --> 00:08:26,150 How many steps would linear search take in this case? 186 00:08:26,150 --> 00:08:30,080 So I'm seeing about n steps, right? 187 00:08:30,080 --> 00:08:33,500 Let's say we have seven elements, it would take us maybe seven steps 188 00:08:33,500 --> 00:08:35,960 in the worst case to find that number if it's all 189 00:08:35,960 --> 00:08:38,190 the way at the very end of our array. 190 00:08:38,190 --> 00:08:40,700 So linear search might take 7 steps in the worst case. 191 00:08:40,700 --> 00:08:42,740 Or in general, if we have n elements, it might 192 00:08:42,740 --> 00:08:47,540 take n steps, one step for every element in that array. 193 00:08:47,540 --> 00:08:50,930 But binary search though might be a little different 194 00:08:50,930 --> 00:08:53,420 because we're dividing the problem in 1/2 and 1/2 and 1/2. 195 00:08:53,420 --> 00:08:56,690 And so what are we seeing now? 196 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. 197 00:09:02,210 --> 00:09:08,488 Any other ideas for how many steps binary search might take in this case? 198 00:09:08,488 --> 00:09:11,320 I'm seeing n minus 1. 199 00:09:11,320 --> 00:09:13,450 I'm seeing log n. 200 00:09:13,450 --> 00:09:17,140 And indeed, so binary search would take about log n steps 201 00:09:17,140 --> 00:09:20,620 if we had n number of elements to search for here. 202 00:09:20,620 --> 00:09:23,890 And people who said n over 2, you're not quite wrong, right, 203 00:09:23,890 --> 00:09:28,300 because what we can do is we can take our array of seven elements. 204 00:09:28,300 --> 00:09:30,460 We can divide it in 1/2. 205 00:09:30,460 --> 00:09:31,810 We've looked at one element. 206 00:09:31,810 --> 00:09:35,650 Let's divide it in 1/2 again and divide it in 1/2 again. 207 00:09:35,650 --> 00:09:38,470 And this idea of dividing things in 1/2, in 1/2, in 1/2 208 00:09:38,470 --> 00:09:43,390 is a logarithm that we need twice as many elements to do one more 209 00:09:43,390 --> 00:09:45,040 step in our algorithm now. 210 00:09:45,040 --> 00:09:48,790 So binary search in this case, in the very worst case, the upper bound 211 00:09:48,790 --> 00:09:51,550 of the binary search algorithm is log of n steps. 212 00:09:51,550 --> 00:09:54,640 And now the question becomes, which one would you rather do? 213 00:09:54,640 --> 00:09:59,900 Would you rather do linear search, or would you rather do binary search? 214 00:09:59,900 --> 00:10:01,760 And so I'm seeing binary, right, because we 215 00:10:01,760 --> 00:10:05,030 know that, for these really worst case inputs, 216 00:10:05,030 --> 00:10:08,120 binary search might, in fact, be better. 217 00:10:08,120 --> 00:10:12,560 And this is OK for now, and we can talk about things in terms 218 00:10:12,560 --> 00:10:14,030 of the number of steps they take. 219 00:10:14,030 --> 00:10:16,940 But in computer science, to be a little more precise, 220 00:10:16,940 --> 00:10:19,850 we try to say that something is in the running time, 221 00:10:19,850 --> 00:10:21,742 on the order of something. 222 00:10:21,742 --> 00:10:23,450 And this is because, in computer science, 223 00:10:23,450 --> 00:10:26,480 we're often not trying to search an array of seven elements 224 00:10:26,480 --> 00:10:28,010 or an array of eight elements. 225 00:10:28,010 --> 00:10:31,160 We're often trying to search an array of maybe a billion elements 226 00:10:31,160 --> 00:10:32,420 or a million elements. 227 00:10:32,420 --> 00:10:34,940 And so who cares if something takes maybe a billion 228 00:10:34,940 --> 00:10:37,520 plus 1 steps or a billion minus 1 steps. 229 00:10:37,520 --> 00:10:40,970 It's on the order of about a billion steps, right? 230 00:10:40,970 --> 00:10:44,780 And so we saw in lecture this idea of these algorithms that can 231 00:10:44,780 --> 00:10:46,700 take a certain amount of running time. 232 00:10:46,700 --> 00:10:50,120 And here, if we look at the bottom of our graph here, 233 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 234 00:10:55,430 --> 00:10:58,710 to solve that problem going up as we go up as well. 235 00:10:58,710 --> 00:11:03,110 So notice how maybe we have two different algorithms, this red line 236 00:11:03,110 --> 00:11:08,030 and this yellow line, one taking n steps, one taking n over 2 steps, 237 00:11:08,030 --> 00:11:13,590 this other one here taking log 2 of n steps here. 238 00:11:13,590 --> 00:11:15,990 Now, that's all fine and good. 239 00:11:15,990 --> 00:11:18,260 We can be that precise, but often, when working 240 00:11:18,260 --> 00:11:21,140 with a billion elements, a million elements, and so on, 241 00:11:21,140 --> 00:11:26,210 we might talk about things being on the order of some number here, 242 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, 243 00:11:32,390 --> 00:11:33,420 and so on. 244 00:11:33,420 --> 00:11:36,350 So here, we might say that this is the upper bound, noting that 245 00:11:36,350 --> 00:11:38,450 with the big O notation. 246 00:11:38,450 --> 00:11:41,060 And when we do that, we get rid of that division. 247 00:11:41,060 --> 00:11:43,665 We say, OK, we don't need that divided by 2 there. 248 00:11:43,665 --> 00:11:46,040 And then similarly, we might also do something like this. 249 00:11:46,040 --> 00:11:50,690 We might say, if we zoom out, these n over 2 and the n, 250 00:11:50,690 --> 00:11:51,840 they look very similar. 251 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 252 00:11:55,490 --> 00:11:59,280 looks very different log n over here. 253 00:11:59,280 --> 00:12:03,080 So we might then characterize linear search and binary search like this 254 00:12:03,080 --> 00:12:09,060 as being in big O of n and big O of log n, respectively. 255 00:12:09,060 --> 00:12:12,240 So what questions do you all have on this big O 256 00:12:12,240 --> 00:12:13,880 notation or these running times? 257 00:12:13,880 --> 00:12:15,710 Happy to help answer some of these. 258 00:12:15,710 --> 00:12:25,380 259 00:12:25,380 --> 00:12:29,132 All right, seeing none so far. 260 00:12:29,132 --> 00:12:30,840 Oh, I'm seeing some question in the chat. 261 00:12:30,840 --> 00:12:33,390 262 00:12:33,390 --> 00:12:36,580 Does binary look at all the possibilities? 263 00:12:36,580 --> 00:12:40,230 So binary search doesn't necessarily look at all of the possibilities. 264 00:12:40,230 --> 00:12:45,720 What it does instead is it takes for granted that a list is sorted. 265 00:12:45,720 --> 00:12:49,620 And because of that we don't need to look at every possible element. 266 00:12:49,620 --> 00:12:52,020 If we know that we go to the middle one and we 267 00:12:52,020 --> 00:12:55,920 find maybe a number that's too high or a color that's too dark, 268 00:12:55,920 --> 00:12:58,290 well, we know we should look to the left of that number. 269 00:12:58,290 --> 00:12:59,998 If though we're looking for a number that 270 00:12:59,998 --> 00:13:02,910 is greater than that number or darker than that color, 271 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. 272 00:13:05,820 --> 00:13:09,870 And so binary search doesn't take n steps, one for every element. 273 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. 274 00:13:14,235 --> 00:13:18,070 275 00:13:18,070 --> 00:13:21,280 I'm also seeing what if it's an unordered list? 276 00:13:21,280 --> 00:13:23,870 What will be the running time of binary search? 277 00:13:23,870 --> 00:13:26,050 And by unordered perhaps we mean unsorted. 278 00:13:26,050 --> 00:13:30,100 So let's say maybe our list is not maybe sorted from light to dark 279 00:13:30,100 --> 00:13:32,350 or from lowest to highest, and so on. 280 00:13:32,350 --> 00:13:35,960 Well, in that case, binary search breaks down, doesn't quite work. 281 00:13:35,960 --> 00:13:39,610 So the prerequisite for binary search is that our list is indeed sorted. 282 00:13:39,610 --> 00:13:43,187 If it's not sorted, what will happen is it will go to that middle element, 283 00:13:43,187 --> 00:13:46,270 and we won't really know anything about where the other elements might be. 284 00:13:46,270 --> 00:13:48,340 We won't know if we can look left or look right. 285 00:13:48,340 --> 00:13:50,780 And so binary search really breaks down in that case. 286 00:13:50,780 --> 00:13:54,850 And we're forced to use linear search of looking at every element step by step 287 00:13:54,850 --> 00:13:58,240 by step here. 288 00:13:58,240 --> 00:14:00,790 And a question about what is the use of big O notation? 289 00:14:00,790 --> 00:14:03,830 Why would we even care about having this big O notation here? 290 00:14:03,830 --> 00:14:05,680 Well, one reason we might care about this 291 00:14:05,680 --> 00:14:08,230 is because we care about this question earlier about, 292 00:14:08,230 --> 00:14:12,790 for any input, what is the most number of steps my algorithm will ever take? 293 00:14:12,790 --> 00:14:15,670 What is the very worst case running time of this algorithm? 294 00:14:15,670 --> 00:14:17,860 And so this big O notation is saying, OK, this 295 00:14:17,860 --> 00:14:23,560 is going to be the number of steps your algorithm will always run faster than, 296 00:14:23,560 --> 00:14:26,440 so to speak, will never run more than this number of steps, 297 00:14:26,440 --> 00:14:31,580 in general, on the order of this many steps, so to speak. 298 00:14:31,580 --> 00:14:33,770 All right, so let's keep going. 299 00:14:33,770 --> 00:14:37,890 And we have this question of what is the most number of steps 300 00:14:37,890 --> 00:14:39,140 this algorithm will ever take? 301 00:14:39,140 --> 00:14:41,510 But also, we can ask another question of, 302 00:14:41,510 --> 00:14:44,810 what is the least number of tests my algorithm could ever take? 303 00:14:44,810 --> 00:14:47,780 So we answered this one already using big O notation. 304 00:14:47,780 --> 00:14:52,640 But using omega notation, this different Greek symbol, this other question. 305 00:14:52,640 --> 00:14:55,520 What is the least number of tests my algorithm will ever take? 306 00:14:55,520 --> 00:14:58,790 Or another way of saying this is, for the best case input, 307 00:14:58,790 --> 00:15:01,190 how many steps will my algorithm take? 308 00:15:01,190 --> 00:15:05,120 And so for example here, we could go to linear search and binary search, 309 00:15:05,120 --> 00:15:10,590 and each one maybe takes one step in the very best case. 310 00:15:10,590 --> 00:15:12,650 And what kind of case would this be where 311 00:15:12,650 --> 00:15:16,340 linear search takes one step and binary search takes one step? 312 00:15:16,340 --> 00:15:20,040 What kind of input would we give here? 313 00:15:20,040 --> 00:15:21,090 Anyone in the chat? 314 00:15:21,090 --> 00:15:26,730 315 00:15:26,730 --> 00:15:30,220 Maybe another way of phrasing this is, at what point 316 00:15:30,220 --> 00:15:33,430 will we get lucky with linear search or binary search? 317 00:15:33,430 --> 00:15:37,280 318 00:15:37,280 --> 00:15:41,180 Yeah, so maybe-- I'm seeing-- so maybe with linear search, 319 00:15:41,180 --> 00:15:44,540 maybe our element is that very first one at the zero index, right? 320 00:15:44,540 --> 00:15:46,550 In that case, linear search took one step. 321 00:15:46,550 --> 00:15:48,020 We can end early. 322 00:15:48,020 --> 00:15:51,502 And similarly, for binary search, maybe our element is right in the middle. 323 00:15:51,502 --> 00:15:54,210 So we can just go right to the middle and find the element there. 324 00:15:54,210 --> 00:15:57,920 So this is why, in the best case, our lower bound for linear search 325 00:15:57,920 --> 00:15:59,930 and binary search will be one step. 326 00:15:59,930 --> 00:16:05,750 These algorithms will, in effect, will never be, let's see, 327 00:16:05,750 --> 00:16:09,530 never be slower than-- 328 00:16:09,530 --> 00:16:11,930 well, let me think about that. 329 00:16:11,930 --> 00:16:15,960 In the very best case, lower bound will be one step and one step here. 330 00:16:15,960 --> 00:16:19,640 And so what we often use for this notation is this omega of 1. 331 00:16:19,640 --> 00:16:22,340 So we're saying this is on the order of about one step 332 00:16:22,340 --> 00:16:28,120 or a finite number of steps for linear search and binary search here. 333 00:16:28,120 --> 00:16:32,995 All right, so what questions do you all have on this omega notation? 334 00:16:32,995 --> 00:16:44,280 335 00:16:44,280 --> 00:16:47,310 All right, so seeing no questions here, let's keep going. 336 00:16:47,310 --> 00:16:48,510 And let's try to find-- 337 00:16:48,510 --> 00:16:51,000 let's try to analyze the runtime of a new algorithm 338 00:16:51,000 --> 00:16:54,120 that we did see in lecture, of course, one called selection sort, right? 339 00:16:54,120 --> 00:16:57,900 So in selection sort, we want to basically go through every element 340 00:16:57,900 --> 00:16:59,290 and sort this list. 341 00:16:59,290 --> 00:17:02,520 And here we have an array that is currently unsorted. 342 00:17:02,520 --> 00:17:04,680 But we do want to sort it in the end. 343 00:17:04,680 --> 00:17:07,920 And selection sort has an algorithm that works like this. 344 00:17:07,920 --> 00:17:11,819 It will say, let's start by looking at that very first element, 345 00:17:11,819 --> 00:17:15,300 and let's go through and find the very smallest element in our list 346 00:17:15,300 --> 00:17:17,400 and put it at the very beginning now. 347 00:17:17,400 --> 00:17:23,348 So currently, if we can only look at one element, let's say this 5 here, 348 00:17:23,348 --> 00:17:25,140 well, that's currently the smallest number. 349 00:17:25,140 --> 00:17:27,119 But let's look at 3. 350 00:17:27,119 --> 00:17:28,500 Is 3 smaller than 5? 351 00:17:28,500 --> 00:17:29,685 Give me a yes or a no. 352 00:17:29,685 --> 00:17:32,410 353 00:17:32,410 --> 00:17:33,790 Yeah, so 3 is smaller than 5. 354 00:17:33,790 --> 00:17:35,660 So 3 is our new smallest number. 355 00:17:35,660 --> 00:17:36,850 So let's go again. 356 00:17:36,850 --> 00:17:39,913 2 is certainly smaller than 3, and so is 1. 357 00:17:39,913 --> 00:17:41,830 And if we were to go through this entire list, 358 00:17:41,830 --> 00:17:46,850 we would see that 1 is indeed that smallest number here. 359 00:17:46,850 --> 00:17:51,660 So what do we do with 1 if we want to sort this list? 360 00:17:51,660 --> 00:17:53,160 We found the smallest one currently. 361 00:17:53,160 --> 00:17:54,390 Where do we put the 1? 362 00:17:54,390 --> 00:17:57,100 363 00:17:57,100 --> 00:17:59,770 Move it to the very first element, or swap it with 5. 364 00:17:59,770 --> 00:18:04,660 So we'll say, let's put 1 where 5 is and 5 where 1 is. 365 00:18:04,660 --> 00:18:07,710 So now we know that 1 is in the right space. 366 00:18:07,710 --> 00:18:09,720 Now, our list is not quite sorted. 367 00:18:09,720 --> 00:18:11,760 We have 1, 3, 4, 8, 2, 5. 368 00:18:11,760 --> 00:18:13,770 That's not quite what we want yet. 369 00:18:13,770 --> 00:18:16,690 What we'll do instead is keep going through that list. 370 00:18:16,690 --> 00:18:20,310 We'll say, OK, well, let's find the smallest number in this list. 371 00:18:20,310 --> 00:18:22,590 3 seems pretty small. 372 00:18:22,590 --> 00:18:25,470 4 is higher, but 2 is smaller. 373 00:18:25,470 --> 00:18:29,230 And 2, right, as people are saying, is going to be our smallest number here. 374 00:18:29,230 --> 00:18:30,660 So what do we do with the 2 now? 375 00:18:30,660 --> 00:18:33,520 376 00:18:33,520 --> 00:18:34,780 2 will swap with 3. 377 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. 378 00:18:38,530 --> 00:18:41,620 And now we're getting a little closer to having this list sorted. 379 00:18:41,620 --> 00:18:44,620 So what we'll do is we'll go ahead and find the next smallest 380 00:18:44,620 --> 00:18:46,610 number in the numbers that remain. 381 00:18:46,610 --> 00:18:49,810 We'll look at 4, 8, 3, 5, 7, and 6, and we'll 382 00:18:49,810 --> 00:18:52,115 find that ultimately 3 is that new smallest number. 383 00:18:52,115 --> 00:18:52,990 What do we do with 3? 384 00:18:52,990 --> 00:18:54,650 Swap it with 4, as people are saying. 385 00:18:54,650 --> 00:18:56,740 OK, now let's find the 4. 386 00:18:56,740 --> 00:18:58,930 Let's put that, top it with 8. 387 00:18:58,930 --> 00:19:02,530 Now, we'll find the next smallest, which will be 5. 388 00:19:02,530 --> 00:19:05,290 Then we'll find, in this case, 6. 389 00:19:05,290 --> 00:19:07,570 So 6 will go up here. 390 00:19:07,570 --> 00:19:10,570 And finally, we'll try to find the smallest again. 391 00:19:10,570 --> 00:19:11,320 That's 7. 392 00:19:11,320 --> 00:19:13,930 Smallest again, and that's 8. 393 00:19:13,930 --> 00:19:16,570 All right, so this is selection sort. 394 00:19:16,570 --> 00:19:20,830 And we might want to analyze the runtime of selection sort. 395 00:19:20,830 --> 00:19:24,550 How many steps does this take? 396 00:19:24,550 --> 00:19:29,470 If we were to give an upper bound in omega notation, or not omega, sorry, 397 00:19:29,470 --> 00:19:35,670 in big O notation, what would selection sort run in? 398 00:19:35,670 --> 00:19:41,770 If we're doing maybe a certain number of steps for every element, 399 00:19:41,770 --> 00:19:43,330 what might we do here? 400 00:19:43,330 --> 00:19:45,900 401 00:19:45,900 --> 00:19:51,520 OK, so I'm seeing something like n squared. 402 00:19:51,520 --> 00:19:53,290 And let's get some intuition for this. 403 00:19:53,290 --> 00:19:56,220 So let's say, if we go back up to these slides here, 404 00:19:56,220 --> 00:20:00,560 notice how, if we go back to this unsorted list, 405 00:20:00,560 --> 00:20:06,380 we started by looking at the 5 and trying to find 406 00:20:06,380 --> 00:20:08,360 the very smallest element in this list. 407 00:20:08,360 --> 00:20:09,800 That took us n steps. 408 00:20:09,800 --> 00:20:12,450 We had to go through every element to find the smallest. 409 00:20:12,450 --> 00:20:14,310 That's n steps here. 410 00:20:14,310 --> 00:20:17,950 So n steps to put the 1 in the right place. 411 00:20:17,950 --> 00:20:20,820 But now we have to go through another about n steps 412 00:20:20,820 --> 00:20:23,400 to put the 2 in the right place. 413 00:20:23,400 --> 00:20:27,780 And have to go through another n steps put the 3 in the right place, 414 00:20:27,780 --> 00:20:30,430 and another n steps to put the 4 in the right place. 415 00:20:30,430 --> 00:20:35,510 And so we're doing n steps how many times? 416 00:20:35,510 --> 00:20:41,110 How many times are we doing n steps to find that smallest number? 417 00:20:41,110 --> 00:20:43,390 We're doing it n times or, in this case, 8, right? 418 00:20:43,390 --> 00:20:46,210 So if there are eight elements, we're doing it n times. 419 00:20:46,210 --> 00:20:51,670 So here, we're thinking of selection sort really is big O of n squared. 420 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. 421 00:20:59,310 --> 00:21:06,510 OK, now though, we need to figure out the omega notation, that lower bound. 422 00:21:06,510 --> 00:21:08,475 How could we figure that out? 423 00:21:08,475 --> 00:21:11,680 424 00:21:11,680 --> 00:21:14,530 Or if we gave it maybe an already sorted list, in the best 425 00:21:14,530 --> 00:21:16,660 case, what might selection sort do? 426 00:21:16,660 --> 00:21:20,400 427 00:21:20,400 --> 00:21:22,500 Yeah, so I'm seeing a few answers. 428 00:21:22,500 --> 00:21:24,120 I'm seeing O of 1. 429 00:21:24,120 --> 00:21:27,400 I'm seeing O of n, O of n squared. 430 00:21:27,400 --> 00:21:30,840 And in this case, if selection isn't optimized, 431 00:21:30,840 --> 00:21:34,080 selection sort will take an already sorted list, one 432 00:21:34,080 --> 00:21:36,780 that looks a bit like this, and still try to do those swaps, 433 00:21:36,780 --> 00:21:40,450 it'll take it a whole n steps to find that smallest number, 434 00:21:40,450 --> 00:21:42,840 put it in the right place, go to the next number, 435 00:21:42,840 --> 00:21:44,947 do another n steps to put it in the right place. 436 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. 437 00:21:48,030 --> 00:21:49,650 It isn't going to end early. 438 00:21:49,650 --> 00:21:53,130 And so selection sort will still be in omega of n 439 00:21:53,130 --> 00:21:57,630 squared, meaning that the upper bound and the lower bound for this algorithm 440 00:21:57,630 --> 00:21:59,140 are really the same. 441 00:21:59,140 --> 00:22:01,320 And that's where we might use this theta notation 442 00:22:01,320 --> 00:22:03,070 that I saw some people referencing earlier 443 00:22:03,070 --> 00:22:05,280 to say that these upper bounds and these lower bounds 444 00:22:05,280 --> 00:22:07,720 are the same in this instance. 445 00:22:07,720 --> 00:22:11,730 So what questions do you all have on upper bounds and lower bounds 446 00:22:11,730 --> 00:22:13,575 and selection sort in this case? 447 00:22:13,575 --> 00:22:15,542 448 00:22:15,542 --> 00:22:17,500 So I'm seeing a question about how do we reason 449 00:22:17,500 --> 00:22:19,990 about spending time sorting a list in order to be 450 00:22:19,990 --> 00:22:21,740 able to use a faster search later on? 451 00:22:21,740 --> 00:22:22,700 It's a good question. 452 00:22:22,700 --> 00:22:27,010 So we saw that with binary search that's faster than linear search, 453 00:22:27,010 --> 00:22:29,560 but it takes time to sort something, right? 454 00:22:29,560 --> 00:22:31,010 So how do we reason about that? 455 00:22:31,010 --> 00:22:35,350 Well, we might do is figure out what are the upper bound and lower bound 456 00:22:35,350 --> 00:22:36,730 for our sorting algorithm? 457 00:22:36,730 --> 00:22:39,310 And are we willing to spend the amount of time 458 00:22:39,310 --> 00:22:43,280 to then get that much faster algorithm for searching later on? 459 00:22:43,280 --> 00:22:46,900 And if you are maybe often searching, maybe it 460 00:22:46,900 --> 00:22:51,400 makes sense to spend that time to sort first and then have that faster search. 461 00:22:51,400 --> 00:22:54,255 If though you're only searching occasionally or maybe 462 00:22:54,255 --> 00:22:56,380 you're not even really searching a data set at all, 463 00:22:56,380 --> 00:22:58,970 maybe it doesn't make sense to sort it in that case. 464 00:22:58,970 --> 00:23:01,150 So maybe it comes into play with what do you 465 00:23:01,150 --> 00:23:05,560 want to do with your list in that case. 466 00:23:05,560 --> 00:23:13,450 Yeah, and so I'm seeing what's the main difference between the big O notation 467 00:23:13,450 --> 00:23:14,750 and omega notation? 468 00:23:14,750 --> 00:23:18,530 So really, the main difference is that they're asking two different questions. 469 00:23:18,530 --> 00:23:22,180 The big O notation is asking, in the very worst case, 470 00:23:22,180 --> 00:23:25,450 how about how many steps will my algorithm take? 471 00:23:25,450 --> 00:23:29,530 The omega notation is asking, in the very best case, about how 472 00:23:29,530 --> 00:23:31,240 many steps of my algorithm take? 473 00:23:31,240 --> 00:23:34,600 And we often say that the big O notation symbolizes 474 00:23:34,600 --> 00:23:38,710 the upper bound for the algorithm, meaning that our algorithm will never 475 00:23:38,710 --> 00:23:40,780 run slower than this. 476 00:23:40,780 --> 00:23:43,420 And similarly, for the lower bound, we're 477 00:23:43,420 --> 00:23:46,870 saying that our algorithm will never run faster than this, 478 00:23:46,870 --> 00:23:52,080 will never run faster then, at least, the omega notation down here. 479 00:23:52,080 --> 00:23:55,550 Answer your question too about how do we use this in practice? 480 00:23:55,550 --> 00:23:57,560 Would we compare algorithms or things like that? 481 00:23:57,560 --> 00:23:58,640 And certainly, you would. 482 00:23:58,640 --> 00:24:01,800 So let's say you're working on an application and you want to figure out, 483 00:24:01,800 --> 00:24:05,390 is it worthwhile for me to use this algorithm or that algorithm? 484 00:24:05,390 --> 00:24:08,300 And often, what you'll do is, before you even write some code, 485 00:24:08,300 --> 00:24:10,770 you'll figure out what algorithm you want to use. 486 00:24:10,770 --> 00:24:14,450 And so these running times can be a clue to you what kind of algorithm 487 00:24:14,450 --> 00:24:16,468 is best for your particular data set. 488 00:24:16,468 --> 00:24:19,010 And once you know that, you can then go off and find the time 489 00:24:19,010 --> 00:24:20,370 to write that algorithm. 490 00:24:20,370 --> 00:24:22,760 But often, it's good to know which one to choose 491 00:24:22,760 --> 00:24:26,300 before you spend all that time writing the algorithm you want to write here. 492 00:24:26,300 --> 00:24:29,340 493 00:24:29,340 --> 00:24:34,750 All right, so these are all really good questions. 494 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. 495 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 496 00:24:44,980 --> 00:24:49,330 where a struct is simply some combination of data types. 497 00:24:49,330 --> 00:24:52,360 And a question we might ask is, when would we even use structs? 498 00:24:52,360 --> 00:24:56,650 If we already have strings, we already have INTs, we already have Booleans, 499 00:24:56,650 --> 00:25:00,520 why do we need a struct, this new structure we could use in our program? 500 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 501 00:25:04,690 --> 00:25:05,802 people in our program? 502 00:25:05,802 --> 00:25:07,510 Let's say we want to write a program that 503 00:25:07,510 --> 00:25:09,968 represents maybe political candidates, as you might work on 504 00:25:09,968 --> 00:25:11,350 in the problem set this week. 505 00:25:11,350 --> 00:25:13,090 How could we do this? 506 00:25:13,090 --> 00:25:18,870 Or what information would we store about these candidates? 507 00:25:18,870 --> 00:25:19,770 So I'm seeing names. 508 00:25:19,770 --> 00:25:21,463 We might want to store names. 509 00:25:21,463 --> 00:25:22,380 I'm seeing your party. 510 00:25:22,380 --> 00:25:24,030 Might want to store their party. 511 00:25:24,030 --> 00:25:28,640 Other things too I want to reference about these candidates here. 512 00:25:28,640 --> 00:25:34,370 Maybe gender, position, maybe their height, right? 513 00:25:34,370 --> 00:25:37,140 So there are lots of things we could store about these candidates 514 00:25:37,140 --> 00:25:39,120 to represent them in our data structure. 515 00:25:39,120 --> 00:25:42,200 And often, I would bet you that we can't represent a candidate 516 00:25:42,200 --> 00:25:43,940 with just a single data type. 517 00:25:43,940 --> 00:25:46,048 I could represent their name, but there's 518 00:25:46,048 --> 00:25:48,965 other information I want to couple with that or put together with that 519 00:25:48,965 --> 00:25:51,470 that I need to use a struct for. 520 00:25:51,470 --> 00:25:56,420 So for example, let's say we wanted to make this structure for candidates. 521 00:25:56,420 --> 00:26:01,760 We wanted to make this new type, so to speak, called candidate in our program. 522 00:26:01,760 --> 00:26:04,760 Well, what we could do is use this kind of syntax. 523 00:26:04,760 --> 00:26:09,758 We could say let's make ourselves, essentially, a new type, roughly 524 00:26:09,758 --> 00:26:12,050 a type, not necessarily a type like a string or an int, 525 00:26:12,050 --> 00:26:15,950 but a new combination data type we could use throughout our program. 526 00:26:15,950 --> 00:26:19,220 And this typedef is helpful because it's basically helping us define-- 527 00:26:19,220 --> 00:26:20,780 that's where the def comes from-- 528 00:26:20,780 --> 00:26:22,700 a new type, right? 529 00:26:22,700 --> 00:26:26,640 The next piece we see is this struct, that struct keyword at the very top 530 00:26:26,640 --> 00:26:27,140 there. 531 00:26:27,140 --> 00:26:31,070 And that's saying we're going to have some combination of basic types, 532 00:26:31,070 --> 00:26:35,610 like string and int, that will form our candidate here. 533 00:26:35,610 --> 00:26:39,840 So we'll have the name of that down below, our candidate right here. 534 00:26:39,840 --> 00:26:44,570 And then on the inside we'll say, what are the basic types that are inside 535 00:26:44,570 --> 00:26:45,480 of this structure? 536 00:26:45,480 --> 00:26:49,700 In this case, we'll have a candidate be maybe a string for their name 537 00:26:49,700 --> 00:26:51,770 and an integer for their votes. 538 00:26:51,770 --> 00:26:54,110 And these two pieces of data will be tied together 539 00:26:54,110 --> 00:26:58,290 in this new structure called a candidate. 540 00:26:58,290 --> 00:27:00,360 And this is helpful because we can actually 541 00:27:00,360 --> 00:27:05,100 have maybe a single variable that keeps track of both 542 00:27:05,100 --> 00:27:06,820 of these information at the same time. 543 00:27:06,820 --> 00:27:10,920 So let's say we want to make a new variable called president. 544 00:27:10,920 --> 00:27:14,430 Well, president has this type called candidate 545 00:27:14,430 --> 00:27:15,990 that we just defined earlier, right? 546 00:27:15,990 --> 00:27:20,280 And we know that a candidate has a name and a number of votes. 547 00:27:20,280 --> 00:27:23,313 So if we wanted to keep these two pieces of data together, their name 548 00:27:23,313 --> 00:27:24,730 and their votes, we could do this. 549 00:27:24,730 --> 00:27:28,110 We could say, maybe the president's name is Alyssa. 550 00:27:28,110 --> 00:27:30,280 And the president has maybe 10 votes. 551 00:27:30,280 --> 00:27:32,340 And so here we're using this new dot syntax, 552 00:27:32,340 --> 00:27:35,430 president.name gets the value Alyssa. 553 00:27:35,430 --> 00:27:38,530 And president.votes gets the value 10. 554 00:27:38,530 --> 00:27:43,470 And so in this single variable called president that is of type candidate, 555 00:27:43,470 --> 00:27:47,190 we are storing now a name and a number of votes 556 00:27:47,190 --> 00:27:50,570 close to each other in memory here. 557 00:27:50,570 --> 00:27:55,055 What questions do you all have on this syntax or what structs are so far? 558 00:27:55,055 --> 00:27:58,490 559 00:27:58,490 --> 00:28:01,370 So your question about the maximum arguments for a struct, 560 00:28:01,370 --> 00:28:05,120 and maybe to go back here and show just some vocabulary. 561 00:28:05,120 --> 00:28:08,270 Here we often call this the attributes of a struct 562 00:28:08,270 --> 00:28:10,400 or the fields of the struct. 563 00:28:10,400 --> 00:28:14,630 And so here, there's really no limit to the number of fields we could define. 564 00:28:14,630 --> 00:28:18,680 But often want to keep things reasonable and compact for ourselves design-wise. 565 00:28:18,680 --> 00:28:21,797 It's a good question of design to figure out how many elements do we need 566 00:28:21,797 --> 00:28:23,630 or how many fields do we need in our struct. 567 00:28:23,630 --> 00:28:26,280 And so in this case, we might have 2, 3. 568 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. 569 00:28:30,530 --> 00:28:35,363 But often, if you're doing that, your struct might be a little too complex. 570 00:28:35,363 --> 00:28:36,905 I'm seeing some other questions here. 571 00:28:36,905 --> 00:28:39,958 572 00:28:39,958 --> 00:28:44,350 Is the C code we need to use in our code just key value pairs, 573 00:28:44,350 --> 00:28:46,420 like a dict in Python? 574 00:28:46,420 --> 00:28:49,270 This is maybe similar to a dictionary, if you're 575 00:28:49,270 --> 00:28:51,940 familiar with that, in Python in the sense 576 00:28:51,940 --> 00:28:55,720 that, when we say the president's name is Alyssa 577 00:28:55,720 --> 00:28:58,690 and the president's votes is 10, we can later on just 578 00:28:58,690 --> 00:29:03,400 get that same value by referencing president.name and president.vote, so 579 00:29:03,400 --> 00:29:07,210 similar in spirit to a dictionary where we're trying to have a key, like name, 580 00:29:07,210 --> 00:29:09,690 correspond to a value, like Alyssa. 581 00:29:09,690 --> 00:29:12,160 582 00:29:12,160 --> 00:29:13,160 Question about the dots. 583 00:29:13,160 --> 00:29:17,332 Why do we have these dots, president dot name, president dot votes? 584 00:29:17,332 --> 00:29:19,040 Simply speaking, long ago, it was decided 585 00:29:19,040 --> 00:29:21,410 that we would have this dot syntax to reference 586 00:29:21,410 --> 00:29:25,190 the fields or the attributes of a struct, so president dot name, 587 00:29:25,190 --> 00:29:26,590 president dot votes. 588 00:29:26,590 --> 00:29:28,340 And as you get used to it, you'll probably 589 00:29:28,340 --> 00:29:30,257 see it's pretty handy just to type that little 590 00:29:30,257 --> 00:29:34,580 dot there to get access to that individual attribute of that struct 591 00:29:34,580 --> 00:29:37,033 there. 592 00:29:37,033 --> 00:29:38,950 A question, can we use struct without typedef? 593 00:29:38,950 --> 00:29:39,700 Indeed, you could. 594 00:29:39,700 --> 00:29:42,820 So if you go back to this syntax here, we 595 00:29:42,820 --> 00:29:47,620 saw that typedef was the very first syntax piece we typed here. 596 00:29:47,620 --> 00:29:51,310 But if you didn't want to maybe reuse this struct, 597 00:29:51,310 --> 00:29:55,000 you want to just use a struct once, no need to use typedef. 598 00:29:55,000 --> 00:29:59,410 Typedef lets you specify a candidate, in this case, 599 00:29:59,410 --> 00:30:02,530 define a name for this new structure that you're building, 600 00:30:02,530 --> 00:30:04,130 and then reuse that name. 601 00:30:04,130 --> 00:30:06,920 So let's say I wanted to do this at the top of my program. 602 00:30:06,920 --> 00:30:07,810 I could do that. 603 00:30:07,810 --> 00:30:10,150 Later on, I would then be able to reuse the name 604 00:30:10,150 --> 00:30:13,012 candidate to refer to this structure. 605 00:30:13,012 --> 00:30:14,470 But maybe I don't want to reuse it. 606 00:30:14,470 --> 00:30:16,000 Maybe I only want to use it once. 607 00:30:16,000 --> 00:30:19,900 In that case, you could just have the struct there and not the typedef 608 00:30:19,900 --> 00:30:24,760 and you could use it just once in your program there. 609 00:30:24,760 --> 00:30:30,830 All right, I'm seeing a question, are structs similar to objects? 610 00:30:30,830 --> 00:30:33,830 There are some distinctions between structs and objects. 611 00:30:33,830 --> 00:30:35,690 You're familiar with this idea of an object 612 00:30:35,690 --> 00:30:38,900 and maybe you've done Python programming or Java programming 613 00:30:38,900 --> 00:30:41,360 and you've seen this idea of an object. 614 00:30:41,360 --> 00:30:46,280 Structs are a bit like objects, but you cannot tie a function to a struct. 615 00:30:46,280 --> 00:30:51,830 So objects in Python and Java might have methods or functions tied to them. 616 00:30:51,830 --> 00:30:54,260 Structs, though, do not have that distinction. 617 00:30:54,260 --> 00:30:58,290 They don't have functions tied to them. 618 00:30:58,290 --> 00:31:02,740 All right, so let's keep going on with these structs here 619 00:31:02,740 --> 00:31:05,830 and figure out what else we can do with them. 620 00:31:05,830 --> 00:31:08,890 Let's actually do a little exercise here, work on this 621 00:31:08,890 --> 00:31:13,057 together, where we'll create our own get candidate function. 622 00:31:13,057 --> 00:31:14,890 So you maybe are familiar with this function 623 00:31:14,890 --> 00:31:17,950 get string or get float in the CSFD library 624 00:31:17,950 --> 00:31:21,808 where you can use those functions to get a string, get a float, 625 00:31:21,808 --> 00:31:24,100 get an integer, whatever you want to get from the user. 626 00:31:24,100 --> 00:31:26,860 And similarly, we'll actually write our own function 627 00:31:26,860 --> 00:31:31,870 called get candidate that will return to us a new candidate that the user has 628 00:31:31,870 --> 00:31:36,290 created for us by being prompted for some information about that candidate. 629 00:31:36,290 --> 00:31:38,507 So let's go on over to our code spaces. 630 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. 631 00:31:41,590 --> 00:31:44,140 And once you get there, let's go ahead and open up 632 00:31:44,140 --> 00:31:47,650 this file called candidate.c. 633 00:31:47,650 --> 00:31:51,730 So once you get there, feel free to type maybe code candidate.c, 634 00:31:51,730 --> 00:31:56,870 or make a new file and title that one candidate.c. 635 00:31:56,870 --> 00:32:00,820 And once you do that, what are you going to include 636 00:32:00,820 --> 00:32:03,735 at the very top of your file? 637 00:32:03,735 --> 00:32:05,610 Can anyone tell me in the chat what you often 638 00:32:05,610 --> 00:32:12,660 want to include at the very top of your program 639 00:32:12,660 --> 00:32:13,970 So I'm seeing some-- 640 00:32:13,970 --> 00:32:18,530 yeah, some libraries, right, like standard io, cs50.h. 641 00:32:18,530 --> 00:32:22,810 Certainly, you want to use these libraries inside of our own program 642 00:32:22,810 --> 00:32:23,310 here. 643 00:32:23,310 --> 00:32:27,542 So all right, now I have my terminal up and running. 644 00:32:27,542 --> 00:32:29,750 So if you're following along with me, what you can do 645 00:32:29,750 --> 00:32:31,730 is simply type maybe code-- 646 00:32:31,730 --> 00:32:35,880 oops, let me go clear that. 647 00:32:35,880 --> 00:32:38,700 you do get rid of the activity bar there. 648 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, 649 00:32:43,920 --> 00:32:45,810 again, called candidate.c up here. 650 00:32:45,810 --> 00:32:47,110 And that dot c is important. 651 00:32:47,110 --> 00:32:50,268 That means there's a c file here. 652 00:32:50,268 --> 00:32:52,060 So what we'll do, as people have suggested, 653 00:32:52,060 --> 00:32:54,530 we'll include some libraries up here. 654 00:32:54,530 --> 00:32:59,110 We'll say, include maybe the cs50 library to get access to functions, 655 00:32:59,110 --> 00:33:02,080 like get int and get string, and so on. 656 00:33:02,080 --> 00:33:05,530 Maybe we'll also include standard io.h to be able to print things 657 00:33:05,530 --> 00:33:07,700 to the screen, use printdef. 658 00:33:07,700 --> 00:33:11,570 All right, now often what we'll do is we'll 659 00:33:11,570 --> 00:33:15,350 declare our struct at the very top of our file 660 00:33:15,350 --> 00:33:20,310 below our includes or our libraries here. 661 00:33:20,310 --> 00:33:22,570 So what syntax would we need here? 662 00:33:22,570 --> 00:33:24,320 We might want to create a new type, right? 663 00:33:24,320 --> 00:33:27,860 So we'll type typedef, and we want to make a struct. 664 00:33:27,860 --> 00:33:30,080 So we'll say this is a new struct. 665 00:33:30,080 --> 00:33:33,662 And what are we going to put inside of this struct? 666 00:33:33,662 --> 00:33:35,120 What attribute did we have earlier? 667 00:33:35,120 --> 00:33:37,602 If you want to type in the chat. 668 00:33:37,602 --> 00:33:39,185 We're trying to make a candidate here. 669 00:33:39,185 --> 00:33:42,362 670 00:33:42,362 --> 00:33:43,570 All right, so name and votes. 671 00:33:43,570 --> 00:33:46,480 So maybe name is a string. 672 00:33:46,480 --> 00:33:49,980 So let's say this attribute is called name. 673 00:33:49,980 --> 00:33:51,660 It's of type string. 674 00:33:51,660 --> 00:33:55,290 And then we'll also say, let's give a new attribute called votes, 675 00:33:55,290 --> 00:33:57,640 and that will be of type int. 676 00:33:57,640 --> 00:34:01,530 And now finally, we'll need to close this out with a name for our struct. 677 00:34:01,530 --> 00:34:06,050 So we'll call it candidate down here. 678 00:34:06,050 --> 00:34:10,116 All right, so now we can re-use this idea of a candidate 679 00:34:10,116 --> 00:34:12,199 throughout our program because we've used typedef. 680 00:34:12,199 --> 00:34:15,590 We can say, I want to create a new candidate using 681 00:34:15,590 --> 00:34:19,940 this new amalgamation of types that we're going to call candidate 682 00:34:19,940 --> 00:34:22,040 throughout our program here. 683 00:34:22,040 --> 00:34:26,780 All right, and now what is the main part of our program now? 684 00:34:26,780 --> 00:34:28,880 We have our libraries. 685 00:34:28,880 --> 00:34:30,770 We have our struct. 686 00:34:30,770 --> 00:34:33,929 What kind of function do we need now? 687 00:34:33,929 --> 00:34:36,690 Maybe in the chat, feel free to type. 688 00:34:36,690 --> 00:34:38,369 Yeah, we need our int main void. 689 00:34:38,369 --> 00:34:42,250 So we need the main function for our program. 690 00:34:42,250 --> 00:34:46,050 So we'll do int main void and have some space there for us 691 00:34:46,050 --> 00:34:49,760 to write our program. 692 00:34:49,760 --> 00:34:52,340 But here, if we go back to our slides, our goal 693 00:34:52,340 --> 00:34:55,610 is to make our own function called get candidate. 694 00:34:55,610 --> 00:35:00,170 So what we want to do is probably define that down below. 695 00:35:00,170 --> 00:35:03,020 And what you'll notice about defining new functions 696 00:35:03,020 --> 00:35:07,160 or declaring new functions is that their signature here, 697 00:35:07,160 --> 00:35:11,160 or we call this line here, has a few key elements to it. 698 00:35:11,160 --> 00:35:14,270 So it has the type that this function gives back 699 00:35:14,270 --> 00:35:16,070 to us, that it returns to us. 700 00:35:16,070 --> 00:35:20,700 It has the function's name, and it has the function's inputs. 701 00:35:20,700 --> 00:35:24,500 So if we're trying to write a function called get candidate, 702 00:35:24,500 --> 00:35:26,570 what name would we type in? 703 00:35:26,570 --> 00:35:30,560 Maybe an obvious answer here, if we type in the chat. 704 00:35:30,560 --> 00:35:33,755 What name would we type in for get candidate? 705 00:35:33,755 --> 00:35:35,630 We probably should type get candidate, right? 706 00:35:35,630 --> 00:35:38,570 Get candidate is the name of our function. 707 00:35:38,570 --> 00:35:40,445 And now, what type does it return to us? 708 00:35:40,445 --> 00:35:43,570 709 00:35:43,570 --> 00:35:44,650 I'm seeing a few-- 710 00:35:44,650 --> 00:35:47,350 I'm seeing string, and I'm seeing candidate. 711 00:35:47,350 --> 00:35:50,590 So notice now, we're not going to return a string. 712 00:35:50,590 --> 00:35:54,700 We're actually going to return an entire candidate because we've 713 00:35:54,700 --> 00:35:58,810 defined a candidate as this combination of a string that is called name 714 00:35:58,810 --> 00:36:00,310 and an integer that is called votes. 715 00:36:00,310 --> 00:36:05,170 So here, we're going to give back to our program a whole candidate, 716 00:36:05,170 --> 00:36:08,500 not just a string, not just an int, but a whole candidate, those two types 717 00:36:08,500 --> 00:36:09,490 put together. 718 00:36:09,490 --> 00:36:12,020 And because we use typedef, we can say this down below. 719 00:36:12,020 --> 00:36:16,090 We can say get candidate. 720 00:36:16,090 --> 00:36:22,060 And now, we can go ahead and define this function called get candidate, 721 00:36:22,060 --> 00:36:23,590 but we need one more step now. 722 00:36:23,590 --> 00:36:28,100 We need to give some inputs or some arguments here. 723 00:36:28,100 --> 00:36:31,568 And if we're using our modeling off of get string, for example, 724 00:36:31,568 --> 00:36:32,860 we might want to take a prompt. 725 00:36:32,860 --> 00:36:37,480 We could say, maybe it takes a prompt that is a string here. 726 00:36:37,480 --> 00:36:40,015 727 00:36:40,015 --> 00:36:42,265 All right, so what questions are there on this so far? 728 00:36:42,265 --> 00:36:46,340 729 00:36:46,340 --> 00:36:49,520 All right, seeing none so far. 730 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. 731 00:36:53,160 --> 00:36:55,670 So ideally, we want to be able to use it like this. 732 00:36:55,670 --> 00:37:00,350 We could say, within my main function, I want to create a new candidate. 733 00:37:00,350 --> 00:37:03,470 Maybe I'll call this one president. 734 00:37:03,470 --> 00:37:07,340 But to actually fill in that variable, to give it a value, 735 00:37:07,340 --> 00:37:13,700 I'll call get candidate, similar to what I did for get string, for example. 736 00:37:13,700 --> 00:37:17,645 Here, I could say maybe Enter a candidate is the prompt. 737 00:37:17,645 --> 00:37:22,830 738 00:37:22,830 --> 00:37:24,140 And now I'm seeing a question. 739 00:37:24,140 --> 00:37:27,810 Is candidate a type because we've declared it above the main function? 740 00:37:27,810 --> 00:37:28,310 Indeed. 741 00:37:28,310 --> 00:37:32,810 So we've used typedef here, which is that key word that says, all of what 742 00:37:32,810 --> 00:37:36,540 follows should be considered reusable in our program. 743 00:37:36,540 --> 00:37:39,680 So here we're saying that this struct that we're going to call candidate 744 00:37:39,680 --> 00:37:44,000 is a bit similar to a type that we can use throughout our program. 745 00:37:44,000 --> 00:37:46,550 We can say that a function does indeed return 746 00:37:46,550 --> 00:37:49,580 an entire candidate and not just those basic data 747 00:37:49,580 --> 00:37:53,540 types, like a string or an int. 748 00:37:53,540 --> 00:37:57,170 All right, and so we're going to be able to use get candidate like this. 749 00:37:57,170 --> 00:38:00,110 We'll create a variable called president that is a candidate 750 00:38:00,110 --> 00:38:02,450 and then have get candidate returned to us 751 00:38:02,450 --> 00:38:07,620 that new candidate that we've created with get candidate down below. 752 00:38:07,620 --> 00:38:11,920 OK, so we now have this function get candidate, 753 00:38:11,920 --> 00:38:16,060 but we need first to be able to print out the prompt to the user 754 00:38:16,060 --> 00:38:17,570 so they know what to type in. 755 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. 756 00:38:23,960 --> 00:38:27,410 So I'll say, whatever the user gives to me as the prompt, 757 00:38:27,410 --> 00:38:31,210 let's say this string here, I'll then print it back 758 00:38:31,210 --> 00:38:36,200 out to the user when I run Get candidate, and I'll make a new line. 759 00:38:36,200 --> 00:38:39,340 Now though, I need to do the work of creating this new candidate 760 00:38:39,340 --> 00:38:41,890 and filling in its attributes and ultimately returning 761 00:38:41,890 --> 00:38:44,690 that candidate to my main function. 762 00:38:44,690 --> 00:38:49,720 So what we could do is we could say, I want to create a new candidate. 763 00:38:49,720 --> 00:38:51,400 And it's like a throwaway candidate. 764 00:38:51,400 --> 00:38:54,160 I'm just going to create it here, add some attributes 765 00:38:54,160 --> 00:38:56,300 and return it back to our main function. 766 00:38:56,300 --> 00:38:57,988 So I'll just call it candidate c. 767 00:38:57,988 --> 00:39:00,280 Maybe we can come up with a better name, but we'll just 768 00:39:00,280 --> 00:39:02,820 call it candidate c for now. 769 00:39:02,820 --> 00:39:06,870 This is a new candidate variable I've created in my get candidate function. 770 00:39:06,870 --> 00:39:08,715 And now what I could do is this. 771 00:39:08,715 --> 00:39:12,850 I could say c.name should be what? 772 00:39:12,850 --> 00:39:17,620 What kind of function could I use to fill in the value for name? 773 00:39:17,620 --> 00:39:19,700 Remember, it's a string. 774 00:39:19,700 --> 00:39:21,310 Ah, I could use get string, right? 775 00:39:21,310 --> 00:39:27,640 I could say get string and, let's say, Enter a name, right? 776 00:39:27,640 --> 00:39:30,100 So now the candidate's name will be filled 777 00:39:30,100 --> 00:39:34,690 in by the user when they enter in some text after get string. 778 00:39:34,690 --> 00:39:36,610 And now here we'll see c.votes. 779 00:39:36,610 --> 00:39:40,140 And how could I fill in the votes? 780 00:39:40,140 --> 00:39:43,960 What kind of function would I use here, maybe in the chat? 781 00:39:43,960 --> 00:39:44,740 Get int, right? 782 00:39:44,740 --> 00:39:49,680 So I could do get int and then enter a number of votes. 783 00:39:49,680 --> 00:39:50,970 Awesome. 784 00:39:50,970 --> 00:39:54,417 And now finally, I've created this new candidate called c. 785 00:39:54,417 --> 00:39:56,250 I've added in the name, the number of votes. 786 00:39:56,250 --> 00:39:59,720 What's left to do? 787 00:39:59,720 --> 00:40:01,710 I need to give it back to my main function. 788 00:40:01,710 --> 00:40:03,020 So what would let me do that? 789 00:40:03,020 --> 00:40:05,710 Return, so I'll return c. 790 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, 791 00:40:09,130 --> 00:40:12,070 this new variable called president that is a candidate 792 00:40:12,070 --> 00:40:14,590 will first call get candidate. 793 00:40:14,590 --> 00:40:16,467 We'll go ahead and prompt the user. 794 00:40:16,467 --> 00:40:19,300 Then we'll create this new candidate, fill in the name of the votes, 795 00:40:19,300 --> 00:40:21,910 return that candidate, and ultimately, store it 796 00:40:21,910 --> 00:40:23,950 in this variable called President. 797 00:40:23,950 --> 00:40:27,070 So what I should be able to do is maybe type in, for example, 798 00:40:27,070 --> 00:40:29,900 print maybe the name. 799 00:40:29,900 --> 00:40:32,480 So I'll say president.name. 800 00:40:32,480 --> 00:40:36,800 And then what I'll do is I'll print, let's say, the votes. 801 00:40:36,800 --> 00:40:39,470 I'll say president.votes. 802 00:40:39,470 --> 00:40:42,630 And when I run this, I should be able to see that result there. 803 00:40:42,630 --> 00:40:45,410 So let's go ahead and go down to our terminal. 804 00:40:45,410 --> 00:40:48,780 I'll type make candidate. 805 00:40:48,780 --> 00:40:50,870 Oh, and I got an error. 806 00:40:50,870 --> 00:40:54,492 What did we forget to do? 807 00:40:54,492 --> 00:40:56,075 If you take a look at this error here. 808 00:40:56,075 --> 00:40:59,460 809 00:40:59,460 --> 00:41:00,840 Seeing a few answers. 810 00:41:00,840 --> 00:41:03,390 What did we forget to do here? 811 00:41:03,390 --> 00:41:07,530 Implicit declaration of function get candidate is invalid in C99. 812 00:41:07,530 --> 00:41:10,900 813 00:41:10,900 --> 00:41:13,880 Yeah, so I'm seeing I'm missing the prototype for this function. 814 00:41:13,880 --> 00:41:16,120 So notice how we got ahead of ourselves here. 815 00:41:16,120 --> 00:41:18,910 We went and defined our function down below, 816 00:41:18,910 --> 00:41:21,950 but we actually use it before it is defined. 817 00:41:21,950 --> 00:41:25,030 So what we should do is really go to line 10, 818 00:41:25,030 --> 00:41:28,107 after our definition of this candidate here. 819 00:41:28,107 --> 00:41:29,690 And we should say something like this. 820 00:41:29,690 --> 00:41:33,640 We should say, let's copy and paste the prototype for this function, 821 00:41:33,640 --> 00:41:38,260 the prototype being what it returns, its name, and any arguments it has, 822 00:41:38,260 --> 00:41:41,780 and put a semicolon to say that, look, this function will come up. 823 00:41:41,780 --> 00:41:44,830 I promise to you, I will define it later as this 824 00:41:44,830 --> 00:41:48,908 a compiler reads our code from top to bottom in this case. 825 00:41:48,908 --> 00:41:50,200 All right, so let's go back in. 826 00:41:50,200 --> 00:41:53,440 Let's go ahead and clear our terminal window. 827 00:41:53,440 --> 00:41:55,570 Type make candidate. 828 00:41:55,570 --> 00:41:57,110 Oop, and we still have an error. 829 00:41:57,110 --> 00:41:59,644 Let's see this one. 830 00:41:59,644 --> 00:42:00,850 Hmm. 831 00:42:00,850 --> 00:42:04,150 President.votes, this error is a little cryptic. 832 00:42:04,150 --> 00:42:08,233 But if the format code for a string, you'll 833 00:42:08,233 --> 00:42:10,150 know that this is maybe the wrong format code. 834 00:42:10,150 --> 00:42:12,400 I'm seeing we need %i right there. 835 00:42:12,400 --> 00:42:14,350 Good, so I'll click my terminal again. 836 00:42:14,350 --> 00:42:15,940 I'll type make candidate. 837 00:42:15,940 --> 00:42:17,630 And now, it seems to work. 838 00:42:17,630 --> 00:42:21,160 So what I can do is I can do dot/candidate. 839 00:42:21,160 --> 00:42:24,850 I now see the prompt Enter a candidate that I typed up above here. 840 00:42:24,850 --> 00:42:29,440 I can say maybe the candidate's name is Carter, and maybe the number of votes 841 00:42:29,440 --> 00:42:30,400 is 10. 842 00:42:30,400 --> 00:42:33,370 And I'll hit Enter, and now I see those same elements 843 00:42:33,370 --> 00:42:38,400 here in my program or my terminal. 844 00:42:38,400 --> 00:42:42,300 OK, so what questions are there on this program so far? 845 00:42:42,300 --> 00:42:49,990 846 00:42:49,990 --> 00:42:54,750 All right, so seeing none right now. 847 00:42:54,750 --> 00:42:57,410 But what we might want to do at the very end 848 00:42:57,410 --> 00:43:00,580 is, maybe we don't just want one candidate. 849 00:43:00,580 --> 00:43:03,470 We want, actually, an array of candidates or a list of candidates. 850 00:43:03,470 --> 00:43:07,040 And you'll see this in the problem set for this week of CS50. 851 00:43:07,040 --> 00:43:12,230 What we can do is we can actually use this same type we've defined 852 00:43:12,230 --> 00:43:14,760 to create an array of that type. 853 00:43:14,760 --> 00:43:19,310 So we could say, I want an array of candidates 854 00:43:19,310 --> 00:43:21,380 that I'll call the candidates array. 855 00:43:21,380 --> 00:43:23,340 And I want to have three of them in there. 856 00:43:23,340 --> 00:43:25,490 So notice how, if I zoom in again, you'll 857 00:43:25,490 --> 00:43:28,910 see we're going to define an array called candidates array 858 00:43:28,910 --> 00:43:32,210 that is full of these candidate types that we've declared up above. 859 00:43:32,210 --> 00:43:35,567 And it has space for three of them, right? 860 00:43:35,567 --> 00:43:37,400 So what we could do in this case is actually 861 00:43:37,400 --> 00:43:39,530 go ahead and fill in the array. 862 00:43:39,530 --> 00:43:43,200 We could say, let's start at index 0. 863 00:43:43,200 --> 00:43:46,660 Let's go on up to but not including that third index. 864 00:43:46,660 --> 00:43:51,750 So we'll go 0, 1, and 2, and increase i by 1 as we go. 865 00:43:51,750 --> 00:43:56,210 And as we do that, we'll say, OK, maybe the candidates array at location i, 866 00:43:56,210 --> 00:44:02,130 first 0, then 1, then 2 is going to use Get candidate. 867 00:44:02,130 --> 00:44:07,420 So I'll say get candidate, and let's say, Enter a candidate. 868 00:44:07,420 --> 00:44:10,123 And now what I can do is, if I were to run this program, 869 00:44:10,123 --> 00:44:12,040 I would get prompted again and again and again 870 00:44:12,040 --> 00:44:17,520 to enter a candidate until my array is full. 871 00:44:17,520 --> 00:44:20,510 Now, if we were to do that and also to access 872 00:44:20,510 --> 00:44:22,730 some of these candidates inside that array, 873 00:44:22,730 --> 00:44:26,340 we need some combination of the syntax we've seen before. 874 00:44:26,340 --> 00:44:29,570 So what we might do is, in the problems that you'll 875 00:44:29,570 --> 00:44:34,340 see maybe an array of candidates like this, like name and number of vote. 876 00:44:34,340 --> 00:44:39,470 And to access the candidate as a whole, like Alice as well as Alice's votes, 877 00:44:39,470 --> 00:44:43,310 you would just type candidates bracket 0 to get that very first element 878 00:44:43,310 --> 00:44:45,380 in this array here. 879 00:44:45,380 --> 00:44:48,520 But if I wanted to get maybe just the candidate's name, 880 00:44:48,520 --> 00:44:49,730 I could do as follows. 881 00:44:49,730 --> 00:44:52,690 I could say candidates brackets 0 dot name, 882 00:44:52,690 --> 00:44:55,840 or, similarly, candidates brackets 0 dot votes. 883 00:44:55,840 --> 00:44:58,420 And that would allow me to get, not just the whole candidate 884 00:44:58,420 --> 00:45:04,210 at that array location, but the actual attribute I'm interested in here 885 00:45:04,210 --> 00:45:06,660 as well. 886 00:45:06,660 --> 00:45:08,985 All right, other questions on this. 887 00:45:08,985 --> 00:45:19,260 888 00:45:19,260 --> 00:45:24,170 All right, so seeing none so far, that will 889 00:45:24,170 --> 00:45:27,950 conclude our little brief foray into structs her. 890 00:45:27,950 --> 00:45:30,650 And certainly, we can take a minute to go back 891 00:45:30,650 --> 00:45:32,760 if there are questions towards the end. 892 00:45:32,760 --> 00:45:36,800 But for now, with our last bit of time, what we want to do 893 00:45:36,800 --> 00:45:39,660 is figure out how we can use recursion. 894 00:45:39,660 --> 00:45:44,030 So recursion is not necessarily an algorithm. 895 00:45:44,030 --> 00:45:48,560 It's more so an approach to problem solving in computer science. 896 00:45:48,560 --> 00:45:51,350 There is no single recursive algorithm, but there 897 00:45:51,350 --> 00:45:53,250 are algorithms that use recursion. 898 00:45:53,250 --> 00:45:55,730 So recursion is simply a way of solving problems. 899 00:45:55,730 --> 00:46:01,430 And recursion, more specifically, is about taking a large problem, one 900 00:46:01,430 --> 00:46:04,910 that seems a little daunting, and breaking it up into smaller pieces 901 00:46:04,910 --> 00:46:07,230 that we know we can solve. 902 00:46:07,230 --> 00:46:11,150 And so one example of this is often used when teaching recursion 903 00:46:11,150 --> 00:46:12,690 is this idea of a factorial. 904 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 905 00:46:17,390 --> 00:46:19,460 is 1, right? 906 00:46:19,460 --> 00:46:23,600 We can say 2 factorial is 2 times 1. 907 00:46:23,600 --> 00:46:27,650 And we can say 3 factorial is, well, 3 times 2 times 1. 908 00:46:27,650 --> 00:46:31,430 And if you're not getting the pattern, 4 factorial might be? 909 00:46:31,430 --> 00:46:34,070 Well, just 4 times 3 times 2 times 1. 910 00:46:34,070 --> 00:46:39,380 So a factorial is multiplying a number by 1 less than that number 911 00:46:39,380 --> 00:46:43,385 and moving down until we get to 1, right, so 4 times 3 times 2 times 912 00:46:43,385 --> 00:46:47,910 1 for 4 factorial, 3 factorial, 3 times 2 times 1, and so on. 913 00:46:47,910 --> 00:46:54,200 Now, what do you notice about this problem, particularly in 4 factorial? 914 00:46:54,200 --> 00:46:57,590 What do you notice, or what do you see if we're 915 00:46:57,590 --> 00:47:00,890 trying to use recursion on this problem, trying to find a smaller 916 00:47:00,890 --> 00:47:05,520 problem within 4 factorial? 917 00:47:05,520 --> 00:47:08,350 Maybe type in the chat if you'd like. 918 00:47:08,350 --> 00:47:15,962 What kind of pattern do you see when you look at 2 factorial, 3 factorial? 919 00:47:15,962 --> 00:47:17,170 So seeing a few ideas, right? 920 00:47:17,170 --> 00:47:20,170 I'm seeing it's repeating the same steps. 921 00:47:20,170 --> 00:47:22,330 It's a little repetitive. 922 00:47:22,330 --> 00:47:25,900 And I'm seeing, more particularly, if we look at 4 factorial, 923 00:47:25,900 --> 00:47:30,490 we actually see that 3 factorial is included in 4 factorial, right? 924 00:47:30,490 --> 00:47:32,680 3 factorial is 3 times 2 times 1. 925 00:47:32,680 --> 00:47:36,010 Well, that's actually right there in 4 factorial, 3 times 2 times 1. 926 00:47:36,010 --> 00:47:39,400 So if we were to look at the problem this way, 927 00:47:39,400 --> 00:47:41,320 we might make it a little more obvious, right? 928 00:47:41,320 --> 00:47:45,890 4 factorial really has the solution 3 factorial inside of it. 929 00:47:45,890 --> 00:47:49,127 And similarly, 3 factorial has 2 factorial inside of it. 930 00:47:49,127 --> 00:47:51,710 And then finally, 1 factorial, that's just kind of on its own. 931 00:47:51,710 --> 00:47:52,570 It's just 1, right? 932 00:47:52,570 --> 00:47:54,910 We know that for a fact. 933 00:47:54,910 --> 00:47:57,690 This is really a good place for recursion 934 00:47:57,690 --> 00:48:01,110 to come in because recursion is all about taking this larger problem, 935 00:48:01,110 --> 00:48:05,470 like 4 factorial, and breaking it down into smaller pieces. 936 00:48:05,470 --> 00:48:08,340 So let's look at it from a recursive standpoint. 937 00:48:08,340 --> 00:48:11,950 Let's go ahead and say we want to find 4 factorial. 938 00:48:11,950 --> 00:48:14,650 Well, what is 4 factorial? 939 00:48:14,650 --> 00:48:17,160 Well, it's 4 times what? 940 00:48:17,160 --> 00:48:19,920 What's the smaller problem within 4 factorial? 941 00:48:19,920 --> 00:48:22,020 4 times 3 factorial, I'm seeing in the chat. 942 00:48:22,020 --> 00:48:25,740 So 4 factorial is just 4 times 3 factorial. 943 00:48:25,740 --> 00:48:28,510 But what then is 3 factorial? 944 00:48:28,510 --> 00:48:32,010 So this is where what comes in as we call it a recursive call. 945 00:48:32,010 --> 00:48:36,120 This is saying we are going to solve this smaller problem before we 946 00:48:36,120 --> 00:48:38,490 can solve this larger problem, right? 947 00:48:38,490 --> 00:48:43,420 We can't solve 4 factorial until we know what 3 factorial is. 948 00:48:43,420 --> 00:48:45,610 So let's go ahead and solve 3 factorial. 949 00:48:45,610 --> 00:48:46,950 Well, what is 3 factorial? 950 00:48:46,950 --> 00:48:52,120 That is just 3 times what? 951 00:48:52,120 --> 00:48:54,550 3 times 2 factorial, right? 952 00:48:54,550 --> 00:48:58,190 So that's fine, but what is 2 factorial? 953 00:48:58,190 --> 00:49:00,520 Well, 2 factorial is? 954 00:49:00,520 --> 00:49:02,750 2 times 1 factorial. 955 00:49:02,750 --> 00:49:04,270 And what is 1 factorial? 956 00:49:04,270 --> 00:49:06,110 At some point, we do have to stop here. 957 00:49:06,110 --> 00:49:09,250 Otherwise, we'll keep finding smaller and smaller problems and never end. 958 00:49:09,250 --> 00:49:12,100 Well, 1 factorial, in this case, is just 1. 959 00:49:12,100 --> 00:49:14,350 We know that for a fact. 960 00:49:14,350 --> 00:49:18,550 And so this down at the bottom is what's called our base case. 961 00:49:18,550 --> 00:49:23,360 This is the problem that we know how to solve just for a fact. 962 00:49:23,360 --> 00:49:26,560 1 factorial is 1, no computation necessary, 963 00:49:26,560 --> 00:49:29,850 no need to break it down into a smaller problem. 964 00:49:29,850 --> 00:49:33,210 And now, once we've gone down to that base case, 965 00:49:33,210 --> 00:49:35,040 well, the rest follows, right? 966 00:49:35,040 --> 00:49:36,960 We know that 1 factorial is 1. 967 00:49:36,960 --> 00:49:40,390 So let's go ahead and make sure that we can solve 2 factorial. 968 00:49:40,390 --> 00:49:42,880 And we're going, what we call, back up the call stack, 969 00:49:42,880 --> 00:49:46,020 where we made a recursive call earlier to go ahead and solve a smaller 970 00:49:46,020 --> 00:49:46,980 problem. 971 00:49:46,980 --> 00:49:49,920 Now we've found our base case, so we'll go back up 972 00:49:49,920 --> 00:49:53,970 this stack of calls we made to find the answer here. 973 00:49:53,970 --> 00:49:57,150 What we'll do is say, OK, 2 factorial, that's actually just 2 times 1. 974 00:49:57,150 --> 00:49:59,370 We know that now because 1 factorial is 1. 975 00:49:59,370 --> 00:50:02,550 Well, 3 factorial, that's actually just 3 times 2 times 976 00:50:02,550 --> 00:50:05,430 1 because we know now that 2 factorial is 2 times 1. 977 00:50:05,430 --> 00:50:08,730 And similarly, for 4 factorial, we know that, in this case, 978 00:50:08,730 --> 00:50:11,400 3 factorial is just 3 times 2 times 1. 979 00:50:11,400 --> 00:50:15,720 So now we can say 4 factorial is just this expression, 4 times 3 times 980 00:50:15,720 --> 00:50:16,290 2 times 1. 981 00:50:16,290 --> 00:50:20,070 And that, as a whole, is 24. 982 00:50:20,070 --> 00:50:22,930 All right, and so I'm seeing in the chat, it's like backwards logic. 983 00:50:22,930 --> 00:50:24,222 It is a little backwards logic. 984 00:50:24,222 --> 00:50:28,082 We have to go down to the bottom first and then work our way back up. 985 00:50:28,082 --> 00:50:29,540 So let's work on this one together. 986 00:50:29,540 --> 00:50:32,490 Let's actually see what might be able to work on with here. 987 00:50:32,490 --> 00:50:35,840 And what we'll do is write our own function called factorial, 988 00:50:35,840 --> 00:50:40,400 where factorial should take an integer and return the factorial of whatever 989 00:50:40,400 --> 00:50:42,570 number we pass in as a parameter. 990 00:50:42,570 --> 00:50:45,410 So if we pass in 4, we should find 4 factorial, or 5, 991 00:50:45,410 --> 00:50:47,720 we should find 5 factorial here. 992 00:50:47,720 --> 00:50:52,098 All right, so let's go ahead and actually open up our own program. 993 00:50:52,098 --> 00:50:53,890 We'll go ahead and go back to our terminal. 994 00:50:53,890 --> 00:50:59,240 We'll type code factorial.c to open up this new file called factorial. 995 00:50:59,240 --> 00:51:01,810 And let's get the same template code in there. 996 00:51:01,810 --> 00:51:04,810 We need to make sure we have cs50 library. 997 00:51:04,810 --> 00:51:07,570 We need to have standard io.h. 998 00:51:07,570 --> 00:51:12,760 And we also need to have, of course, our int main void function, 999 00:51:12,760 --> 00:51:15,620 that main function in our program. 1000 00:51:15,620 --> 00:51:19,320 And now we can also make sure we have our factorial function. 1001 00:51:19,320 --> 00:51:21,830 So I'll zoom in just a little bit more. 1002 00:51:21,830 --> 00:51:23,600 We might want to have a factorial. 1003 00:51:23,600 --> 00:51:28,740 What type is factorial returning to us, do we know in this case? 1004 00:51:28,740 --> 00:51:30,440 If you want to type a chime in the chat. 1005 00:51:30,440 --> 00:51:31,190 An integer, right? 1006 00:51:31,190 --> 00:51:35,420 So we'll say int, and then the name of this function, factorial. 1007 00:51:35,420 --> 00:51:37,550 And then does it take any inputs? 1008 00:51:37,550 --> 00:51:39,110 What kind of input does it take? 1009 00:51:39,110 --> 00:51:41,840 1010 00:51:41,840 --> 00:51:44,130 Yeah, it takes a number that is also an integer. 1011 00:51:44,130 --> 00:51:48,060 So I could say int, maybe, number in this case. 1012 00:51:48,060 --> 00:51:50,210 So here we have this function, again, called 1013 00:51:50,210 --> 00:51:56,000 factorial that takes a argument called number that is an integer. 1014 00:51:56,000 --> 00:52:01,480 And it returns to us an integer, that number factorialized, right? 1015 00:52:01,480 --> 00:52:04,450 And now we know from our past mistake we need to actually go ahead 1016 00:52:04,450 --> 00:52:08,590 and include this prototype up at the very top of our file 1017 00:52:08,590 --> 00:52:11,790 in order to use this function in our code. 1018 00:52:11,790 --> 00:52:15,810 OK, and let's just go ahead and fill our main function here. 1019 00:52:15,810 --> 00:52:19,750 Let's make sure we maybe prompt the user for a number. 1020 00:52:19,750 --> 00:52:24,660 So we could say, let's give ourselves maybe int n is get int, 1021 00:52:24,660 --> 00:52:29,760 and we'll say type a number to our user. 1022 00:52:29,760 --> 00:52:33,690 And then what we'll do is maybe print the resulting 1023 00:52:33,690 --> 00:52:36,990 integer that comes from running factorial 1024 00:52:36,990 --> 00:52:40,600 in this case, so factorial of n. 1025 00:52:40,600 --> 00:52:43,760 Now, it's up to us to actually implement factorial down here. 1026 00:52:43,760 --> 00:52:47,050 And when we think about implementing recursive functions, 1027 00:52:47,050 --> 00:52:50,380 we often want to start first with our base case. 1028 00:52:50,380 --> 00:52:52,910 What is the thing we know to be a fact? 1029 00:52:52,910 --> 00:52:58,990 And if we look at our factorial call stack here, what was our thing 1030 00:52:58,990 --> 00:53:01,210 we know to be a factor down here? 1031 00:53:01,210 --> 00:53:02,500 Feel free to type in the chat. 1032 00:53:02,500 --> 00:53:05,500 1033 00:53:05,500 --> 00:53:06,130 Seeing 1. 1034 00:53:06,130 --> 00:53:07,960 So yeah, 1 factorial is 1. 1035 00:53:07,960 --> 00:53:08,920 We know that. 1036 00:53:08,920 --> 00:53:10,610 That is always true. 1037 00:53:10,610 --> 00:53:13,840 So what we should do is go back to our factorial function 1038 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 1039 00:53:22,510 --> 00:53:23,890 and just say the answer. 1040 00:53:23,890 --> 00:53:26,590 Let's say the answer is 1. 1041 00:53:26,590 --> 00:53:30,752 So now, if I were to type in 1 and pass it to factorial, 1042 00:53:30,752 --> 00:53:31,960 I would get the right answer. 1043 00:53:31,960 --> 00:53:34,720 1 factorial is 1. 1044 00:53:34,720 --> 00:53:37,060 But there's more to do here. 1045 00:53:37,060 --> 00:53:40,420 If I were to type in factorial of 3 or factorial of 4, 1046 00:53:40,420 --> 00:53:43,060 that wouldn't quite work because I haven't figured out 1047 00:53:43,060 --> 00:53:46,380 how to solve that piece yet. 1048 00:53:46,380 --> 00:53:50,280 Now, if we go back to our diagram here, what 1049 00:53:50,280 --> 00:53:55,020 did we notice about how each factorial problem is 1050 00:53:55,020 --> 00:53:58,360 composed of some other problem? 1051 00:53:58,360 --> 00:54:00,940 What should be our recursive step here? 1052 00:54:00,940 --> 00:54:04,270 1053 00:54:04,270 --> 00:54:06,760 Yes, I'm seeing something like n minus 1. 1054 00:54:06,760 --> 00:54:09,940 And if you notice, you'll look at maybe 4 factorial, and see, 1055 00:54:09,940 --> 00:54:14,200 well, 4 factorial is really just 4 times 3 factorial. 1056 00:54:14,200 --> 00:54:16,150 And 3 factorial is just 3 times 2 factorial. 1057 00:54:16,150 --> 00:54:19,330 So it's really whatever number we're at times 1058 00:54:19,330 --> 00:54:21,600 the factorial of a number minus 1. 1059 00:54:21,600 --> 00:54:26,130 Now, there is a way to use a loop here, and that 1060 00:54:26,130 --> 00:54:27,880 would be called what an iterative approach 1061 00:54:27,880 --> 00:54:29,338 using a loop to solve this problem. 1062 00:54:29,338 --> 00:54:32,560 But here we'll actually use a recursive solution, 1063 00:54:32,560 --> 00:54:36,440 which is one that calls itself in the definition. 1064 00:54:36,440 --> 00:54:39,940 So factorial will call the factorial function 1065 00:54:39,940 --> 00:54:42,050 to try to solve this problem here. 1066 00:54:42,050 --> 00:54:45,490 So if we know that we don't have the answer already, 1067 00:54:45,490 --> 00:54:49,365 if we know that we aren't at 1 factorial, what we can do instead 1068 00:54:49,365 --> 00:54:52,240 is try to solve this problem by breaking it down into smaller pieces. 1069 00:54:52,240 --> 00:54:55,210 We could say, well, we know that a certain number factorial is really 1070 00:54:55,210 --> 00:55:07,870 just that number times that number minus 1 factorialized like this. 1071 00:55:07,870 --> 00:55:11,170 If I go full screen here, we'll see that really the solution is just 1072 00:55:11,170 --> 00:55:17,680 number times the factorial of that number minus 1. 1073 00:55:17,680 --> 00:55:20,800 And let's go ahead and try to get a visual here, 1074 00:55:20,800 --> 00:55:22,480 but just first confirm it works. 1075 00:55:22,480 --> 00:55:28,290 So I'll say make factorial and run./factorial. 1076 00:55:28,290 --> 00:55:32,230 And maybe I'll type in 4, and I get 24. 1077 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. 1078 00:55:38,280 --> 00:55:42,210 But why is this working? 1079 00:55:42,210 --> 00:55:45,570 It seems a little odd that we can just solve this problem 1080 00:55:45,570 --> 00:55:48,030 with only a single if statement and this expression 1081 00:55:48,030 --> 00:55:51,780 down here that uses itself in the definition, right? 1082 00:55:51,780 --> 00:55:55,282 So to visualize this, we actually want to use something called a debug50, 1083 00:55:55,282 --> 00:55:56,490 if you're familiar with that. 1084 00:55:56,490 --> 00:56:00,090 Debug50 lets you step through your code and go through 1085 00:56:00,090 --> 00:56:01,990 and see how things are working here. 1086 00:56:01,990 --> 00:56:05,910 So while we're at it, let's set a breakpoint right 1087 00:56:05,910 --> 00:56:08,760 at this point in our code, meaning we'll stop at this point, 1088 00:56:08,760 --> 00:56:11,460 and then we'll step through piece by piece 1089 00:56:11,460 --> 00:56:13,990 to see what's happening in the computer's memory. 1090 00:56:13,990 --> 00:56:19,100 So we'll go ahead and run this using debug50. 1091 00:56:19,100 --> 00:56:22,040 And we'll wait for debug50 to pull itself up. 1092 00:56:22,040 --> 00:56:24,680 And we'll step through our code in a minute here. 1093 00:56:24,680 --> 00:56:28,340 1094 00:56:28,340 --> 00:56:31,780 All right, let me zoom out just a little bit. 1095 00:56:31,780 --> 00:56:34,130 OK, so I'm seeing type a number in my prompt. 1096 00:56:34,130 --> 00:56:37,580 So I'll go ahead and type in the number for, right? 1097 00:56:37,580 --> 00:56:40,910 All right, so notice debug50 on the side here. 1098 00:56:40,910 --> 00:56:44,570 We now have number 4, and what we've done 1099 00:56:44,570 --> 00:56:46,940 is we've given our program a number. 1100 00:56:46,940 --> 00:56:48,350 Now, we're at this stage. 1101 00:56:48,350 --> 00:56:52,850 We've called factorial with n is 4, which 1102 00:56:52,850 --> 00:56:55,940 means that number here is equal to 4. 1103 00:56:55,940 --> 00:56:58,610 And if we look down at our call stack, that vocabulary 1104 00:56:58,610 --> 00:57:01,850 term we learned earlier, we see that we first called main, 1105 00:57:01,850 --> 00:57:04,490 and then we called factorial, right? 1106 00:57:04,490 --> 00:57:08,030 But we still need to call probably factorial again 1107 00:57:08,030 --> 00:57:11,450 because, if we go in here, we see that number is not 1. 1108 00:57:11,450 --> 00:57:12,830 Number is 4 right now. 1109 00:57:12,830 --> 00:57:15,110 It's not 1, so we can't return 1. 1110 00:57:15,110 --> 00:57:18,060 We will instead need to do this line of code. 1111 00:57:18,060 --> 00:57:22,440 But we can't solve this line of code until we run the factorial function 1112 00:57:22,440 --> 00:57:24,550 again with number 1 less than that. 1113 00:57:24,550 --> 00:57:29,590 So what we'll do is we'll step into this function factorial. 1114 00:57:29,590 --> 00:57:32,310 And now, see in our call stack, factorial shows up again. 1115 00:57:32,310 --> 00:57:34,560 We call factorial once, we're calling it again. 1116 00:57:34,560 --> 00:57:36,970 But now, what's going to happen? 1117 00:57:36,970 --> 00:57:39,310 Number is 3, so we're getting closer. 1118 00:57:39,310 --> 00:57:40,380 We're not quite there. 1119 00:57:40,380 --> 00:57:44,190 3 is not 1, so we're going to continue down again. 1120 00:57:44,190 --> 00:57:47,280 We'll go ahead, and we can't return 1 there, 1121 00:57:47,280 --> 00:57:49,630 but we can figure out what is 3 factorial? 1122 00:57:49,630 --> 00:57:52,560 Well, to find 3 factorial, we've got to find 2 factorial. 1123 00:57:52,560 --> 00:57:53,730 So we'll dive in again. 1124 00:57:53,730 --> 00:57:57,150 We'll say, OK, let's go deeper in our call stack. 1125 00:57:57,150 --> 00:58:00,360 Notice how if we scroll down, factorial is being called yet again. 1126 00:58:00,360 --> 00:58:02,130 we've called it the third time now. 1127 00:58:02,130 --> 00:58:04,380 Now, number is 2. 1128 00:58:04,380 --> 00:58:05,310 OK, let's keep going. 1129 00:58:05,310 --> 00:58:06,960 Number is not 1 yet. 1130 00:58:06,960 --> 00:58:09,720 To find 2 factorial, we got to find 1 factorial. 1131 00:58:09,720 --> 00:58:12,122 Let's go dive in again. 1132 00:58:12,122 --> 00:58:13,080 Look at our call stack. 1133 00:58:13,080 --> 00:58:15,700 We've called factorial four times now. 1134 00:58:15,700 --> 00:58:19,830 But at this point, we know number is 1, and so we 1135 00:58:19,830 --> 00:58:23,040 can simply and safely return 1. 1136 00:58:23,040 --> 00:58:25,440 We know the answer now, right? 1137 00:58:25,440 --> 00:58:28,320 So we'll do that, and then, that's correct, 1138 00:58:28,320 --> 00:58:29,910 we called this number 1 our base case. 1139 00:58:29,910 --> 00:58:31,530 We've hit our base case now. 1140 00:58:31,530 --> 00:58:34,530 We can start going back up our call stack. 1141 00:58:34,530 --> 00:58:39,040 So we can say let's finish that call of factorial. 1142 00:58:39,040 --> 00:58:44,001 Now, we're back at our third factorial call where number is 2. 1143 00:58:44,001 --> 00:58:45,850 Well, we solved that problem. 1144 00:58:45,850 --> 00:58:49,530 We know that 2 factorial is just 2 times 1. 1145 00:58:49,530 --> 00:58:52,650 And now we can return that 2 times 1. 1146 00:58:52,650 --> 00:58:55,260 Now, we're at that later version of factorial, 1147 00:58:55,260 --> 00:58:58,050 that second call where number is 3. 1148 00:58:58,050 --> 00:59:01,230 We know 3 factorial now is 3 times 2 times 1 based 1149 00:59:01,230 --> 00:59:03,330 on the earlier calls of factorial. 1150 00:59:03,330 --> 00:59:04,560 We're going to go again. 1151 00:59:04,560 --> 00:59:07,670 Now, we're at that very first call a factorial, number is 4. 1152 00:59:07,670 --> 00:59:11,640 Well, the answer here we now know is 4 times 3 times 2 times 1153 00:59:11,640 --> 00:59:13,950 1 based on this call stack we've done. 1154 00:59:13,950 --> 00:59:17,625 And now we can finish that program and type out 24. 1155 00:59:17,625 --> 00:59:20,410 1156 00:59:20,410 --> 00:59:25,600 So a bit of a leap of faith wherein you're trying to take for 1157 00:59:25,600 --> 00:59:28,930 granted that your program knows exactly what to do. 1158 00:59:28,930 --> 00:59:30,970 And it will eventually hit this base case. 1159 00:59:30,970 --> 00:59:33,130 If it doesn't hit that base case, we'll know 1160 00:59:33,130 --> 00:59:35,350 that maybe our program will keep running, keep running, keep running. 1161 00:59:35,350 --> 00:59:36,517 And that's not a good thing. 1162 00:59:36,517 --> 00:59:38,410 So we always need this base case here to stop 1163 00:59:38,410 --> 00:59:41,493 the call stack from growing and growing and growing and growing and always 1164 00:59:41,493 --> 00:59:44,138 finding that end case there. 1165 00:59:44,138 --> 00:59:46,930 But certainly, feel free to take some time thinking about this one. 1166 00:59:46,930 --> 00:59:49,750 So what questions do you all have about how this works 1167 00:59:49,750 --> 00:59:52,195 or how the recursion is working here? 1168 00:59:52,195 --> 00:59:56,570 1169 00:59:56,570 --> 01:00:00,050 Yes, so your question about, you know how recursion works, 1170 01:00:00,050 --> 01:00:03,930 but how do you know if a recursion is a good approach to a problem? 1171 01:00:03,930 --> 01:00:07,250 And what I encourage you to do is really try to draw things out 1172 01:00:07,250 --> 01:00:10,950 before you end up trying to code a recursive function. 1173 01:00:10,950 --> 01:00:17,120 So similarly, if we go back here, we saw that factorial was we drew things out. 1174 01:00:17,120 --> 01:00:23,430 We saw, hey, I notice that 3 factorial is embedded inside of 4 factorial. 1175 01:00:23,430 --> 01:00:26,630 So maybe it's a good use of a recursive algorithm here. 1176 01:00:26,630 --> 01:00:30,650 If you can find a problem and you find that problem 1177 01:00:30,650 --> 01:00:33,920 is made of a smaller problem that can be solved in the same way, 1178 01:00:33,920 --> 01:00:36,725 that's a hint you might want to use recursion in that instance. 1179 01:00:36,725 --> 01:00:41,040 1180 01:00:41,040 --> 01:00:43,685 What other questions are there on recursion in this case? 1181 01:00:43,685 --> 01:00:54,430 1182 01:00:54,430 --> 01:00:55,120 Let's see. 1183 01:00:55,120 --> 01:00:59,118 1184 01:00:59,118 --> 01:01:01,410 I'm seeing, what do we call the thing we did on line 4? 1185 01:01:01,410 --> 01:01:05,370 So if you scroll up to the top here in our program, 1186 01:01:05,370 --> 01:01:09,180 we'll see on line 4 we declared the function. 1187 01:01:09,180 --> 01:01:11,680 We gave the compiler our prototype. 1188 01:01:11,680 --> 01:01:14,250 So this right here is called our function prototype 1189 01:01:14,250 --> 01:01:16,950 and, more specifically, putting this piece right here 1190 01:01:16,950 --> 01:01:18,690 is declaring our function. 1191 01:01:18,690 --> 01:01:22,950 We're telling c, hey, we have this function that returns an integer. 1192 01:01:22,950 --> 01:01:25,410 It is named factorial and takes an argument 1193 01:01:25,410 --> 01:01:26,880 called number that is an integer. 1194 01:01:26,880 --> 01:01:30,330 And that in respect we're declaring our function there. 1195 01:01:30,330 --> 01:01:33,550 1196 01:01:33,550 --> 01:01:35,680 Is there a way to make this code shorter? 1197 01:01:35,680 --> 01:01:36,400 Perhaps. 1198 01:01:36,400 --> 01:01:38,525 I won't go out on a limb and say that this is maybe 1199 01:01:38,525 --> 01:01:40,150 the most short you can make it. 1200 01:01:40,150 --> 01:01:42,350 Maybe there is a way to do it. 1201 01:01:42,350 --> 01:01:45,085 But certainly, if it seems well designed for us here. 1202 01:01:45,085 --> 01:01:47,760 1203 01:01:47,760 --> 01:01:51,510 And another question is, can we use a loop here? 1204 01:01:51,510 --> 01:01:53,050 We actually could use a loop here. 1205 01:01:53,050 --> 01:01:55,380 So let's say we didn't want to use recursion. 1206 01:01:55,380 --> 01:01:57,690 Maybe it feels a little too much like a leap of faith. 1207 01:01:57,690 --> 01:02:01,300 So what we'll do is we'll, maybe instead of this, we'll say, 1208 01:02:01,300 --> 01:02:05,670 OK, we know that, when number is 1, we'll go ahead and return 1. 1209 01:02:05,670 --> 01:02:10,350 But otherwise, we know that factorial is really just that number times 1 1210 01:02:10,350 --> 01:02:12,270 less than it times 1 less than it. 1211 01:02:12,270 --> 01:02:13,330 So we could do this. 1212 01:02:13,330 --> 01:02:15,540 We could say something like a for loop. 1213 01:02:15,540 --> 01:02:17,370 We could take for. 1214 01:02:17,370 --> 01:02:24,180 Maybe we'll start at i is equal to our number and go until i is-- 1215 01:02:24,180 --> 01:02:29,510 maybe, let's say, as long as i is greater than 0, 1216 01:02:29,510 --> 01:02:33,290 and then keep subtracting from i as we go through. 1217 01:02:33,290 --> 01:02:38,990 So what we could do is maybe say that our solution is going 1218 01:02:38,990 --> 01:02:45,260 to be first probably equal to number. 1219 01:02:45,260 --> 01:02:52,970 And then we could say solution is equal to that solution times some other-- 1220 01:02:52,970 --> 01:02:54,178 times i, I believe. 1221 01:02:54,178 --> 01:02:56,720 And feel free to correct me if I'm doing anything wrong here. 1222 01:02:56,720 --> 01:02:59,750 I think what might happen though, is we have solution times number. 1223 01:02:59,750 --> 01:03:04,650 Something like this, number minus 1, and so on and so forth. 1224 01:03:04,650 --> 01:03:07,760 But basically what we're doing here is trying to make a loop out 1225 01:03:07,760 --> 01:03:11,660 of this, trying to say, OK, let's start with 4 and multiply 3 to it 1226 01:03:11,660 --> 01:03:14,300 and then 2 to it and then 1 to it through a loop. 1227 01:03:14,300 --> 01:03:15,950 And we could do that. 1228 01:03:15,950 --> 01:03:19,560 But often what happens is that maybe recursion is more elegant solution 1229 01:03:19,560 --> 01:03:20,060 here. 1230 01:03:20,060 --> 01:03:21,840 This seems like much more lines of code. 1231 01:03:21,840 --> 01:03:27,880 So maybe, in this case, we could use our recursive solution that we had before. 1232 01:03:27,880 --> 01:03:32,920 And a question related to this is, can all recursions be rewritten as loops? 1233 01:03:32,920 --> 01:03:35,030 It's a good question. 1234 01:03:35,030 --> 01:03:38,260 I would say that at least some of them could be, as we demonstrated here. 1235 01:03:38,260 --> 01:03:41,350 I think there are some problems though where recursion is really 1236 01:03:41,350 --> 01:03:44,380 going to be helpful for you because what recursion does 1237 01:03:44,380 --> 01:03:47,920 is it allows you to have a whole new smaller 1238 01:03:47,920 --> 01:03:51,100 problem to work with and take a big chunk out of that problem 1239 01:03:51,100 --> 01:03:52,540 and work with that smaller one. 1240 01:03:52,540 --> 01:03:55,750 So often, in computer science, we want to solve bigger problems 1241 01:03:55,750 --> 01:03:57,370 by first solving smaller ones. 1242 01:03:57,370 --> 01:04:00,687 And a loop might not always give you that same leverage 1243 01:04:00,687 --> 01:04:02,770 that you might have by breaking down a big problem 1244 01:04:02,770 --> 01:04:04,910 and making it into a smaller one. 1245 01:04:04,910 --> 01:04:05,785 But a great question. 1246 01:04:05,785 --> 01:04:09,060 1247 01:04:09,060 --> 01:04:11,300 Other questions to you on this recursion here? 1248 01:04:11,300 --> 01:04:20,310 1249 01:04:20,310 --> 01:04:26,670 All right, so that does just about bring us to the very end of our section. 1250 01:04:26,670 --> 01:04:29,110 We talked about algorithms, how we compare them. 1251 01:04:29,110 --> 01:04:31,260 We talked about structs and how we might use them. 1252 01:04:31,260 --> 01:04:34,980 We talked about recursion, how we can identify recursion and ultimately write 1253 01:04:34,980 --> 01:04:37,200 our own recursive functions. 1254 01:04:37,200 --> 01:04:39,900 As you go off into this week, you will, in fact, 1255 01:04:39,900 --> 01:04:42,570 do your own kind of algorithms that involve structs, 1256 01:04:42,570 --> 01:04:46,060 that might involve recursion, that might involve all these different elements. 1257 01:04:46,060 --> 01:04:48,685 And so I wish you the very best as you're going off and working 1258 01:04:48,685 --> 01:04:49,838 on your own work this week. 1259 01:04:49,838 --> 01:04:51,630 Thank you so much for joining us over Zoom. 1260 01:04:51,630 --> 01:04:53,205 It was wonderful to see you all here. 1261 01:04:53,205 --> 01:04:55,080 Hope to see you in the coming weeks, and I'll 1262 01:04:55,080 --> 01:04:56,955 be happy to stay around and answer questions. 1263 01:04:56,955 --> 01:04:58,490 Thank you all. 1264 01:04:58,490 --> 01:05:00,000