1 00:00:02,290 --> 00:00:02,980 Hello everyone. 2 00:00:03,010 --> 00:00:04,630 So I hope you get the idea. 3 00:00:04,630 --> 00:00:07,240 What is recursion recursion is awesome. 4 00:00:07,240 --> 00:00:08,950 Basically we go Genesis. 5 00:00:08,980 --> 00:00:14,170 You want to find factual and then find and minus one factorial first by calling the same function and 6 00:00:14,170 --> 00:00:18,950 then using the result of and minus one factoid properly calculate and factorial. 7 00:00:19,050 --> 00:00:19,620 Okay. 8 00:00:19,630 --> 00:00:23,880 The best part of recursion is it makes problem solving very very easy for us. 9 00:00:23,980 --> 00:00:26,820 We can find factorial identically also. 10 00:00:26,860 --> 00:00:30,010 I literally means using the four or Devi loop. 11 00:00:30,010 --> 00:00:30,700 Okay. 12 00:00:30,700 --> 00:00:39,220 Going forward we will not think like going forward we will not think like four is calling three threes 13 00:00:39,250 --> 00:00:41,990 calling to do is calling 1 and so on. 14 00:00:42,010 --> 00:00:47,440 The biggest problem with recursion is people generally try to go in depth and then they face many problems 15 00:00:47,440 --> 00:00:49,240 and then they got confused. 16 00:00:49,240 --> 00:00:53,130 So to avoid that let's look at the principle behind recursion. 17 00:00:53,170 --> 00:00:55,380 Okay let's see how it goes in books. 18 00:00:55,420 --> 00:01:01,670 So recursion works on a principle that you guys have already started and that principle is being my 19 00:01:02,200 --> 00:01:05,250 principle of mathematical induction. 20 00:01:05,290 --> 00:01:07,420 Okay so what is BMI. 21 00:01:07,780 --> 00:01:10,870 So BMI was used to prove fact. 22 00:01:11,170 --> 00:01:12,510 Let us take an example. 23 00:01:12,520 --> 00:01:23,370 Okay so suppose is a function f so function F is through for all natural numbers. 24 00:01:23,870 --> 00:01:24,400 Okay. 25 00:01:24,540 --> 00:01:25,940 So this is an example. 26 00:01:25,940 --> 00:01:29,570 So what BMI will do BMI prove it in three steps. 27 00:01:29,580 --> 00:01:29,850 Okay. 28 00:01:29,880 --> 00:01:31,170 So there are two steps. 29 00:01:31,170 --> 00:01:40,350 So step one and step one but we will do we will prove that F of zero or F of 1 is true. 30 00:01:40,350 --> 00:01:42,500 So this is the first step of BMI. 31 00:01:42,690 --> 00:01:42,990 Okay. 32 00:01:42,990 --> 00:01:44,390 BMI proves anything. 33 00:01:44,400 --> 00:01:45,930 And effect in three steps. 34 00:01:46,140 --> 00:01:51,320 So the first step is prove f of 0 F of 1 is true okay. 35 00:01:51,380 --> 00:01:57,530 So this step means begin start with very small number and prove that generally it's a very trivial problem. 36 00:01:57,530 --> 00:02:00,820 Okay simply just put the value okay. 37 00:02:00,840 --> 00:02:02,710 We will also take an example. 38 00:02:02,760 --> 00:02:08,340 So this step is actually called biscuits. 39 00:02:08,350 --> 00:02:12,040 Now the second step of BMI is in second step. 40 00:02:12,070 --> 00:02:12,830 What we will do. 41 00:02:12,910 --> 00:02:22,010 The name of the second step is induction hypotheses so in induction hypotheses what do we do. 42 00:02:22,030 --> 00:02:25,940 We will assume Okay so what we will assume. 43 00:02:25,940 --> 00:02:28,690 So first of all we have to assume you do not question it. 44 00:02:28,730 --> 00:02:29,120 Okay. 45 00:02:29,120 --> 00:02:30,130 Please don't caution it. 46 00:02:30,140 --> 00:02:32,110 We will always assume something. 47 00:02:32,180 --> 00:02:41,430 So we are assuming we are assuming that f of K is true where gays are generally okay for any general 48 00:02:41,430 --> 00:02:42,860 gay. 49 00:02:42,950 --> 00:02:53,540 Now the third step of that third step of BMI is induction step okay induction step so in induction step 50 00:02:53,740 --> 00:03:00,040 what we will do generally in induction step what we do is using that too. 51 00:03:00,120 --> 00:03:09,180 So I am writing here using Step Two using Step two we will prove using Step two we will try to prove 52 00:03:09,330 --> 00:03:11,100 that f k plus one is true 53 00:03:13,840 --> 00:03:20,970 okay so we have to prove two things this one and this one we have to prove base case and we have to 54 00:03:20,970 --> 00:03:31,090 prove induction step okay we can assume this one we can assume Step Two okay we can assume Step 2 It 55 00:03:31,090 --> 00:03:37,150 is our hypotheses we do not have to worry about this but we have to prove Step 1 and we have to prove 56 00:03:37,300 --> 00:03:41,080 step t Step 2 we can assume and please do not question it. 57 00:03:41,410 --> 00:03:51,320 Okay so let us take an example and then we will soil that example with the help of BMI Okay so let's 58 00:03:51,320 --> 00:03:59,460 solve this very simple example so Sigma and what is segment segment basically means some more fast and 59 00:03:59,460 --> 00:04:03,830 natural number and there's a formula and in doing plus one by two. 60 00:04:03,850 --> 00:04:04,160 Okay. 61 00:04:04,180 --> 00:04:06,160 Some of the first and natural number. 62 00:04:06,160 --> 00:04:09,030 Now let's apply BMI so in BMI. 63 00:04:09,130 --> 00:04:15,650 First step is the base case in the base case what we will do we will solve very small problem. 64 00:04:15,730 --> 00:04:18,010 So first step. 65 00:04:18,430 --> 00:04:24,020 Base case so in base case f of 0. 66 00:04:24,330 --> 00:04:30,630 So what is f 0 so Sigma 0 is basically sum of zero natural number first is our natural number that will 67 00:04:30,630 --> 00:04:31,480 be zero. 68 00:04:31,500 --> 00:04:33,880 So this is our largest. 69 00:04:33,900 --> 00:04:36,330 Now let's calculate outages. 70 00:04:36,330 --> 00:04:39,630 So for outages this is our formula. 71 00:04:39,630 --> 00:04:46,290 And now let us try to put an equal 0 so n equals zero here so zero and to zero plus one by two. 72 00:04:46,290 --> 00:04:47,880 So this is this is zero. 73 00:04:48,030 --> 00:04:49,760 Okay so this is outages. 74 00:04:49,860 --> 00:04:51,910 So logistics outages. 75 00:04:52,080 --> 00:04:54,390 So we proved the base case. 76 00:04:54,510 --> 00:04:54,980 Okay. 77 00:04:55,260 --> 00:04:56,910 So we have proved 4 0. 78 00:04:56,940 --> 00:04:59,240 We can also provide for 1 2. 79 00:04:59,280 --> 00:05:01,140 Now let us also provide for 1. 80 00:05:01,140 --> 00:05:02,160 So 4 1. 81 00:05:02,160 --> 00:05:05,990 So sigma 1 will be some 0 first one natural number that will be 1 only. 82 00:05:05,990 --> 00:05:12,420 So this is our allergies and our right to our allergies will be so and into an investment by. 83 00:05:12,420 --> 00:05:14,980 So when one plus one by 2. 84 00:05:15,150 --> 00:05:19,500 So this is 2 by 2 and this is 1 and this is our allergies. 85 00:05:19,500 --> 00:05:21,620 So allergies is outages. 86 00:05:21,630 --> 00:05:23,610 Hence we have proved our base case. 87 00:05:23,610 --> 00:05:23,880 Okay. 88 00:05:25,530 --> 00:05:27,140 Our base case is ready now. 89 00:05:27,150 --> 00:05:31,280 Now the second step the second step is induction hypotheses. 90 00:05:31,380 --> 00:05:32,070 Okay. 91 00:05:32,220 --> 00:05:35,870 So our second step is induction hypotheses. 92 00:05:36,120 --> 00:05:38,140 So in induction I put it this what we will do. 93 00:05:38,160 --> 00:05:40,140 We will assume I can assume. 94 00:05:40,140 --> 00:05:48,190 So what I'm assuming here I'm assuming Sigma okay is keen to Kate Plus One By Two please do not question 95 00:05:48,190 --> 00:05:51,120 it to why I am assuming we just have to assume. 96 00:05:51,210 --> 00:05:52,970 So what I'm assuming Sigma okay. 97 00:05:53,000 --> 00:06:00,210 You said Mark equals Kate plus on might do is true I'm assuming this thing is true. 98 00:06:00,270 --> 00:06:01,690 Okay. 99 00:06:01,840 --> 00:06:03,320 So this is our exemption. 100 00:06:03,340 --> 00:06:04,690 Okay broad worry about it. 101 00:06:04,690 --> 00:06:06,320 And please broad question this. 102 00:06:06,550 --> 00:06:11,380 Now the third step the third step is induction step. 103 00:06:11,580 --> 00:06:17,190 So in induction step what we have to do we have to prove we have to prove 40 plus 1. 104 00:06:17,190 --> 00:06:23,520 So we have to prove that Sigma K plus 1 This is for the value. 105 00:06:23,520 --> 00:06:27,560 So what we will do we are we will put an equals K plus 1. 106 00:06:27,670 --> 00:06:30,370 Okay here we will put an equal escape lesson. 107 00:06:30,370 --> 00:06:35,400 So K plus 1 this will become K plus two by two. 108 00:06:35,440 --> 00:06:35,700 Okay. 109 00:06:35,710 --> 00:06:44,160 So we have to prove this Sigma K plus 1 sigma Kate plus 1 is keep listening to K plus two by two. 110 00:06:44,180 --> 00:06:46,020 Now let us prove this. 111 00:06:46,040 --> 00:06:47,570 So what is this. 112 00:06:47,630 --> 00:06:48,970 We are solving allergies. 113 00:06:49,000 --> 00:06:52,300 Okay so segment K plus 1. 114 00:06:52,330 --> 00:06:54,220 So can I write like this. 115 00:06:54,280 --> 00:06:58,020 K plus 1 plus sick monkey. 116 00:06:58,060 --> 00:06:59,980 I can write it like this. 117 00:06:59,980 --> 00:07:02,240 This is basically K plus 1. 118 00:07:02,620 --> 00:07:11,270 So what is the value of sick mucky so we can take the value of sigma came from here okay so let's put 119 00:07:11,270 --> 00:07:12,370 the value of sigma okay. 120 00:07:12,400 --> 00:07:17,240 So this is gain do K plus 1 by 2. 121 00:07:17,810 --> 00:07:18,640 Okay. 122 00:07:18,830 --> 00:07:23,360 Now what we can do can and multiply and divide about 2 here. 123 00:07:23,660 --> 00:07:26,170 Yes I can then what I will do. 124 00:07:26,250 --> 00:07:32,330 Take Gabe listen my 2 s comment Um okay I'm digging K plus 1 by the way is common. 125 00:07:32,330 --> 00:07:41,050 So we have 2 plus K so this is our largest and now our largest and outages are equal. 126 00:07:41,070 --> 00:07:44,870 So a logistic equals outages okay. 127 00:07:44,890 --> 00:07:49,100 So we have proved our third step which is the induction step. 128 00:07:49,100 --> 00:07:54,350 Okay so we have proved the base case we have proved the induction step and we have assumed our induction 129 00:07:54,350 --> 00:07:55,340 hypotheses. 130 00:07:55,340 --> 00:08:01,660 Hence we proved that Sigma n is added to in person by okay. 131 00:08:01,830 --> 00:08:08,700 So proved hence proved OK so why it works OK. 132 00:08:08,730 --> 00:08:10,830 How does it prove something. 133 00:08:10,830 --> 00:08:14,460 So there is a very simple and awesome intuition behind this. 134 00:08:14,460 --> 00:08:16,250 And what the intuitions is. 135 00:08:16,280 --> 00:08:20,160 So the indulgences we have told you the starting position. 136 00:08:20,160 --> 00:08:29,790 We have told you the base we have taught you how to take next step from one step now from the base from 137 00:08:29,790 --> 00:08:30,530 the base. 138 00:08:30,630 --> 00:08:36,660 We can use this thing to go to next step to go to one step ahead. 139 00:08:36,660 --> 00:08:42,380 And then we can prove this step and then we can go to next step. 140 00:08:42,420 --> 00:08:45,870 Then we can prove this step and then we can go to next step. 141 00:08:45,870 --> 00:08:47,340 And so on. 142 00:08:47,340 --> 00:08:50,370 Okay so this was the basic contusion. 143 00:08:50,400 --> 00:08:52,290 Now let's see some math also. 144 00:08:52,350 --> 00:08:55,850 Okay let's see some metal also. 145 00:08:55,890 --> 00:09:05,250 So what we have done here is so if gay equals zero so gay means basically and only so if any equals 146 00:09:05,370 --> 00:09:05,880 zero. 147 00:09:05,970 --> 00:09:11,580 So this we have proved this was our base we have proved four and equals zero. 148 00:09:11,590 --> 00:09:15,010 So this we have proved okay. 149 00:09:15,050 --> 00:09:18,020 Now the second step which was the induction hypothesis step. 150 00:09:18,620 --> 00:09:19,110 Okay. 151 00:09:19,190 --> 00:09:22,390 So inside the induction I put this step if gay equals zero. 152 00:09:22,400 --> 00:09:28,000 What did I assume I assume that f off gay is true. 153 00:09:28,100 --> 00:09:28,900 Now this. 154 00:09:28,910 --> 00:09:31,210 Now this thing we assumed an induction I put to this step. 155 00:09:31,270 --> 00:09:34,250 But what I'm saying here is the value of k 0. 156 00:09:34,690 --> 00:09:35,210 Okay. 157 00:09:35,300 --> 00:09:38,620 The value of k 0 inside the induction I put this step. 158 00:09:38,660 --> 00:09:45,060 So that means F of zero is true so first of all this is not assumption. 159 00:09:45,070 --> 00:09:47,970 This we have proved okay. 160 00:09:48,020 --> 00:09:49,640 This we have proved the base case. 161 00:09:49,640 --> 00:09:50,950 This is not our inception. 162 00:09:50,960 --> 00:09:52,070 F of 0 is true. 163 00:09:52,070 --> 00:09:54,800 This is not an assumption this is a fact. 164 00:09:54,820 --> 00:09:55,280 Okay. 165 00:09:55,360 --> 00:09:57,070 I am not assuming anything here. 166 00:09:57,140 --> 00:10:00,020 We have already proved this in our base case. 167 00:10:00,110 --> 00:10:03,460 Now the induction step inside the induction step. 168 00:10:03,590 --> 00:10:04,510 What did I approved. 169 00:10:04,520 --> 00:10:10,180 I approved that if F of case true then f of K plus 1 is also true. 170 00:10:10,520 --> 00:10:13,470 This thing I approved for any general gay. 171 00:10:13,510 --> 00:10:17,100 Okay I have proved this thing for any general Okay. 172 00:10:17,270 --> 00:10:21,550 F F off gays true then f of gay plus 1 is also true. 173 00:10:21,590 --> 00:10:25,870 Now the value of k 0 so f of 0 is true. 174 00:10:25,910 --> 00:10:30,950 That means using the index in step f of 1 is also true. 175 00:10:31,170 --> 00:10:40,820 Okay because we have proved this for a general G no f f of Venus true then f of 2 is also true using 176 00:10:40,820 --> 00:10:48,110 the induction step f f of 2 is true then f of TS also true then 4 is also true then 5 is also true. 177 00:10:48,140 --> 00:10:50,980 And this way we can go up to and okay. 178 00:10:51,140 --> 00:10:59,120 So finally what we can write here we can write f often is true and we have to prove this only. 179 00:10:59,120 --> 00:11:02,210 So we have proved in this way okay. 180 00:11:02,330 --> 00:11:09,020 So we came out to using when using do we go 2 3 using 3 we go to 4 and so on. 181 00:11:09,020 --> 00:11:14,380 So in every recurrent problem we have to think like this only okay in every cogent problem. 182 00:11:14,420 --> 00:11:18,080 You have to think you are applying PMI to prove it to them. 183 00:11:18,100 --> 00:11:20,230 I am repeating myself in every cogent problem. 184 00:11:20,240 --> 00:11:24,260 What we will do we will think that we are applying PMI to prove a totem. 185 00:11:24,320 --> 00:11:29,770 Okay so first of all in every occasion problem what we have to do to solve an integration problem. 186 00:11:29,780 --> 00:11:32,110 We have to do two simple things. 187 00:11:32,210 --> 00:11:34,940 So the first thing is we will think we will. 188 00:11:34,940 --> 00:11:36,910 We have to think about the base case. 189 00:11:36,930 --> 00:11:38,230 Okay very simple case. 190 00:11:38,240 --> 00:11:40,620 We have to think about the base case. 191 00:11:40,750 --> 00:11:45,420 Now the second thing is I don't have to worry for the smaller problem. 192 00:11:45,440 --> 00:11:49,870 Okay in the second step We don't have to worry for the smaller problem. 193 00:11:49,870 --> 00:11:54,900 If I have to work for n then I'm going to assume it works for and minus one. 194 00:11:54,910 --> 00:11:58,980 So assume you have a solution for the smaller problem solution assumes. 195 00:11:58,990 --> 00:12:04,300 While the problem solutions already did you just have to use their solution to solve the bigger problem. 196 00:12:04,330 --> 00:12:07,200 If I am able to do that then be a Macy's. 197 00:12:07,240 --> 00:12:08,210 Your code will work. 198 00:12:08,240 --> 00:12:10,520 BMI guarantees that your code will work. 199 00:12:10,760 --> 00:12:17,620 Okay and I will not think all this like fact for is calling 3 3s calling 2 and so on. 200 00:12:17,890 --> 00:12:23,050 Okay I will not think all this so we will directly think for an okay. 201 00:12:23,260 --> 00:12:28,690 We will directly think foreign because we will assume we have and minus one. 202 00:12:28,900 --> 00:12:32,270 Now using that assumption I need to properly solve for then. 203 00:12:32,460 --> 00:12:38,580 Okay so let's write factorial and again but this time we will think in terms of BMI. 204 00:12:38,670 --> 00:12:47,980 Okay so I am writing factorial function again but this time we will think only in BMI items. 205 00:12:48,010 --> 00:12:51,310 So first of all what do the return type they return. 206 00:12:51,320 --> 00:12:52,580 They will be in danger. 207 00:12:52,750 --> 00:12:55,200 The name of the function is factorial fact. 208 00:12:55,420 --> 00:12:57,750 It will take AI Indigenous input. 209 00:12:57,880 --> 00:13:01,690 Now the first step of an integration problem thinking BMI terms only. 210 00:13:01,720 --> 00:13:02,580 Okay. 211 00:13:02,710 --> 00:13:04,180 What is the first step. 212 00:13:04,180 --> 00:13:06,250 The first step is the base case. 213 00:13:06,490 --> 00:13:07,730 Very small problem. 214 00:13:08,530 --> 00:13:10,780 So you can take. 215 00:13:10,780 --> 00:13:12,040 So if any equals zero. 216 00:13:12,070 --> 00:13:15,070 What is effectual for zero factorial. 217 00:13:15,070 --> 00:13:16,390 The answer is 1. 218 00:13:16,460 --> 00:13:17,840 Okay zero effect or Lisbon. 219 00:13:17,890 --> 00:13:19,780 You can also write for one on one also. 220 00:13:19,800 --> 00:13:20,090 Okay. 221 00:13:20,110 --> 00:13:22,310 If any equals 1 then also return 1. 222 00:13:22,360 --> 00:13:23,590 So that's our trade. 223 00:13:23,620 --> 00:13:25,320 So our base case is ready. 224 00:13:25,540 --> 00:13:26,380 Now what we have to do. 225 00:13:26,380 --> 00:13:29,470 Second step of PMI is induction hypotheses. 226 00:13:29,470 --> 00:13:40,720 You have to assume so I am assuming that I have my own set for then minus 1 OK so this is our assumption 227 00:13:40,730 --> 00:13:42,480 now please do not question this. 228 00:13:42,480 --> 00:13:45,990 OK so this is assumption. 229 00:13:46,180 --> 00:13:49,830 Okay so suppose this function for all function works. 230 00:13:49,870 --> 00:13:53,700 So I'm giving the actual function a smaller input it will give me the answer. 231 00:13:53,710 --> 00:13:54,100 Okay. 232 00:13:54,220 --> 00:13:56,560 Do not caution this line okay. 233 00:13:56,560 --> 00:13:58,100 Please note caution this line. 234 00:13:58,180 --> 00:13:59,170 You have to assume this. 235 00:13:59,380 --> 00:14:00,240 Okay. 236 00:14:00,580 --> 00:14:03,550 So this is our assumption it is also called a recursive case 237 00:14:06,970 --> 00:14:07,930 okay. 238 00:14:07,960 --> 00:14:12,130 Now what we have to do we have done set for and minus in fact total. 239 00:14:12,160 --> 00:14:15,160 Now we have to properly calculate the so for and factorial. 240 00:14:15,160 --> 00:14:22,920 So this will be an multiply and multiply small onset okay. 241 00:14:23,010 --> 00:14:24,610 We have to properly calculate. 242 00:14:24,660 --> 00:14:25,140 Okay. 243 00:14:25,290 --> 00:14:26,630 So this is our third step. 244 00:14:28,850 --> 00:14:34,840 This was the third step of being my third step for solving any recursion problem okay. 245 00:14:34,850 --> 00:14:35,990 This was the second step 246 00:14:39,980 --> 00:14:41,480 and this was the first to step 247 00:14:44,310 --> 00:14:46,800 so first step is basically base case. 248 00:14:46,830 --> 00:14:49,910 Second step is assumption which is also called recursive case. 249 00:14:49,920 --> 00:14:53,690 And the third step is the calculation okay. 250 00:14:53,810 --> 00:14:55,030 So the third step is 251 00:14:57,740 --> 00:15:04,740 calculation where we have our answer ready and we can draw done either on set okay. 252 00:15:04,800 --> 00:15:11,280 Now let's call this function to see out federal food 253 00:15:14,210 --> 00:15:14,670 okay. 254 00:15:14,880 --> 00:15:16,030 Let's go now file. 255 00:15:16,210 --> 00:15:23,550 Let's run the called so our output is 24 for factory list 24 so our code is working. 256 00:15:23,550 --> 00:15:29,520 Now see here we are not thinking like 4 is calling 3 3 is calling to do is calling when we are not going 257 00:15:29,520 --> 00:15:30,160 in depth. 258 00:15:30,210 --> 00:15:31,110 Okay. 259 00:15:31,110 --> 00:15:35,220 Think only in terms of PMI remember three step first step. 260 00:15:35,220 --> 00:15:37,070 Simple very simple biscuits. 261 00:15:37,110 --> 00:15:39,780 Second step assumption which is the recursive keys. 262 00:15:39,900 --> 00:15:41,740 Third step is the calculation. 263 00:15:41,820 --> 00:15:42,610 Okay. 264 00:15:42,840 --> 00:15:46,830 You have done so with a smaller problem now with the help of the answer of the smaller problem. 265 00:15:46,860 --> 00:15:50,040 Calculate the big answer and then return the big answer. 266 00:15:50,070 --> 00:15:50,520 Okay. 267 00:15:50,610 --> 00:15:51,990 Simple enough. 268 00:15:51,990 --> 00:15:53,600 So there are two step. 269 00:15:53,610 --> 00:15:54,840 First is the base case. 270 00:15:54,840 --> 00:15:57,620 Second is as you know it will work for the smaller problem. 271 00:15:57,810 --> 00:16:01,800 Okay third step is properly called for the bigger problem. 272 00:16:01,870 --> 00:16:02,780 Three simple step. 273 00:16:02,790 --> 00:16:05,210 I am repeating first base case. 274 00:16:05,250 --> 00:16:07,980 Second assume it will work for the smaller problem. 275 00:16:07,980 --> 00:16:10,970 Third properly called for the bigger problem. 276 00:16:11,010 --> 00:16:11,570 Okay. 277 00:16:11,730 --> 00:16:14,660 This is very simple called okay. 278 00:16:14,870 --> 00:16:15,230 Thank you.