1 00:00:00,430 --> 00:00:02,560 Hey everyone, and welcome back. 2 00:00:02,860 --> 00:00:07,420 Over here we are starting with a new topic which is recursion. 3 00:00:07,420 --> 00:00:12,280 Now I have placed recursion right at the beginning part of this course. 4 00:00:12,280 --> 00:00:17,710 Because recursion is a very important topic for any coding interview. 5 00:00:17,710 --> 00:00:25,390 You will see that as you go on with this course, that recursion is in fact the parent of various other 6 00:00:25,390 --> 00:00:33,040 topics such as backtracking, dynamic programming, greedy algorithms, divide and conquer algorithms, 7 00:00:33,040 --> 00:00:33,760 etc.. 8 00:00:33,760 --> 00:00:37,390 Now more of that later in the course over here. 9 00:00:37,390 --> 00:00:42,370 Let's try to spend some time and understand recursion thoroughly. 10 00:00:42,370 --> 00:00:47,650 And then let's go ahead and take a look at a few interesting coding interview questions. 11 00:00:47,650 --> 00:00:49,120 So let's get started. 12 00:00:49,120 --> 00:00:55,300 Now these are the topics that we will be discussing over here to understand recursion thoroughly. 13 00:00:55,300 --> 00:00:57,130 So let's get started. 14 00:00:57,130 --> 00:01:00,910 The first question over here is what is recursion? 15 00:01:00,910 --> 00:01:10,690 Now in simple terms, recursion is just a function calling itself until a base condition or a terminating 16 00:01:10,690 --> 00:01:12,010 condition occurs. 17 00:01:12,160 --> 00:01:16,210 Let's take an example to understand what is written over here. 18 00:01:16,210 --> 00:01:20,620 Let's say you want to print the numbers from 1 to 5. 19 00:01:20,620 --> 00:01:28,750 And if we were to write the pseudo code for this one way, of course to do this would be by having five 20 00:01:28,750 --> 00:01:29,860 print statements. 21 00:01:29,860 --> 00:01:33,970 But of course this is not an optimal way for various reasons. 22 00:01:33,970 --> 00:01:37,960 For example, what if instead of five, you have 100 over here? 23 00:01:37,960 --> 00:01:42,850 And even worse, what if you don't know this and if it's just a variable? 24 00:01:43,690 --> 00:01:47,260 So we know that this is not an optimal approach. 25 00:01:47,260 --> 00:01:52,210 Another approach to handle this would be to use recursion. 26 00:01:52,210 --> 00:01:56,620 Now, if we were to write the pseudo code for this, it would look like this. 27 00:01:56,620 --> 00:01:58,000 You have a function. 28 00:01:58,000 --> 00:01:59,650 You can name it as you want. 29 00:01:59,650 --> 00:02:01,720 I've not given it any name over here. 30 00:02:01,720 --> 00:02:05,110 And you have the body of the function over here. 31 00:02:05,110 --> 00:02:08,590 And you call the function over here with a particular input. 32 00:02:08,590 --> 00:02:11,800 In this case we are calling the function with one. 33 00:02:11,800 --> 00:02:16,630 Now when you come over here, when the control comes to the function over here n is equal to one. 34 00:02:16,630 --> 00:02:21,670 And then inside you have a statement over here if n greater than five return. 35 00:02:21,670 --> 00:02:22,660 But n is one. 36 00:02:22,660 --> 00:02:24,850 So you don't execute this. 37 00:02:24,850 --> 00:02:27,370 You come over here and you print n. 38 00:02:27,370 --> 00:02:28,900 So n over here is one. 39 00:02:28,900 --> 00:02:30,340 So you print one. 40 00:02:30,340 --> 00:02:37,330 And then notice over here that inside the body of the function you are calling the function again recursively. 41 00:02:37,330 --> 00:02:40,360 So that's what is function calling itself. 42 00:02:40,360 --> 00:02:45,220 So over here we are calling the function again with a different input. 43 00:02:45,220 --> 00:02:50,470 And again you will see that many times it's about making the input smaller. 44 00:02:50,470 --> 00:02:59,290 Or a better way of saying that would be making the input closer to the base condition or the terminating 45 00:02:59,290 --> 00:02:59,920 condition. 46 00:02:59,920 --> 00:03:04,390 So over here we are calling the same function with one plus one which is two. 47 00:03:04,390 --> 00:03:08,470 And once you are inside the function again n is not greater than five. 48 00:03:08,470 --> 00:03:10,480 And we would be printing two. 49 00:03:10,480 --> 00:03:15,130 And we would again call the same function with three which is two plus one. 50 00:03:15,130 --> 00:03:21,880 So that's what we say function calling itself which is recursion in simple terms okay. 51 00:03:21,880 --> 00:03:29,830 And again remember a base condition is very important for any recursive um solution. 52 00:03:29,830 --> 00:03:34,840 Because if you don't have a base condition you would have created an infinite loop, right. 53 00:03:34,840 --> 00:03:42,130 So you need the function calling itself to stop at some point, which is the base condition or the terminating 54 00:03:42,130 --> 00:03:42,730 condition. 55 00:03:42,730 --> 00:03:49,540 Now in this case, because we just want to print up to five, if n becomes greater than five we can 56 00:03:49,540 --> 00:03:50,020 stop. 57 00:03:50,020 --> 00:03:51,850 So this is the base condition. 58 00:03:51,850 --> 00:03:57,670 And remember if you don't have a base condition you will get a stack overflow error. 59 00:03:57,670 --> 00:04:00,760 Because computers don't have unlimited memory. 60 00:04:00,760 --> 00:04:01,900 Memory is limited. 61 00:04:01,900 --> 00:04:07,180 So you would get a stack overflow error if you have no base condition. 62 00:04:07,180 --> 00:04:14,350 So we have seen that recursion is just a function calling itself, which is what we have over here until 63 00:04:14,350 --> 00:04:17,170 a base condition, which is what we have over here. 64 00:04:17,170 --> 00:04:20,950 So that's pretty much what recursion is in very simple terms. 65 00:04:20,950 --> 00:04:25,330 Now let's think of when to use recursion. 66 00:04:26,140 --> 00:04:36,460 If you have to solve a problem, and if you can see that the problem at hand can be divided into smaller 67 00:04:36,460 --> 00:04:37,570 subproblems. 68 00:04:37,570 --> 00:04:45,310 And if solving these subproblems can help you solve the original problem, then probably you should 69 00:04:45,310 --> 00:04:47,440 be using recursion now. 70 00:04:47,440 --> 00:04:55,810 It's also many times the case that these smaller subproblems would be of similar nature, or they would 71 00:04:55,810 --> 00:04:58,720 be similar to the original problem at hand. 72 00:04:58,720 --> 00:05:00,010 Now what do I mean with that? 73 00:05:00,380 --> 00:05:01,880 Let's take an example. 74 00:05:01,880 --> 00:05:07,070 Let's say you are given n and you want to find n factorial. 75 00:05:07,070 --> 00:05:15,680 Now, if your n is five five, factorial is nothing but five into four into three, up to one or n factorial 76 00:05:15,680 --> 00:05:20,480 is just n into n minus one, into n minus two, etc. up to one. 77 00:05:20,480 --> 00:05:27,770 Now if you want to find n factorial and you're given n or let's say for simplicity, let's say you want 78 00:05:27,770 --> 00:05:30,260 to find five factorial, okay? 79 00:05:30,260 --> 00:05:32,270 Or let's say n is equal to five. 80 00:05:32,270 --> 00:05:40,790 As an example, notice that if you can find the answer to a subproblem, let's say that's four factorial. 81 00:05:40,790 --> 00:05:47,210 Again, notice four is less than five and it's closer to the terminating condition or the base condition. 82 00:05:47,210 --> 00:05:54,860 So if you can find the answer to four factorial, you can find the answer to five factorial using the 83 00:05:54,860 --> 00:05:57,560 answer that you find which is four factorial. 84 00:05:57,560 --> 00:06:03,410 Because five factorial is equal to five into four factorial. 85 00:06:03,410 --> 00:06:09,890 And over here four factorial is the subproblem which is of similar nature to the original problem, 86 00:06:09,890 --> 00:06:15,140 and solving the subproblem helps us solve the original problem. 87 00:06:15,140 --> 00:06:17,390 So four factorial is 24. 88 00:06:17,870 --> 00:06:25,640 Now using this 24, we can find the original problem's answer, which is five factorial, because five 89 00:06:25,640 --> 00:06:29,630 factorial is equal to five into 24. 90 00:06:30,050 --> 00:06:38,330 So if the question at hand has these type of characteristics, then probably you can solve it using 91 00:06:38,330 --> 00:06:39,020 recursion. 92 00:06:39,020 --> 00:06:45,170 Now, I know that this is a lot of theory, but we will do a lot of practice questions and this will 93 00:06:45,170 --> 00:06:46,700 become second nature to you. 94 00:06:46,700 --> 00:06:48,200 So don't worry about that. 95 00:06:48,200 --> 00:06:51,770 But again, let's take it step by step and let's proceed. 96 00:06:51,770 --> 00:06:54,020 So we have seen what recursion is. 97 00:06:54,020 --> 00:06:58,040 And we have seen from a high level when to use recursion. 98 00:06:58,040 --> 00:07:05,090 Now let's take a look at the pseudocode of this, what we just now discussed over here for n factorial. 99 00:07:05,120 --> 00:07:11,030 To understand this in a better manner before we move ahead and try to visualize recursion. 100 00:07:11,030 --> 00:07:17,240 So if I were to write the pseudocode of what we just now discussed over here, let's say I have a function, 101 00:07:17,240 --> 00:07:21,110 you can call it factorial or anything to save space over here. 102 00:07:21,110 --> 00:07:22,910 I'm not writing any name for the function. 103 00:07:22,910 --> 00:07:28,070 And let's say we are calling the function with five because we want to find, let's say five factorial. 104 00:07:28,070 --> 00:07:36,410 Now inside the function we have the base condition or the terminating condition that if n is equal to 105 00:07:36,410 --> 00:07:43,940 one, just return one, because five factorial, as we discussed, is five into four into three into 106 00:07:43,940 --> 00:07:46,670 two into one, and then node is after one. 107 00:07:46,670 --> 00:07:48,020 You don't need to go further. 108 00:07:48,020 --> 00:07:51,410 So that's why if n is equal to one, return just one. 109 00:07:51,410 --> 00:07:58,010 And again we will discuss as we go ahead in this lecture how you can systematically think of coming 110 00:07:58,010 --> 00:07:59,240 up with the base condition. 111 00:07:59,240 --> 00:08:04,910 But for now, because this is a very simple question, it's intuitive that if n is equal to one, we 112 00:08:04,910 --> 00:08:05,990 can just return one. 113 00:08:05,990 --> 00:08:07,370 So that's what we have seen over here. 114 00:08:07,370 --> 00:08:09,530 So that's the base condition that we have. 115 00:08:09,740 --> 00:08:12,500 And what would be the recursive case. 116 00:08:12,950 --> 00:08:20,330 The recursive case would be if n is not equal to one we just need to make the input smaller or call 117 00:08:20,330 --> 00:08:27,800 the function again recursively by having the input closer to the base condition or the terminating condition. 118 00:08:27,800 --> 00:08:30,140 So that would be return. 119 00:08:30,140 --> 00:08:35,930 We could just return function n minus one into n, right. 120 00:08:35,930 --> 00:08:44,270 So if you want to find factorial five factorial we are just returning four factorial into n. 121 00:08:44,270 --> 00:08:45,830 So n in this case is five. 122 00:08:45,830 --> 00:08:49,820 So we have seen that five factorial is five into four factorial. 123 00:08:49,820 --> 00:08:56,090 So to get this four factorial, we are recursively calling the function again with the input as n minus 124 00:08:56,090 --> 00:08:56,540 one. 125 00:08:56,540 --> 00:09:01,820 And then to multiply this five over here we have n into this part over here. 126 00:09:01,820 --> 00:09:05,180 So this over here is the recursive case. 127 00:09:06,280 --> 00:09:13,390 So whenever you think of a recursive solution, always try to think of the base case and the recursive 128 00:09:13,390 --> 00:09:13,840 case. 129 00:09:13,840 --> 00:09:17,050 So we have discussed some interesting things over here. 130 00:09:17,200 --> 00:09:20,620 Now in the next video let's try to visualize this.