1 00:00:02,230 --> 00:00:02,980 Hello, everyone. 2 00:00:03,010 --> 00:00:05,590 So I hope you got the idea what is recursion? 3 00:00:05,920 --> 00:00:07,220 Recursion is awesome. 4 00:00:07,240 --> 00:00:12,550 Basically, it goes and says you want to find factorial and then find and minus one factorial first 5 00:00:12,550 --> 00:00:18,070 by calling the same function and then using the result of N minus one factorial properly calculate and 6 00:00:18,070 --> 00:00:18,640 factorial. 7 00:00:18,940 --> 00:00:23,490 OK, the best part of recursion is it makes problem solving very, very easy for us. 8 00:00:23,890 --> 00:00:25,990 We can find factorial iteratively. 9 00:00:25,990 --> 00:00:29,670 Also iteratively means using the four or devi loop. 10 00:00:29,890 --> 00:00:30,340 OK. 11 00:00:30,640 --> 00:00:32,830 Going forward we will not think like. 12 00:00:34,720 --> 00:00:41,020 Going forward, we will not think like Ford is calling three, three is calling to do is calling one 13 00:00:41,020 --> 00:00:41,620 Anton. 14 00:00:41,950 --> 00:00:47,800 The biggest problem of is people generally try to go in depth and then they face many problems and then 15 00:00:47,800 --> 00:00:48,730 they got confused. 16 00:00:49,190 --> 00:00:52,900 So to avoid that, let's look at the principle behind recursion. 17 00:00:53,110 --> 00:00:55,110 OK, let's see how it works. 18 00:00:55,360 --> 00:01:01,630 So recursion works on a principle that you guys have already studied and that principle is being my 19 00:01:02,170 --> 00:01:04,599 principle of mathematical induction. 20 00:01:05,230 --> 00:01:07,410 OK, so what is PMI? 21 00:01:07,720 --> 00:01:10,560 So PMI was used to prove fact. 22 00:01:11,110 --> 00:01:12,410 Let us take an example. 23 00:01:12,460 --> 00:01:19,870 OK, so suppose there is a function F so function F is through. 24 00:01:21,840 --> 00:01:25,930 For all natural numbers, OK, so this is an example. 25 00:01:25,990 --> 00:01:29,450 So what PMI will do, BMI prove it in three steps. 26 00:01:29,490 --> 00:01:33,740 OK, so there are three steps, so step one and step one. 27 00:01:33,750 --> 00:01:34,500 But we will do. 28 00:01:34,500 --> 00:01:35,370 We will prove. 29 00:01:37,200 --> 00:01:39,460 That F of zero or F of one is true. 30 00:01:40,290 --> 00:01:42,270 So this is the first step of BMI. 31 00:01:42,570 --> 00:01:45,880 OK, BMI proves anything and effect in three steps. 32 00:01:46,080 --> 00:01:48,930 So the first step is proof of 051 is true. 33 00:01:50,610 --> 00:01:57,030 OK, so this means we can start with a very small number and prove that generally it's a very trivial 34 00:01:57,030 --> 00:01:57,490 problem. 35 00:01:57,510 --> 00:01:59,460 OK, simply just put the value. 36 00:02:00,450 --> 00:02:02,290 OK, we will also take an example. 37 00:02:02,700 --> 00:02:06,420 So this step is actually called Biscuit's. 38 00:02:08,289 --> 00:02:14,380 Now, the second step of BMI is in the second step, what we will do, the name of the second step is 39 00:02:14,800 --> 00:02:16,180 induction hypotheses. 40 00:02:18,520 --> 00:02:23,530 So induction hypotheses, what we will do, we will assume, OK? 41 00:02:24,770 --> 00:02:29,070 So what we will assume so, first of all, we have to assume you do not question it, OK? 42 00:02:29,090 --> 00:02:30,120 Please don't question it. 43 00:02:30,140 --> 00:02:31,640 We will always assume something. 44 00:02:32,130 --> 00:02:37,220 So we are assuming we are assuming that FFG is true. 45 00:02:38,700 --> 00:02:41,430 Workers are generally OK for any general. 46 00:02:42,810 --> 00:02:47,640 Now, the third step of that third step of BMI is induction step. 47 00:02:48,960 --> 00:02:51,180 OK, induction step. 48 00:02:51,980 --> 00:02:54,440 So introduction step where people do. 49 00:02:55,680 --> 00:03:02,760 Generally, in an action step, what we do is using the tool, so I'm writing here using step stepto. 50 00:03:04,200 --> 00:03:07,990 Using Stepto, we will prove using Stepto. 51 00:03:08,010 --> 00:03:11,130 We will try to prove that FFG plus one is true. 52 00:03:13,710 --> 00:03:20,850 OK, so we have to prove two things, this one and this one, we have to prove based case and we have 53 00:03:20,850 --> 00:03:22,140 to prove induction step. 54 00:03:22,590 --> 00:03:24,330 OK, we can assume this one. 55 00:03:25,400 --> 00:03:26,720 We can assume step stepto. 56 00:03:29,320 --> 00:03:32,270 OK, we can assume step two, it is our hypothesis. 57 00:03:32,290 --> 00:03:38,050 We do not have to worry about this, but we have to prove step one and we have to prove step three. 58 00:03:38,560 --> 00:03:41,080 Step two, we can assume and please do not question it. 59 00:03:41,340 --> 00:03:46,890 OK, so let us take an example and then we will solve that example with the help of FEMA. 60 00:03:47,570 --> 00:03:47,980 OK. 61 00:03:49,940 --> 00:03:53,030 So let's solve this very simple example. 62 00:03:54,000 --> 00:03:55,530 So, Sigmon. 63 00:03:56,440 --> 00:04:02,650 What is Sigmon segment basically means some of us to an natural number and there's a formula and in 64 00:04:02,650 --> 00:04:05,400 doing plus one, why do some of us aren't natural? 65 00:04:05,410 --> 00:04:05,710 No. 66 00:04:06,070 --> 00:04:07,530 Now, let's apply BMI. 67 00:04:07,900 --> 00:04:11,110 So in BMI, first step is the best case. 68 00:04:11,380 --> 00:04:15,170 In the best case, what we will do, we will solve a very small problem. 69 00:04:15,670 --> 00:04:19,120 So first step case. 70 00:04:21,630 --> 00:04:23,980 So in this case, a four zero. 71 00:04:24,240 --> 00:04:25,330 So what is above zero? 72 00:04:25,350 --> 00:04:29,160 So Sigma Zero is basically some of zero actual number. 73 00:04:29,160 --> 00:04:31,060 First to zero, national debt will be zero. 74 00:04:31,410 --> 00:04:32,980 So this is our largest. 75 00:04:33,810 --> 00:04:35,590 Now let's calculate averages. 76 00:04:36,270 --> 00:04:39,560 So for our riches, this is our formula. 77 00:04:39,570 --> 00:04:43,160 And now let us try to put an equal zero and equals zero here. 78 00:04:43,170 --> 00:04:46,240 So zero and two zero plus one by two. 79 00:04:46,260 --> 00:04:47,940 So this is this is zero. 80 00:04:47,970 --> 00:04:49,620 OK, so this is averages. 81 00:04:49,800 --> 00:04:51,540 So energises outages. 82 00:04:52,020 --> 00:04:54,910 So we proved the base case, OK. 83 00:04:55,170 --> 00:04:56,580 So we have proved four zero. 84 00:04:56,850 --> 00:04:58,230 We can also prove it for one. 85 00:04:58,950 --> 00:05:01,050 So now let us also provide for one. 86 00:05:01,090 --> 00:05:05,080 So one so sigma one will be some of first an actual number. 87 00:05:05,100 --> 00:05:05,980 It will be one only. 88 00:05:06,000 --> 00:05:14,220 So this is our energies and our our averages will be so around 12 percent Birtwhistle one one plus one 89 00:05:14,220 --> 00:05:14,770 by two. 90 00:05:15,030 --> 00:05:17,300 So this is two by two and this is one. 91 00:05:17,940 --> 00:05:19,470 And this is our averages. 92 00:05:19,470 --> 00:05:21,360 So this is outages. 93 00:05:21,570 --> 00:05:23,490 Hence we have proved our base case. 94 00:05:23,520 --> 00:05:23,910 OK. 95 00:05:25,410 --> 00:05:31,290 Our best guess is ready now, now the second step, the second step is induction hypothesis. 96 00:05:31,320 --> 00:05:35,250 OK, so our second step is induction hypotheses. 97 00:05:36,060 --> 00:05:38,120 So in induction, I put it, this is what we will do. 98 00:05:38,130 --> 00:05:39,000 We will assume. 99 00:05:39,000 --> 00:05:39,780 I can assume. 100 00:05:40,080 --> 00:05:46,890 So what I'm assuming here, I'm assuming Sigma K is going to Cabletron by two. 101 00:05:47,220 --> 00:05:48,400 Please do not question it. 102 00:05:48,570 --> 00:05:51,590 I am assuming we just have to assume so what. 103 00:05:51,600 --> 00:05:55,980 I'm assuming Sigma Sigma equals Cabelas and Mitu is true. 104 00:05:57,700 --> 00:06:00,570 I am assuming this thing is true, OK? 105 00:06:01,780 --> 00:06:03,230 So this is our mission. 106 00:06:03,340 --> 00:06:06,030 OK, don't worry about it and please do not question this. 107 00:06:06,460 --> 00:06:07,390 Now, the third step. 108 00:06:09,090 --> 00:06:15,900 The third step is induction step, so in induction step, what we have to do, we have to prove we have 109 00:06:15,900 --> 00:06:17,160 to prove what plus one. 110 00:06:17,160 --> 00:06:20,850 So we have to prove that Sigma K plus one. 111 00:06:21,150 --> 00:06:23,110 This is for the value. 112 00:06:23,460 --> 00:06:24,690 So what we will do, we are. 113 00:06:25,660 --> 00:06:27,580 We will put an equal K plus one. 114 00:06:27,610 --> 00:06:29,990 OK, here we will put an equal shaped lesson. 115 00:06:30,310 --> 00:06:35,700 So listen, this will become Gabler's two by two, OK? 116 00:06:35,710 --> 00:06:38,710 So we have to prove this Sigma plus. 117 00:06:40,670 --> 00:06:45,590 Segment gave listeners keep listening to Cabelas two by two now let us prove this. 118 00:06:45,980 --> 00:06:47,550 So what is this? 119 00:06:47,570 --> 00:06:48,890 We are solving allergies. 120 00:06:48,920 --> 00:06:49,330 OK. 121 00:06:50,740 --> 00:06:55,030 So Sigma K plus one, so can I write like this K plus one? 122 00:06:55,960 --> 00:06:59,200 Plus, sick monkey, I can write it like this. 123 00:06:59,920 --> 00:07:02,230 This is basically cape lesson. 124 00:07:02,560 --> 00:07:04,180 So what is the value of the monkey? 125 00:07:05,250 --> 00:07:07,500 So we can take the value of sigma market from here. 126 00:07:09,200 --> 00:07:12,180 OK, so let's put the value of Sigma. 127 00:07:12,390 --> 00:07:18,140 So this is going to a plus one by two, OK? 128 00:07:18,770 --> 00:07:23,380 Now what we can do can multiply and divide by two here. 129 00:07:23,570 --> 00:07:24,400 Yes, I can. 130 00:07:24,980 --> 00:07:26,840 Then what I will do, take Gabe. 131 00:07:26,860 --> 00:07:28,090 Listen to his comment. 132 00:07:28,430 --> 00:07:37,550 OK, I am taking K plus one by two is common so we have two plus K so this is our allergist's and now. 133 00:07:38,760 --> 00:07:42,810 Our allergies and allergies are equal, so allergies equals outages. 134 00:07:44,510 --> 00:07:48,710 OK, so we have proved our third step, which is the induction step. 135 00:07:49,010 --> 00:07:54,350 OK, so we have proved the base case, we have proved the induction step and we have assumed our induction 136 00:07:54,350 --> 00:07:55,010 hypothesis. 137 00:07:55,280 --> 00:08:00,050 Hence we proved that Sigma is added to in person by two. 138 00:08:01,020 --> 00:08:03,930 OK, so proved has proved. 139 00:08:05,610 --> 00:08:10,350 OK, so why it works, OK, how does it prove something? 140 00:08:10,770 --> 00:08:16,020 So there is a very simple and awesome intuition behind this and what the intuition is. 141 00:08:16,230 --> 00:08:20,160 So the intelligence is we have told you the starting position. 142 00:08:20,160 --> 00:08:21,540 We have told you the base. 143 00:08:22,170 --> 00:08:26,430 We have taught you how to take next step from one step. 144 00:08:26,940 --> 00:08:31,890 Now, from the base, from the base, we can use this thing. 145 00:08:32,940 --> 00:08:41,280 To go to the next step, to go to one step ahead, and then we can prove this step and then we can go 146 00:08:41,280 --> 00:08:46,470 to the next step, then we can prove this step and then we can go to the next step and so on. 147 00:08:47,250 --> 00:08:50,080 OK, so this was the basic condition. 148 00:08:50,340 --> 00:08:51,980 Now let's see some math also. 149 00:08:52,230 --> 00:08:54,330 OK, let's see some math also. 150 00:08:55,830 --> 00:08:59,910 So what we have done here is so if K equals zero. 151 00:09:01,330 --> 00:09:05,870 So game means basically and only so if N equals zero. 152 00:09:05,920 --> 00:09:08,410 So this we have proved this was our base. 153 00:09:09,670 --> 00:09:12,970 We have proved four and equals zero, so this we have proved. 154 00:09:14,390 --> 00:09:17,800 OK, now the second step, which was the induction hypothesis. 155 00:09:18,500 --> 00:09:23,240 OK, so inside the induction, I put this step if Gaikwad zero, what did I assume? 156 00:09:23,240 --> 00:09:25,100 I assume that is true. 157 00:09:28,010 --> 00:09:32,330 Now, this now this thing we assumed in the election, I put to this step, but what I am saying here 158 00:09:32,330 --> 00:09:37,440 is the value of zero, OK, the value of Kizito inside the index. 159 00:09:37,460 --> 00:09:38,420 And I put this step. 160 00:09:38,600 --> 00:09:40,430 So that means of zero is true. 161 00:09:42,670 --> 00:09:46,030 So first of all, this is not assumption, this we have proved. 162 00:09:47,360 --> 00:09:52,670 OK, this we have proven the base case, this is not our inception, if zero is true, this is not an 163 00:09:52,680 --> 00:09:53,030 assumption. 164 00:09:53,040 --> 00:09:53,720 This is a fact. 165 00:09:54,740 --> 00:09:56,770 OK, I'm not assuming anything here. 166 00:09:57,050 --> 00:09:59,390 We have already proved this in our best case. 167 00:10:00,050 --> 00:10:03,320 Now, the next step inside the next step. 168 00:10:03,540 --> 00:10:04,460 What did I proved? 169 00:10:04,460 --> 00:10:09,230 I proved that if it was true, then FFG plus one is also true. 170 00:10:10,460 --> 00:10:12,950 This thing I approved for attorney general. 171 00:10:13,340 --> 00:10:16,350 OK, I have proved this thing for any general. 172 00:10:17,150 --> 00:10:21,200 If it is true, then F of K plus one is also true. 173 00:10:21,500 --> 00:10:23,030 Now the value of K zero. 174 00:10:24,110 --> 00:10:29,350 So far, zero is true, that means using the index step of one is also true. 175 00:10:31,050 --> 00:10:34,170 OK, because we have proved this for a general. 176 00:10:34,890 --> 00:10:38,730 Now, if one is true, then of two is also true. 177 00:10:40,340 --> 00:10:47,420 Using the induction step, if true is true, then that is also true, then it is also true, then FIFA 178 00:10:47,420 --> 00:10:49,940 is also true and this way we can go up to end. 179 00:10:50,390 --> 00:10:59,060 OK, so finally, what we can right here, we can write FSN is true and we have to prove this only. 180 00:10:59,060 --> 00:11:00,530 So we have proved in this way. 181 00:11:01,640 --> 00:11:08,490 OK, so we came here to using when using do we go to try using three, we go to four and so on. 182 00:11:08,990 --> 00:11:14,780 So in every occasion problem you have to think like this only, OK, in every occasion problem you have 183 00:11:14,780 --> 00:11:17,570 to think you are applying BMI to prove a term. 184 00:11:17,970 --> 00:11:20,230 I'm repeating myself in every occasion problem. 185 00:11:20,240 --> 00:11:23,960 What we will do, we will think that we are applying BMI to prove a theorem. 186 00:11:24,210 --> 00:11:30,020 OK, so first of all, in every occasion problem, but we have to do to solve any problem, we have 187 00:11:30,020 --> 00:11:31,270 to do three simple things. 188 00:11:32,150 --> 00:11:36,550 So the first thing is we will think we will we have to think about the best case. 189 00:11:36,940 --> 00:11:38,240 OK, very simple case. 190 00:11:38,240 --> 00:11:39,740 We have to think about the best case. 191 00:11:40,660 --> 00:11:46,900 Now, the second thing is, I don't have to worry for the smaller problem, OK, in the second step. 192 00:11:46,930 --> 00:11:53,170 We don't have to worry for the smaller problem if I have to work for and then I'm going to assume it 193 00:11:53,170 --> 00:11:54,430 works for and minus one. 194 00:11:54,850 --> 00:11:57,640 So assume you have a solution for the smaller problem. 195 00:11:57,880 --> 00:12:00,420 Solution assumes smaller problem solutions already. 196 00:12:00,430 --> 00:12:04,020 Did you just have to use their solution to solve the bigger problem? 197 00:12:04,210 --> 00:12:10,240 If I'm able to do that, then be a mice's your Cordwell work permit guarantees that your code will work 198 00:12:10,600 --> 00:12:11,080 OK. 199 00:12:11,200 --> 00:12:15,820 And I will not think all this like fact for is calling three. 200 00:12:16,210 --> 00:12:17,620 Three is calling to on. 201 00:12:17,770 --> 00:12:26,260 OK, I will not take all this so we will directly think for an OK, we will directly thank for N because 202 00:12:26,260 --> 00:12:28,420 we will assume we have and minus one. 203 00:12:28,810 --> 00:12:31,960 Now using that assumption I need to propolis all 14. 204 00:12:32,380 --> 00:12:35,200 OK, so let's write factorial and again. 205 00:12:35,560 --> 00:12:38,980 But this time we will think in terms of PMI, ok. 206 00:12:40,860 --> 00:12:46,650 So I am writing factual function again, but this time we will think Orlin p.m. items. 207 00:12:47,950 --> 00:12:54,910 So first of all, what the return type that will be under the name of the function is Vectorial fact, 208 00:12:55,300 --> 00:12:57,370 it will take our indigenous input. 209 00:12:57,790 --> 00:13:01,710 Now, the first step of an education problem, thinking payment items only. 210 00:13:01,720 --> 00:13:03,820 OK, what is the first step? 211 00:13:04,090 --> 00:13:05,890 The first step is the best case. 212 00:13:06,430 --> 00:13:07,540 Very small problem. 213 00:13:08,470 --> 00:13:17,310 So you can take so if any equals zero, what is a factual four zero factual answer is one zero, factual 214 00:13:17,320 --> 00:13:17,650 is one. 215 00:13:17,800 --> 00:13:19,780 You can also write for one on one also. 216 00:13:19,800 --> 00:13:21,890 OK, if I equals one, then also return one. 217 00:13:22,300 --> 00:13:23,250 So let's have a tweet. 218 00:13:23,530 --> 00:13:25,010 So our best is ready. 219 00:13:25,450 --> 00:13:29,440 Now, what we have to do is take a step of PMI is induction hypotheses. 220 00:13:29,440 --> 00:13:32,350 You have to assume so I am assuming. 221 00:13:34,320 --> 00:13:37,080 Then I have my answer for 10 minus one. 222 00:13:39,080 --> 00:13:44,450 OK, so this is our assumption, no, please do not question this, OK, so this is assumption. 223 00:13:46,000 --> 00:13:52,210 OK, so suppose this function for both function works, so I'm giving the function a smaller input, 224 00:13:52,340 --> 00:13:53,590 it will give me the answer. 225 00:13:53,680 --> 00:13:55,600 OK, do not question this line. 226 00:13:55,770 --> 00:13:57,880 OK, please do not question this line. 227 00:13:58,090 --> 00:13:59,260 You have to assume this. 228 00:13:59,290 --> 00:14:01,590 OK, so this is our assumption. 229 00:14:01,600 --> 00:14:03,550 It is also called the recursive case. 230 00:14:06,880 --> 00:14:13,720 OK, now what we have to do, we have the answer for and minus factorial, now we have to properly calculate 231 00:14:13,720 --> 00:14:15,160 the answer for and factorial. 232 00:14:15,170 --> 00:14:17,350 So this will be and multiply. 233 00:14:19,120 --> 00:14:20,740 And multiply, Smolan said. 234 00:14:21,900 --> 00:14:26,640 OK, we have to properly calculate, OK, so this is our third step. 235 00:14:28,820 --> 00:14:33,530 This was the third step of the third step for solving any immigration problem. 236 00:14:33,580 --> 00:14:33,830 OK. 237 00:14:34,790 --> 00:14:35,990 This was the second step. 238 00:14:39,860 --> 00:14:41,510 And this was the first to step. 239 00:14:44,250 --> 00:14:50,130 So first step is basically the second step is assumption, which is also called recursive case, and 240 00:14:50,130 --> 00:14:51,810 that third step is the calculation. 241 00:14:52,930 --> 00:14:55,000 OK, so third step is. 242 00:14:57,710 --> 00:14:58,430 Calculation. 243 00:14:59,740 --> 00:15:02,650 Now we have our own sanity and we can do it on our own set. 244 00:15:03,660 --> 00:15:08,040 OK, now let's call this function so called. 245 00:15:10,430 --> 00:15:11,300 Federal food. 246 00:15:14,100 --> 00:15:17,420 OK, let's go now file, let's read the good. 247 00:15:19,320 --> 00:15:23,170 So output is 24 for Vectorial, and of course, our goal is working. 248 00:15:23,460 --> 00:15:26,850 Now see here we are not thinking like Ford is three. 249 00:15:26,850 --> 00:15:30,020 Three is calling to do is calling when we are not going in depth. 250 00:15:30,210 --> 00:15:32,750 OK, think only in terms of PMI. 251 00:15:33,270 --> 00:15:34,970 Remember to step first step. 252 00:15:35,190 --> 00:15:36,300 Simple, very simple. 253 00:15:36,300 --> 00:15:39,600 Biscuit's second step assumption, which is the recursive keys. 254 00:15:39,900 --> 00:15:41,490 Third step is the calculation. 255 00:15:41,680 --> 00:15:46,820 OK, you have the answer for the smaller problem now with the help of the answer of the smaller problem, 256 00:15:46,830 --> 00:15:49,750 calculate the big answer and then return the big answer. 257 00:15:49,940 --> 00:15:51,380 OK, simple enough. 258 00:15:51,900 --> 00:15:53,340 So there are three steps. 259 00:15:53,580 --> 00:15:54,780 First is the best case. 260 00:15:54,780 --> 00:15:57,670 Second is assume it will work for the smaller problem. 261 00:15:57,810 --> 00:16:01,470 OK, third step is properly called for the bigger problem. 262 00:16:01,830 --> 00:16:03,380 Three simple steps I am repeating. 263 00:16:04,050 --> 00:16:05,190 First base case. 264 00:16:05,220 --> 00:16:07,920 Second, assume it will work for this problem. 265 00:16:07,950 --> 00:16:10,520 Third, properly called for the bigger problem. 266 00:16:10,860 --> 00:16:11,310 OK. 267 00:16:11,640 --> 00:16:12,570 This is very simple. 268 00:16:12,570 --> 00:16:12,870 Called. 269 00:16:13,970 --> 00:16:15,260 OK, thank you.