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.

