1 00:00:01,750 --> 00:00:09,370 OK, so our next topic is one that many students find quite difficult to wrap their head around despite 2 00:00:09,370 --> 00:00:10,540 its simplicity. 3 00:00:11,890 --> 00:00:13,980 That topic is recursion. 4 00:00:14,000 --> 00:00:21,410 And in this lecture, we will hopefully demystify some of the confusion surrounding it, so let's go 5 00:00:21,410 --> 00:00:22,670 ahead and get started. 6 00:00:25,240 --> 00:00:26,470 So what is recursion? 7 00:00:27,160 --> 00:00:32,530 For those of you that haven't yet heard of it, a simple explanation is that it is a problem-solving 8 00:00:32,530 --> 00:00:39,700 technique and it is the technique that uses function calls instead of loops for solving problems that 9 00:00:39,700 --> 00:00:40,960 require repetition. 10 00:00:42,160 --> 00:00:48,040 So while loops are considered iterative solutions, when we talk about recursion, we are talking about 11 00:00:48,040 --> 00:00:54,550 a function calling itself somehow, whether that be a direct call kind of like how you see in the picture 12 00:00:54,730 --> 00:00:59,080 here on the slide that's inside the function implementation itself. 13 00:00:59,440 --> 00:01:05,950 Or maybe it is indirect where this recursion function calls another function that in turn calls this 14 00:01:05,950 --> 00:01:07,270 recursion function again. 15 00:01:08,360 --> 00:01:14,300 This function that you see here, recursion would be considered a recursive function, although it is 16 00:01:14,300 --> 00:01:15,710 not very useful. 17 00:01:18,240 --> 00:01:21,810 So let's take a closer look at this function. 18 00:01:22,560 --> 00:01:27,990 In fact, you should go ahead and just pause the video and write a C++ program, probably in a text 19 00:01:27,990 --> 00:01:34,140 editor, so it's more simple write a program that implements this function and calls it. 20 00:01:34,830 --> 00:01:36,330 So go ahead and do that. 21 00:01:38,260 --> 00:01:43,270 OK, so if you went ahead and did that, you might have noticed something weird. 22 00:01:45,040 --> 00:01:48,220 It most likely gave you a segmentation fault. 23 00:01:49,030 --> 00:01:53,350 And the reason for this is something that we call Stack Overflow. 24 00:01:54,430 --> 00:01:58,360 So let's go ahead and go over that term. 25 00:01:58,390 --> 00:02:01,030 What is a stack and what a stack overflow mean? 26 00:02:04,940 --> 00:02:09,500 So technically, a stack is just a data structure. 27 00:02:11,000 --> 00:02:16,610 You can imagine it like a stack of something, you know, have some kind of analogy that works best 28 00:02:16,610 --> 00:02:17,150 for you. 29 00:02:17,430 --> 00:02:20,930 You can think of it like plates, pancakes, any things you could stack on top of each other. 30 00:02:22,190 --> 00:02:26,060 But it's just a data structure where things are piled on top of each other. 31 00:02:27,490 --> 00:02:33,640 We are going to look at using this data structure in our code later to help us with our programs. 32 00:02:34,540 --> 00:02:40,930 But that is something different than what we're talking about today, which is a region of the computer's 33 00:02:40,930 --> 00:02:46,210 memory that is called the stack and functions like that stack data structure. 34 00:02:47,540 --> 00:02:55,730 So basically, each time a function is called another, what we call a stack frame is added to the stack, 35 00:02:55,730 --> 00:03:00,500 and we refer to this as pushing a new frame to the stack. 36 00:03:02,080 --> 00:03:11,380 So this frame that's pushed to the stack, it contains information about the current function, it's 37 00:03:11,380 --> 00:03:18,820 a function call and it'll have the things like the local variables and stuff like that in it, for example. 38 00:03:21,480 --> 00:03:23,640 OK, so what is Stack Overflow? 39 00:03:23,970 --> 00:03:31,110 Well, the problem with this function that we were looking at is that it just calls itself and has no 40 00:03:31,530 --> 00:03:34,230 nothing really stopping it, no mechanism to stop it. 41 00:03:34,230 --> 00:03:42,210 So it would most likely just infinitely call itself if something didn't intervene, although the program 42 00:03:42,210 --> 00:03:44,130 did stop and you got a segfault. 43 00:03:45,230 --> 00:03:52,010 That is because the stacked section of the computer's memory eventually runs out of space when we're 44 00:03:52,010 --> 00:03:59,750 pushing those frames to it, those frames and all that information actually overflows into another segment 45 00:03:59,750 --> 00:04:00,500 of memory. 46 00:04:00,830 --> 00:04:07,640 And that's what causes the Stack Overflow and is what led to you seeing that segfault air. 47 00:04:11,480 --> 00:04:17,690 So let's look in a more useful example, recursion that does something besides just having a function 48 00:04:17,690 --> 00:04:18,650 call itself. 49 00:04:20,320 --> 00:04:27,760 So this function here returns the sum of all numbers up to the number in that it's being passed in the 50 00:04:27,760 --> 00:04:28,990 function as an argument. 51 00:04:30,050 --> 00:04:38,180 And so what we are doing here is basically solving this same problem backwards, so we're starting with 52 00:04:38,180 --> 00:04:42,890 the number that we want to go up to and including for our some. 53 00:04:44,430 --> 00:04:51,150 Rather than doing it forwards and you can see that is happening here in this return statement. 54 00:04:52,090 --> 00:04:55,750 Where let's say we start out with a four. 55 00:04:57,340 --> 00:05:05,290 What we're doing is we would return for plus the sum of three because we have four minus one and it 56 00:05:05,290 --> 00:05:10,630 would go back here and do the same thing for three, it would be three plus the sum of two. 57 00:05:11,230 --> 00:05:14,950 And it just works kind of in reverse like that. 58 00:05:16,040 --> 00:05:20,300 But you notice that we still don't really have a stopping mechanism. 59 00:05:21,660 --> 00:05:27,810 So how would we set that up to prevent it from going on infinitely or until we get a Stack Overflow? 60 00:05:30,190 --> 00:05:36,280 So the way we're going to do this is use something called a base case. 61 00:05:38,090 --> 00:05:45,080 So as we work backwards to solve this problem, we're going to go and tell in is zero. 62 00:05:45,770 --> 00:05:52,490 And that will be our stopping condition, which is our base case, and once in is zero, we're just 63 00:05:52,490 --> 00:06:00,320 going to return zero and this is where the magic happens because this is where we will do our actual 64 00:06:00,320 --> 00:06:02,150 addition that creates the some. 65 00:06:02,630 --> 00:06:10,130 It's kind of like we're putting off the work as we keep bouncing back and forth between this return 66 00:06:10,130 --> 00:06:11,510 and the top of the function. 67 00:06:12,020 --> 00:06:17,540 We're kind of saying like, OK, you want me to do four, I'm going to go ahead and do three and try 68 00:06:17,540 --> 00:06:21,950 and figure that out, OK, you want me to do three and we'll go ahead and do two and figure that out. 69 00:06:22,190 --> 00:06:30,050 And I recognize that you're asking me each time to add the current in that I'm on and the previous one. 70 00:06:31,430 --> 00:06:34,790 And it'll get all the way to zero and we'll return zero. 71 00:06:35,060 --> 00:06:40,510 And then it will go back through all that work that it put aside and add up all of these different ends. 72 00:06:41,270 --> 00:06:44,780 The state, you know that endless end so we can get our summit. 73 00:06:45,260 --> 00:06:49,310 So let's go ahead and work through this example to see how how it actually works. 74 00:06:50,970 --> 00:06:51,390 So. 75 00:06:52,820 --> 00:06:54,980 We start out with N equals four. 76 00:06:56,040 --> 00:06:59,130 Then we're going to have an equals three, as we saw. 77 00:07:00,030 --> 00:07:07,200 So we have any goals for it, go down here for IS was not equal to zero, so we didn't return. 78 00:07:07,210 --> 00:07:15,030 We returned this line here, which is four plus the sum of four minus one, which is three, so we went 79 00:07:15,030 --> 00:07:15,930 back to the top. 80 00:07:16,440 --> 00:07:17,730 So now we're on this call. 81 00:07:18,420 --> 00:07:19,290 Same thing. 82 00:07:20,470 --> 00:07:22,910 You know, three minus one is to go back up here. 83 00:07:24,880 --> 00:07:26,080 Two win, one is one. 84 00:07:27,680 --> 00:07:31,100 And of course, one minus one is zero now and is zero. 85 00:07:31,340 --> 00:07:33,740 And we're saying if N equals zero. 86 00:07:33,770 --> 00:07:34,520 Yes, it does. 87 00:07:34,820 --> 00:07:36,620 Let's go ahead and return zero. 88 00:07:36,860 --> 00:07:39,800 And this is where the magic of recursion happens. 89 00:07:41,010 --> 00:07:47,280 So what we're going to do is we're returning zero from this function, call this stack frame back to 90 00:07:47,280 --> 00:07:47,850 this one. 91 00:07:49,930 --> 00:07:53,680 And then we're basically adding, as you see, we return to zero. 92 00:07:55,670 --> 00:08:02,300 And we're adding that to one, so in this room right here in was one. 93 00:08:03,140 --> 00:08:09,020 Since we returned zero from this frame and it came back here, we're looking at this line right here 94 00:08:09,020 --> 00:08:10,390 to do this edition right here. 95 00:08:10,400 --> 00:08:17,540 So return when in is one, we returning one plus what was returned from here, which is zero. 96 00:08:17,600 --> 00:08:19,670 So you notice there was this function call here. 97 00:08:20,890 --> 00:08:26,020 When we're talking about zero or thinking about this, this specific function call this stack frame 98 00:08:26,260 --> 00:08:31,780 that returns zero, so you basically can take that and put it right here and now in the function call 99 00:08:31,780 --> 00:08:33,310 in which in was one. 100 00:08:34,460 --> 00:08:37,370 We're having this line right here is looking like this. 101 00:08:38,030 --> 00:08:41,810 We're going to return one plus that zero that was returned. 102 00:08:42,050 --> 00:08:43,400 So let's continue this pattern. 103 00:08:44,960 --> 00:08:50,090 We have when Annie goes to win, you win to plus the one that was returned, that's three. 104 00:08:53,160 --> 00:08:54,450 We have an equals three. 105 00:08:54,630 --> 00:08:59,220 We're doing three plus the three that was returned from this frame. 106 00:09:01,130 --> 00:09:08,480 And when it equals four, we're doing this four plus six, which was the sum of this previous result 107 00:09:08,480 --> 00:09:08,810 there. 108 00:09:09,080 --> 00:09:10,490 So we end up with 10. 109 00:09:11,550 --> 00:09:13,740 So four plus three plus two plus one. 110 00:09:14,370 --> 00:09:20,510 That was our sum, plus zero, of course, that was our son there, so we ended up with 10. 111 00:09:20,520 --> 00:09:22,140 So hopefully that makes sense. 112 00:09:22,630 --> 00:09:26,880 I went ahead and just tried to start out with a basic example, so you could kind of just see what the 113 00:09:26,880 --> 00:09:28,710 recursion itself is actually doing. 114 00:09:28,710 --> 00:09:36,480 Like this is where in this specific example of recursion, the interesting stuff is happening in the 115 00:09:36,480 --> 00:09:40,200 recursive process when we go back down the stack here. 116 00:09:42,330 --> 00:09:43,680 OK, so let's continue. 117 00:09:45,370 --> 00:09:49,810 Let's look at a slightly less trivial example, something a little more complex. 118 00:09:50,620 --> 00:09:57,610 I'm not sure if you have heard of the Fibonacci sequence, but this is it right here. 119 00:09:58,700 --> 00:10:08,720 And it is obtained by adding the previous to Fibonacci numbers, so whatever number you're talking about 120 00:10:08,720 --> 00:10:10,190 in the Fibonacci sequence. 121 00:10:12,360 --> 00:10:14,010 Like, for example, to. 122 00:10:16,260 --> 00:10:16,950 Right here. 123 00:10:17,070 --> 00:10:20,310 So this would be one to sorry. 124 00:10:20,860 --> 00:10:22,690 Well, yeah, the. 125 00:10:22,710 --> 00:10:24,420 It would be the sea. 126 00:10:26,810 --> 00:10:30,040 0tH, 1st, 2nd, 3rd. 127 00:10:30,560 --> 00:10:38,130 So this third Fibonacci number is going to be the result of something the previous two right here, 128 00:10:38,150 --> 00:10:41,060 so one plus one is two. 129 00:10:41,630 --> 00:10:51,800 So that's kind of how the feminazi sequence works, and we are writing a recursive function to calculate 130 00:10:51,830 --> 00:10:53,840 the end Fibonacci numbers. 131 00:10:53,840 --> 00:10:55,370 So just some Fibonacci number. 132 00:10:55,700 --> 00:11:01,700 And you see here, I've already started with an example where we are looking at the. 133 00:11:04,690 --> 00:11:12,550 Six Fibonacci number, so we have zero one two three four five six. 134 00:11:13,360 --> 00:11:18,630 So the index of six in this, that's what we're talking about in this example. 135 00:11:18,640 --> 00:11:20,980 So calculate the Fibonacci numbers. 136 00:11:20,980 --> 00:11:25,540 So this is a function, a recursive function that would do that. 137 00:11:25,930 --> 00:11:30,370 We're passing in as the feminazi number we want. 138 00:11:31,350 --> 00:11:39,930 And then what we are doing is setting up our base case here where we say, if in is less than or equal 139 00:11:39,930 --> 00:11:46,650 to one return in and you'll see why we're doing that in a moment, it's because just a quick explanation 140 00:11:46,650 --> 00:11:47,190 is that. 141 00:11:49,240 --> 00:11:55,840 This tree here that I'm about to explain is what's representing the recursive calls and these stack 142 00:11:56,830 --> 00:11:57,760 frames here. 143 00:11:57,790 --> 00:12:04,390 Each one of these nodes, these dots here, and you notice that at the bottom, these are base cases 144 00:12:04,660 --> 00:12:08,910 and you can see that some of them are one in, some of them are zero. 145 00:12:08,920 --> 00:12:12,610 So that's why we're putting less than or equal to one here. 146 00:12:14,670 --> 00:12:19,860 And then just like I said, you add the previous two numbers, so what we're doing is calling the function 147 00:12:19,860 --> 00:12:29,710 again with our, you know, one less than in and then adding to less than in. 148 00:12:29,790 --> 00:12:36,060 So these are represent our two previous numbers that we're summing up to get the Fibonacci number. 149 00:12:38,110 --> 00:12:44,920 And just kind of taking a look again at recursion in general and the purpose and how it works. 150 00:12:46,350 --> 00:12:55,050 We want to know, let's say, this six Fibonacci number, but to know that to solve that by using recursion. 151 00:12:56,200 --> 00:13:01,810 We're going to need to figure out these smaller sub problems. 152 00:13:03,000 --> 00:13:09,930 And when I talk about smaller sub problems, it's kind of a precursor to what we're going to speak more 153 00:13:09,930 --> 00:13:15,930 about in the future and learn more about when we talk about divide and conquer algorithms and things 154 00:13:15,930 --> 00:13:16,410 like that. 155 00:13:16,650 --> 00:13:17,730 A lot of times it's. 156 00:13:19,200 --> 00:13:27,840 A good way to solve problems is to break the problem into smaller sub problems and solve those by breaking 157 00:13:27,840 --> 00:13:33,930 that into smaller sub problems until you reach a point where it's quite simple to solve. 158 00:13:34,140 --> 00:13:37,940 And then you can kind of in this example with recursion. 159 00:13:37,950 --> 00:13:43,920 Then once we have that base case, we can solve all of these other sub problems that we had back up 160 00:13:43,920 --> 00:13:45,030 to our original problem. 161 00:13:45,990 --> 00:13:49,800 So that's just kind of a general explanation of what's happening here with this. 162 00:13:49,830 --> 00:13:55,440 We have two recursive calls, so it's slightly more complex than that previous example where we only 163 00:13:55,440 --> 00:13:56,790 had one recursive call. 164 00:13:57,750 --> 00:14:00,660 So let me get into explaining what this is right here. 165 00:14:01,320 --> 00:14:06,750 This tree structure, it is in fact called a tree is a recursive tree. 166 00:14:08,270 --> 00:14:08,750 And. 167 00:14:10,080 --> 00:14:17,280 Like I said, what this represents is each one of these gray dots or nodes or whatever you'd like to 168 00:14:17,280 --> 00:14:19,350 use to represent that. 169 00:14:20,700 --> 00:14:25,320 These are each stack frames or actual function calls. 170 00:14:26,750 --> 00:14:33,770 And the number inside here is in at that specific function call what in is what state and has there. 171 00:14:33,980 --> 00:14:36,530 So we start out as six in this example. 172 00:14:36,530 --> 00:14:38,720 So we want to find the six Fibonacci number. 173 00:14:40,650 --> 00:14:49,680 The arrows to the left are pointing to this function, call the N minus one so one before you know, 174 00:14:49,680 --> 00:14:55,110 the like one less than the N that we are talking about the Fibonacci number. 175 00:14:55,800 --> 00:14:58,770 The right call function call. 176 00:14:58,770 --> 00:15:00,120 Is this one right here? 177 00:15:01,630 --> 00:15:09,250 So it is the, you know, two before the end Fibonacci number that we are at on any given function call, 178 00:15:10,300 --> 00:15:16,990 and you see that this pattern continues, we have two children breaking off here because we have to 179 00:15:17,470 --> 00:15:18,640 function calls, so. 180 00:15:19,950 --> 00:15:28,140 I'm also going to refer to things like that, like this node and this node are child nodes of this node 181 00:15:28,140 --> 00:15:28,550 right here. 182 00:15:28,560 --> 00:15:33,810 So you could consider this node with the six, the parent node of these two child nodes. 183 00:15:35,790 --> 00:15:39,960 And so just to kind of do a quick recap on that. 184 00:15:41,520 --> 00:15:47,850 These this sub tree over here in this sub over here and so on and so forth. 185 00:15:48,570 --> 00:15:55,530 The left is represented by this function call and the right is represented by this function call here. 186 00:15:56,920 --> 00:15:59,990 OK, so let's take a little bit deeper, look at the tree then. 187 00:16:01,210 --> 00:16:03,160 So we start out with six here. 188 00:16:04,140 --> 00:16:10,470 We originally start with our function and we pass six to our function, six is not less than or equal 189 00:16:10,470 --> 00:16:20,070 to one, so we go down here and we say, Hey, return fib of six minus one plus five oh six minus two, 190 00:16:20,070 --> 00:16:26,070 but right when you hit this, it's going to jump back up here to this function, call again with five. 191 00:16:26,610 --> 00:16:28,440 And so that's what this is right here. 192 00:16:29,910 --> 00:16:35,490 And so if we just keep traversing it in that fashion, this tree right here and we're just like, OK, 193 00:16:35,490 --> 00:16:40,470 it's making us jump back up, jump back up here, and it's kind of setting this aside that we need to 194 00:16:40,470 --> 00:16:42,960 add this function, call to it each time. 195 00:16:43,680 --> 00:16:48,660 If you're just taking left turns, it kind of goes like this like six two five five two four four two 196 00:16:48,660 --> 00:16:52,350 three three two two two two one. 197 00:16:52,350 --> 00:16:56,910 And we stop here because this goes with our base case here. 198 00:16:57,240 --> 00:17:01,410 When MN is one in is equal to one. 199 00:17:01,590 --> 00:17:03,230 We said less than or equal to. 200 00:17:03,270 --> 00:17:08,050 And so it's just going to return in and since in is one. 201 00:17:08,280 --> 00:17:13,050 We're just returning this right here and that's going to return back up to here. 202 00:17:15,920 --> 00:17:21,050 So if we look at the right call and let's go back down to this bottom part right here. 203 00:17:22,940 --> 00:17:31,490 We have two and two minus two is zero, so we would go back up to the top for this function call in 204 00:17:31,490 --> 00:17:33,990 would be zero zero is less than one. 205 00:17:34,010 --> 00:17:37,160 So we're going to return it in is zero. 206 00:17:37,460 --> 00:17:41,960 So this is going to get added to this. 207 00:17:41,960 --> 00:17:44,510 And you know, this is what's going to get returns. 208 00:17:44,510 --> 00:17:49,670 So when I was saying, we're going to turn that back up here from this one, what we're actually doing 209 00:17:49,670 --> 00:17:53,660 this, we're returning this some of these to back up to this node. 210 00:17:53,660 --> 00:17:56,450 So it would be one plus zero. 211 00:17:58,760 --> 00:18:04,550 So now that you kind of have a general understanding of what these areas are for, how we're representing 212 00:18:04,550 --> 00:18:09,890 these recursive calls and the whole idea of this tree, you know, these are base cases down here like 213 00:18:09,890 --> 00:18:14,000 this, this this, this this all these are base cases. 214 00:18:14,480 --> 00:18:17,780 Let's go ahead and walk through this example here. 215 00:18:17,990 --> 00:18:25,280 I'm going to start down at the base cases and work our way back up to show how the recursion actually 216 00:18:25,280 --> 00:18:26,180 solve this. 217 00:18:26,660 --> 00:18:28,550 So let's go ahead and do that. 218 00:18:30,050 --> 00:18:39,120 So we start down at this left most portion of the tree where we had in is to. 219 00:18:39,800 --> 00:18:44,360 And then we did this recursive call to minus one, which was one. 220 00:18:44,720 --> 00:18:47,150 And then we had two minus two, which is zero. 221 00:18:48,110 --> 00:18:49,190 So we ended up. 222 00:18:50,150 --> 00:18:55,520 You notice the one, just like I talked about that recursive call where it was one, it returned one. 223 00:18:58,160 --> 00:19:03,200 And so that one can basically be put right here and remember this right here. 224 00:19:04,330 --> 00:19:11,830 Represents this right here, and then you can imagine a plus sign right here, and then we had two months 225 00:19:11,830 --> 00:19:15,520 to is zero zero was less than one, so we return zero. 226 00:19:15,730 --> 00:19:21,340 And imagine that that can be taken and put, you know, right here. 227 00:19:22,180 --> 00:19:32,080 And so basically like this is representing this really what these are representing are these returned 228 00:19:32,080 --> 00:19:32,500 values. 229 00:19:32,500 --> 00:19:39,310 But to help us understand it, this function call is going to be added to this function call. 230 00:19:39,310 --> 00:19:43,240 And what we want to do is add this one plus this zero. 231 00:19:43,780 --> 00:19:49,720 So the one that was returned and this zero that was returned, we're putting them back into the function 232 00:19:49,720 --> 00:19:50,650 calls right here. 233 00:19:51,280 --> 00:19:52,720 So that equals one. 234 00:19:53,860 --> 00:20:01,810 And so that's going to go the answer of one is going to go back up to this recursive function call. 235 00:20:03,950 --> 00:20:06,790 OK, so we're going to move on to this next portion then. 236 00:20:08,690 --> 00:20:12,830 I'm color coding these, so it's a little easier to understand. 237 00:20:13,580 --> 00:20:22,520 The green is going to be our base cases, you know, we had this one in the zero where our base case 238 00:20:22,520 --> 00:20:23,450 returned values. 239 00:20:24,290 --> 00:20:27,440 We returned one up to here up into this node. 240 00:20:27,950 --> 00:20:30,620 So that is the yellow right here. 241 00:20:30,920 --> 00:20:37,790 And then we have another base case right here, which is one because when we have an equal three. 242 00:20:39,070 --> 00:20:45,610 You notice that we did three minus one for this call and we had two right here, and that's what led 243 00:20:45,610 --> 00:20:47,200 us to this whole sub here. 244 00:20:48,190 --> 00:20:54,850 But then when we did three minus two, that was this right here and we came back up here, three minus 245 00:20:54,850 --> 00:20:55,780 two is one. 246 00:20:56,110 --> 00:20:58,810 And one suffices for our base case here. 247 00:20:59,290 --> 00:21:01,660 So that's why we have this one right here. 248 00:21:01,660 --> 00:21:02,950 It has no children. 249 00:21:02,950 --> 00:21:07,030 It's a base case and that's represented by this green right here. 250 00:21:07,030 --> 00:21:13,810 So we have the one that was returned back up here, plus this base case one right here, which is to. 251 00:21:15,190 --> 00:21:18,160 So hopefully you're following along with me, let's keep going. 252 00:21:19,390 --> 00:21:21,970 I'm going to jump over here to solve this little problem. 253 00:21:22,720 --> 00:21:27,070 So we have another base case we have one plus zero is one. 254 00:21:28,980 --> 00:21:34,800 We get this blue one here, and, you know, as we took our answer here and our answer here, you can 255 00:21:34,800 --> 00:21:40,850 now see this whole green box as like one of these. 256 00:21:40,920 --> 00:21:46,990 And this whole game box as one of these here, some members of problems, these are two such problems. 257 00:21:47,080 --> 00:21:48,780 Imagine a plus sign right here. 258 00:21:49,440 --> 00:21:55,140 So we have our one that was passed back up to here or sorry, not that we have our two. 259 00:21:55,530 --> 00:22:01,770 We added these two to get two, and then we added these base cases to get this blue one here. 260 00:22:02,700 --> 00:22:07,770 And so the one comes back up to here, the blue one kind of back up to here. 261 00:22:07,770 --> 00:22:13,140 And this red too comes back up to here and we have two plus one is three. 262 00:22:16,480 --> 00:22:18,460 So I'm going to do these here real quick. 263 00:22:18,640 --> 00:22:23,080 And we have a one plus zero is one that one comes back up here. 264 00:22:23,500 --> 00:22:27,550 We have the blue one plus our green base case one equals two. 265 00:22:29,200 --> 00:22:30,310 Let's go back up here. 266 00:22:30,340 --> 00:22:36,760 We take this three that gets returned up to this function call and we have our three plus hour orange 267 00:22:36,760 --> 00:22:38,650 too, which just goes right here. 268 00:22:39,130 --> 00:22:43,260 So two to hear this three two here, we're adding them together. 269 00:22:43,270 --> 00:22:45,880 You mentioned that plus sign at five. 270 00:22:45,940 --> 00:22:47,950 Let's go over and solve this over here now. 271 00:22:49,240 --> 00:22:50,560 We have our base cases. 272 00:22:50,560 --> 00:22:52,540 One goes up to here. 273 00:22:52,900 --> 00:22:53,770 That's to. 274 00:22:55,090 --> 00:22:56,290 We have one right here. 275 00:22:57,490 --> 00:23:00,790 This two plus this one is three. 276 00:23:02,190 --> 00:23:09,510 Now we go up to here and we add our five plus three, so we had this five from here. 277 00:23:09,810 --> 00:23:13,470 This three first year, we added them and we get eight. 278 00:23:13,890 --> 00:23:17,460 And that is what is returning for our final answer here. 279 00:23:18,030 --> 00:23:24,450 So the six Fibonacci zero one two three four five six is eight. 280 00:23:25,260 --> 00:23:27,660 And so you can now see how that was solved. 281 00:23:27,660 --> 00:23:33,180 It looks a little complex, but if you walk through these recursive three examples, they can kind of 282 00:23:33,180 --> 00:23:37,830 explain it in greater detail and make it a little more obvious. 283 00:23:40,130 --> 00:23:44,900 So you might notice that this has a pretty poor time complexity. 284 00:23:46,070 --> 00:23:54,200 You notice that there are some repetition, so you can see this whole sub tree here is pretty much, 285 00:23:54,320 --> 00:23:55,550 you know, it's reflected over here. 286 00:23:55,550 --> 00:23:58,100 So I had to calculate this same thing multiple times. 287 00:23:58,370 --> 00:24:00,110 These trees can get pretty big. 288 00:24:01,130 --> 00:24:02,300 You should go ahead and. 289 00:24:03,330 --> 00:24:06,360 Put this in a program, this function here. 290 00:24:06,540 --> 00:24:15,000 Make a C++ program, write this function and then go ahead and pass 50 as end to the initial call there 291 00:24:15,000 --> 00:24:20,670 and see like how long your computer takes to solve that problem. 292 00:24:20,820 --> 00:24:26,910 This tree is going to be really big, and you'll notice that the program should hang up quite a bit 293 00:24:26,910 --> 00:24:31,290 or take a really long time to solve it, at which point you might just want to exit out. 294 00:24:32,160 --> 00:24:37,650 So, yeah, that'll make you realize that it does have a pretty poor time complexity. 295 00:24:37,650 --> 00:24:40,760 And later on, we're going to optimize this with another programming strategy. 296 00:24:40,770 --> 00:24:44,460 So since it's pretty slow, don't worry about that. 297 00:24:44,460 --> 00:24:50,870 We're just going over recursion and kind of some more naive solutions that can be further optimized 298 00:24:50,880 --> 00:24:51,360 later on. 299 00:24:54,060 --> 00:24:59,880 Another thing to look at that we haven't talked about yet of something that goes way we go is that each 300 00:24:59,880 --> 00:25:02,460 one of the nodes on this tree. 301 00:25:02,640 --> 00:25:06,330 These gray nodes here. 302 00:25:07,520 --> 00:25:14,270 They represent a stacked frame like we talked about, but you can also think of that as memory space 303 00:25:14,960 --> 00:25:16,040 being taken up. 304 00:25:16,040 --> 00:25:21,440 So we talked about how the stack frames pile up in the stack, which is a region of memory. 305 00:25:22,280 --> 00:25:25,350 Something we haven't really talked about yet is space complexity. 306 00:25:25,370 --> 00:25:30,260 We've talked a little bit about time complexity, but later on we're going to also talk about taking 307 00:25:30,260 --> 00:25:35,230 space in an account to how efficient an algorithm is. 308 00:25:35,240 --> 00:25:36,980 It's not just about how fast it is. 309 00:25:37,310 --> 00:25:39,380 It's also about how much space it takes up. 310 00:25:40,250 --> 00:25:47,240 So just wanted to add that in here right now, just so you kind of plant a seed about this idea of space 311 00:25:47,240 --> 00:25:48,560 complexity as well. 312 00:25:49,490 --> 00:25:56,840 You know, if you have a huge tree with recursion here, you should definitely consider when you're 313 00:25:56,840 --> 00:26:03,470 writing a recursive algorithm, consider the fact that these stack frames are what are going to be used 314 00:26:03,470 --> 00:26:07,880 for our idea of how much space the algorithm takes up. 315 00:26:07,910 --> 00:26:08,930 So keep that in mind. 316 00:26:10,400 --> 00:26:15,890 One last thing I just want to point out that we can also use recursion to traverse data structures. 317 00:26:15,890 --> 00:26:19,430 So this is a simple example with just a vector. 318 00:26:20,810 --> 00:26:27,770 But I'm going to go ahead and provide some problems for you to solve to kind of test yourself out like 319 00:26:27,770 --> 00:26:33,890 with how well, you know, recursion after this lecture and to help you push yourself a little bit and 320 00:26:33,890 --> 00:26:36,710 learn to solve recursive problems on your own. 321 00:26:36,980 --> 00:26:44,240 And we will be doing some problems with traversing data structures like a vector, so I wanted to introduce 322 00:26:44,240 --> 00:26:44,540 that. 323 00:26:45,140 --> 00:26:51,770 This is an entire program here if you want to type that into a text editor and run it. 324 00:26:52,820 --> 00:27:00,470 What we're doing is just declaring a vector right here and we are passing the vector itself and the 325 00:27:00,470 --> 00:27:06,440 last element of the vector by doing my vector size minus one up to our recursive function here. 326 00:27:07,430 --> 00:27:13,070 So this is the last element of the vector and the vector itself passed by reference, and we're just 327 00:27:13,070 --> 00:27:19,310 printing out the vector in reverse order, starting at the end and doing that in minus one thing that 328 00:27:19,310 --> 00:27:20,930 we've already seen with recursion. 329 00:27:21,990 --> 00:27:27,660 Here's our recursive call, and then our base case is, of course, when it is zero and you know this 330 00:27:27,660 --> 00:27:31,100 here is the first element of the vector so we can stop. 331 00:27:31,110 --> 00:27:32,370 It's just a void function. 332 00:27:32,380 --> 00:27:37,110 So we're just returning when in is at the first element of the vector. 333 00:27:37,800 --> 00:27:39,960 So you can just go ahead and test this out. 334 00:27:40,680 --> 00:27:44,040 It should print out five four three two one. 335 00:27:45,450 --> 00:27:47,610 Of course, on new lines because we have an in line. 336 00:27:48,330 --> 00:27:51,000 But I wanted to mention this as well. 337 00:27:51,510 --> 00:27:53,730 Just so you know you have. 338 00:27:55,360 --> 00:28:01,510 The knowledge that recursion is also used for traversing data structures and as we'll see later on, 339 00:28:01,510 --> 00:28:08,320 it is not just used two to first steal things like this, but we can also traverse things like link 340 00:28:08,320 --> 00:28:11,800 lists and another topic we'll get into, which is trees. 341 00:28:12,250 --> 00:28:20,650 So hopefully that explained everything, and I will go ahead and provide some problems that you can 342 00:28:20,650 --> 00:28:21,970 use to practice this. 343 00:28:22,390 --> 00:28:28,060 But of course, with the recursion and most other things as well, practice makes perfect. 344 00:28:28,060 --> 00:28:37,240 So go ahead and come up with some recursive functions that are kind of another way to solve things that 345 00:28:37,240 --> 00:28:38,530 you've done with loops. 346 00:28:38,860 --> 00:28:46,150 So think of something that you problem you solve by using while loops or for loops and see if you can 347 00:28:46,150 --> 00:28:49,720 transform that into a recursive solution. 348 00:28:50,020 --> 00:28:51,910 So something that requires repetition. 349 00:28:52,180 --> 00:28:53,950 Just some simple things. 350 00:28:54,880 --> 00:29:01,150 See if you can instead have a function, call itself and implement a recursive solution to it just so 351 00:29:01,150 --> 00:29:02,830 you can get some extra practice. 352 00:29:03,370 --> 00:29:03,820 All right. 353 00:29:04,090 --> 00:29:06,790 And with that, I will see you in the next lecture.