1 00:00:01,020 --> 00:00:08,250 Every recursive function needs to have something called a base case or a stop point. 2 00:00:09,340 --> 00:00:16,380 Remember my example at the beginning where I showed you how to recursively check out all the folders 3 00:00:16,890 --> 00:00:19,290 in one of our projects. 4 00:00:20,620 --> 00:00:27,880 We have to tell the program, hey, if the subfolder we're going to no longer has any more folder's 5 00:00:28,210 --> 00:00:33,250 stop, if this stop wasn't there, the function would just keep running. 6 00:00:33,850 --> 00:00:36,280 So recursive functions have two paths. 7 00:00:37,480 --> 00:00:45,880 One is the recursive case that is called a function again and run it, and then the base case that is 8 00:00:45,880 --> 00:00:49,000 stop calling the function, there's nothing more to search. 9 00:00:49,950 --> 00:00:55,950 So how can we add this feature of telling the function, hey, quit it, you're being ridiculous right 10 00:00:55,950 --> 00:00:57,100 now, you need to stop? 11 00:00:57,750 --> 00:01:00,350 Well, we can do something like this. 12 00:01:00,960 --> 00:01:04,350 We can create a counter and we'll say this counter is zero. 13 00:01:06,840 --> 00:01:14,040 And we can add a conditional statement will say that if counter is. 14 00:01:15,520 --> 00:01:16,900 Greater than three. 15 00:01:17,990 --> 00:01:21,230 In that case, just return done. 16 00:01:24,360 --> 00:01:29,940 Otherwise, we'll call Inception, but we also want to increment the counter by one. 17 00:01:31,310 --> 00:01:37,850 So if I click run here, well, I have to call the function first, let's say Inception. 18 00:01:38,850 --> 00:01:42,000 If I call this function right now. 19 00:01:43,100 --> 00:01:44,180 What do you think will happen? 20 00:01:45,180 --> 00:01:46,140 Pause a video. 21 00:01:46,290 --> 00:01:51,090 Think about it, because I'm about to click run and three to one. 22 00:01:54,470 --> 00:01:58,580 I get undefined, is that what you expected? 23 00:02:00,320 --> 00:02:07,430 Just to show you something, if I comment this code out and we just do this inception where we just 24 00:02:07,430 --> 00:02:15,080 keep calling it ception inception and perhaps do a console dialogue here saying hello. 25 00:02:19,310 --> 00:02:22,340 I get maximum call stack size exceeded. 26 00:02:23,890 --> 00:02:30,040 OK, we know by looking at this function, this version of the function, that it's never going to get 27 00:02:30,040 --> 00:02:36,160 to console Dahlborg because as soon as it hits the first line of the function, it's going to go back 28 00:02:36,160 --> 00:02:40,750 and say, oh, I'm calling this, and then it's going to go here is just going to bounce back and forth, 29 00:02:40,750 --> 00:02:43,020 back and forth, never getting to console a lot. 30 00:02:43,510 --> 00:02:49,600 But if we go back to what we have before, well, our function clearly has ended. 31 00:02:49,930 --> 00:02:52,750 It hasn't done stack overflow. 32 00:02:53,680 --> 00:02:57,460 And at one point it's ended because we increment the counter. 33 00:02:58,830 --> 00:03:02,970 So let me console dialogue here, our counter. 34 00:03:03,880 --> 00:03:10,540 And make sure that this works, if I click run, I get zero one, two, three, four. 35 00:03:11,050 --> 00:03:14,880 When it gets to four, counter is greater than three. 36 00:03:15,370 --> 00:03:17,020 So we're returning done. 37 00:03:17,620 --> 00:03:20,530 But why is there no done here? 38 00:03:22,110 --> 00:03:28,170 And this is a great illustration of how recursion works, I'm going to copy this code. 39 00:03:31,170 --> 00:03:33,660 And go back to our browser over here. 40 00:03:34,650 --> 00:03:37,620 Let me refresh this page to make sure that. 41 00:03:38,660 --> 00:03:46,070 We have a clear global variable and I'm going to copy and paste Inception this time around, I'm going 42 00:03:46,070 --> 00:03:53,540 to add the debugger keyboard so that we can debug our code and go step by step through it. 43 00:03:55,290 --> 00:03:57,000 Let's run Inception. 44 00:03:58,850 --> 00:03:59,810 And see what happens. 45 00:04:00,620 --> 00:04:03,410 All right, we're back to our debugger. 46 00:04:04,670 --> 00:04:09,440 We see that we have the call stack here, Inception has just been called by me. 47 00:04:10,540 --> 00:04:17,290 And I also opened up this little tab called Scope for our case, we want to just open up the script 48 00:04:17,470 --> 00:04:17,980 scope. 49 00:04:19,840 --> 00:04:27,310 It shows us what variables we have available to us in this case, we have counter, which is zero. 50 00:04:28,560 --> 00:04:30,390 So I'm going to click step over. 51 00:04:31,470 --> 00:04:37,570 And it's going to say, hey, we have counter is equal to zero, is that greater than three? 52 00:04:38,080 --> 00:04:42,270 No, I'm going to skip over incremented counter and run Inception. 53 00:04:43,770 --> 00:04:45,030 We see that that's happened. 54 00:04:45,970 --> 00:04:51,970 Counter has now been incremented because we've gone through this line and now we go to Inception, we're 55 00:04:51,970 --> 00:04:56,110 going to run the function again and you'll notice that the call stack when I click this is going to 56 00:04:56,110 --> 00:04:56,500 increase. 57 00:04:59,310 --> 00:05:04,110 And we're going to go one more time, Connery's, not one nope, don't return anything yet. 58 00:05:04,290 --> 00:05:09,300 Increment a counter you'll see of goes to two and we're going to run Inception again. 59 00:05:10,470 --> 00:05:12,050 And we keep going once more. 60 00:05:13,310 --> 00:05:20,150 Passing through counter becomes three, adding inception to the stack and then one more time. 61 00:05:21,200 --> 00:05:27,230 Three is not greater than three, so we go one more time calling Inception, adding it to the stack, 62 00:05:27,500 --> 00:05:32,870 we now have these many stacks counters at four and then we step over here. 63 00:05:33,890 --> 00:05:41,500 Counter is now four, which is greater than three, we're finally going to enter the if condition that's 64 00:05:41,500 --> 00:05:43,160 going to return done for us. 65 00:05:43,210 --> 00:05:44,190 Let's see what happens here. 66 00:05:44,590 --> 00:05:46,360 I'm going to click next. 67 00:05:48,510 --> 00:05:50,400 And I click next again. 68 00:05:52,230 --> 00:05:58,140 Look at that, we have a local variable now that has return value done. 69 00:06:00,480 --> 00:06:02,910 We've now returned, done. 70 00:06:04,480 --> 00:06:06,970 And we're no longer going to call Inception. 71 00:06:07,950 --> 00:06:14,850 The call stack is now going to start popping off these functions because it's going to say, oh, we 72 00:06:14,850 --> 00:06:21,450 have a return, key word, I'm going to stop whatever I'm doing at the bottom here and return from this 73 00:06:21,450 --> 00:06:21,840 function. 74 00:06:21,990 --> 00:06:25,470 So this inception function is going to get return done. 75 00:06:26,410 --> 00:06:27,840 But notice what happens next. 76 00:06:31,000 --> 00:06:38,890 Oh, I get return value undefined as we popped off the top item from Inception from the call stack and 77 00:06:38,890 --> 00:06:42,160 if I keep popping things from the call stack. 78 00:06:43,610 --> 00:06:47,000 The return value is undefined, and that's why we get. 79 00:06:48,730 --> 00:06:50,320 Now, why is that? 80 00:06:51,160 --> 00:06:57,190 Well, if we go back to our function, what you just saw was us essentially doing this. 81 00:06:58,000 --> 00:07:01,090 We called Inception once. 82 00:07:05,040 --> 00:07:05,760 Three times. 83 00:07:06,870 --> 00:07:07,980 And then four times. 84 00:07:11,600 --> 00:07:19,070 And within here, when we finally got here, we said, oh, return done so this inception function turns 85 00:07:19,070 --> 00:07:20,420 into done. 86 00:07:22,950 --> 00:07:25,380 And then we go to this function. 87 00:07:27,310 --> 00:07:33,340 Now, the problem with this, and I know this can get confusing, is that once we've returned, once 88 00:07:33,910 --> 00:07:40,930 we've popped off the stack and we're now at this part of inception, but this interception never returns 89 00:07:40,930 --> 00:07:41,410 anything. 90 00:07:41,770 --> 00:07:45,780 When a function doesn't return anything, it just returns undefined. 91 00:07:46,210 --> 00:07:53,080 So we need to keep telling it to return this done and and bubble it up towards the very end. 92 00:07:53,710 --> 00:07:57,130 And this is something that you have to keep in mind with recursion. 93 00:07:58,360 --> 00:08:05,980 There's usually a base case, and you always want to make sure you return so that the value that you 94 00:08:05,980 --> 00:08:09,330 want gets bubbled up all the way to the top. 95 00:08:09,790 --> 00:08:14,890 In our case, all we need to do is say return inception. 96 00:08:15,580 --> 00:08:22,660 This way, this inception knows to return whatever its result was which was done, and this inception 97 00:08:22,660 --> 00:08:28,600 knows to result, to return, whatever this result was, which again is done and so on and so forth 98 00:08:28,600 --> 00:08:30,700 until we get Don back. 99 00:08:31,490 --> 00:08:32,950 Let's run this again. 100 00:08:34,870 --> 00:08:36,790 Or and I have to call the function. 101 00:08:36,940 --> 00:08:38,680 Let's do that again, Inception. 102 00:08:42,070 --> 00:08:46,990 And we're done very, very nice if I go back here. 103 00:08:48,180 --> 00:08:54,450 And go back to the council, I encourage you to try this out this time, adding the return keyword to 104 00:08:54,450 --> 00:08:58,590 Inception and running through the debugger to see what happens. 105 00:08:59,910 --> 00:09:06,590 But what I just showed you is all you need to build recursive functions, you have three rules. 106 00:09:07,080 --> 00:09:11,640 One is to identify the base case. 107 00:09:13,480 --> 00:09:19,360 Two is to identify the recursive case. 108 00:09:21,400 --> 00:09:28,810 So we've identified the base case went to stop the recursive case, that is when Connor is less than 109 00:09:28,810 --> 00:09:29,140 three. 110 00:09:30,070 --> 00:09:36,390 And then finally, our third step is to get closer and closer. 111 00:09:37,700 --> 00:09:43,430 And return when needed, and that usually. 112 00:09:45,150 --> 00:09:48,740 You have to returns. 113 00:09:52,610 --> 00:09:57,520 For the base case and the recursive case, because you want to return something at the end of the function, 114 00:09:58,340 --> 00:10:00,110 so let's comment this out. 115 00:10:00,890 --> 00:10:03,190 We have an idea of how recursion works. 116 00:10:03,980 --> 00:10:09,380 The function simply gets closer and closer and closer to the base case. 117 00:10:09,620 --> 00:10:15,770 And once it gets to the base case, it finally returns and pops functions off the stack. 118 00:10:16,550 --> 00:10:17,990 But that's enough talking for me. 119 00:10:18,230 --> 00:10:23,990 I think it's time for us to do some coding exercises to get really familiar with this topic. 120 00:10:24,420 --> 00:10:26,480 I'll see in the next one by.