Decoding Recursion | Count Ways to Reach Nth Stair Problem! | Nishant Chahar | Leetcode | GFG
Decoding Recursion | Count Ways to Reach Nth Stair Problem! | Nishant Chahar | Leetcode | GFG
In this video, we are learning about Recursion and how it works with the help of two problems.
1. Problem: https://practice.geeksforgeeks.org/pr…
You can use my code NISHANT to get 10% Off on all GFG courses.
✨ Important Links ✨
- Don’t Click Here: https://bit.ly/3afmPha
- Telegram Link: https://t.me/codeIn10byNishant
- Github Repo Link: https://github.com/chaharnishant11/Co…
✨ Hashtags ✨
#NishantChahar #Microsoft #DSA #Recursion #FAANG #NSIT #NSUT #engineering #internship #college
✨tags ✨
Where to learn dp
where to learn graphs
where to learn dsa
how to start programming
how to start coding
where to learn trees
what is memoisation
what is tabulation
what are graphs
where to learn Operating systems
where to learn dbms
where to learn oops
where to learn computer networks
where to learn low level design
where to learn cs fundamentals
Sanchit jain
Gaurav sen
Gate smashers
Placement guide
How to start programming
where to learn cpp
where to learn python
where to learn javascript
where to learn java
Placement guide
Nishant Chahar Placement Guide
languages to learn
resources to learn data structures
Projects development
AR/VR
Blockchain Machine learning
Deep Learning
Software developer engineer ,
Side projects ,
Importance of side projects ,
Machine Learning Engineer,
How to become a machine learning engineer ,
Associate engineer
Data structures Algorithms
College Life, College, Memories
Fun Fests Chill Enjoy
IITD Mood indigo rendezvous IIT
NSUT Moksha DTU Engifest
Bits Bitsgoa
Namaste Javascript
Namaste Javascript Akshay Saini
Apna college
Apna college c++
apna college DSA
Where to learn dp
where to learn graphs
where to learn dsa
how to start programming
how to start coding
where to learn trees
what is memoisation
what is tabulation
what are graphs
where to learn programming
how to start coding
where to learn coding
where to learn DSA
resources to learn programming
how to crack amazon
how to crack placement
blockchain
what is blockchain
blockchain technology
blockchain technology explained
blockchain explained
blockchain technology in hindi
web development roadmap
roadmap to learn web development
android development roadmap
MERN stack roadmap
machine learning roadmap
roadmap to learn machine learning
roadmap for deep learning
roadmap for 2nd years
roadmap for opensource
roadmap for ios development
roadmap for deep learning
roadmap to learn DSA
Content
0 -> Hi guys welcome to the channel
1.598 -> Code in 10
2.364 -> And I am Nishant Chahar
3.339 -> So in today's video we gonna talk about a question
5.742 -> Count ways to reach nth stair
7.319 -> First lets understand the question
10.013 -> After understanding question we will understand code
11.759 -> And lets start the video without any delay
14.663 -> Before starting the video, the most important thing
17.008 -> Lets revise recursion once again
19.016 -> What is it
19.847 -> We have completed last 2 videos
21.799 -> We have done a lot of questions in last 2 videos
23.67 -> Okay
24.46 -> We have solved around 3-4 questions
25.745 -> And the most important thing in that
28.375 -> which I explained in starting
29.987 -> Recursion has 3 steps
31.356 -> Okay
32.428 -> One is your base case
33.292 -> Second is your recursive call
35.482 -> And third is your small calculations part
37.929 -> These 2 steps are interchangeable
40.275 -> Many a time we do small calculations first and recursive call after that
43.364 -> Vice versa
44.549 -> Okay
45.296 -> Now you will say that you have told us the same thing in last 2 video
47.867 -> Why are you telling the same thing again
49.088 -> I am telling you because, as soon as you get a recursive question
52.618 -> It should come to your mind that how can I break it in 3 steps
57.038 -> What can be its base case
58.601 -> What can be its recursive call
60.018 -> Okay
60.858 -> And what can be my small calculation
62.475 -> As soon as you understand the recursive call , base case and small calculation
66.777 -> Your recursive question gets solved
69.603 -> Same is the case for back tracking
71.218 -> DP
72.197 -> So that is why I am focusing on this thing more
75.363 -> Because it is going to be used a lot
77.53 -> Now lets first understand the question
79.524 -> What is the scene here? You have given an n
82.193 -> We will not take 5 this time , lets take 6 this time
84.427 -> Okay
84.896 -> You are given an n
86.396 -> So these are stairs
87.966 -> Like this
91.162 -> 6
91.818 -> Okay
92.512 -> Now we have habit in childhood
94.183 -> We used to stand here
96.195 -> We used to jump one or two stairs at once
99.274 -> I still jump 2 stairs
100.948 -> So that is the habit
103.236 -> So this question is made on that habit
105.558 -> That there is a man
107.021 -> He has to go from this 0th level to 6th level
110.874 -> So in how many ways he can go
113.884 -> And every time, either he will take 1 step or 2 step
115.897 -> Okay
117.455 -> Now lets take different ways in it.
119.212 -> It can happen that there is some tired man or an aged person
123.029 -> That will not jump 2 steps
124.711 -> We are children , we jump
125.765 -> He will jump one by one
127.661 -> So 1, 2,3 4, 5, 6
129.902 -> So this is one case
132.675 -> In which we took one , one step
133.937 -> Okay
134.872 -> Now there is someone who have just come after playing
137.048 -> He first took 2 steps
138.448 -> But after that he took 1,1 step
140.306 -> Right
141.373 -> So this become your second case
145.378 -> Similarly there are multiple cases
147.584 -> That he climbed one time in first step
148.856 -> Then he jumped two
149.995 -> Like this , many cases can be made here
153.908 -> Okay
156.263 -> Multiple cases can be made
158.19 -> Now if we understand this
160.328 -> That what is exactly happening
162.193 -> Means what we do , we thing from the above
163.846 -> If some person is coming from above
165.78 -> Okay
166.518 -> Means he is standing above
167.734 -> So he if gets to know that how many ways did he had on this step
171.699 -> And on this step, how many ways did he had
173.088 -> He will add these 2
175.066 -> So I will get to know that how many steps I will have here
177.608 -> Right
178.106 -> Means it is it
179.527 -> That coming here will be equal to these 2
182.881 -> It is very similar
186.52 -> To Fibonacci
188.672 -> It is very similar to Fibonacci
189.777 -> Now why it is happening like this
191.316 -> Lets take a small example in it
194.002 -> Now lets take n equal to 4 here
196.686 -> If we will take N as 4
200.333 -> So what will happen
203.47 -> That
204.324 -> These are 4 stairs only
206.307 -> We can try dry running it
209.653 -> There is a guy here
211.577 -> What can happen in it is , he came to this step
214.96 -> Came to this step
216.13 -> came to this step
217.146 -> And to this step
218.533 -> This is one case
219.736 -> What can be the second case?
221.375 -> He came to this step
222.188 -> He said lets take one more step
225.521 -> And then Jumped 2 steps
226.849 -> So these are our 2 cases
228.834 -> Similarly
230.418 -> Again he came to this step
231.991 -> Now he said lets take 2 steps first
234.527 -> After that I will take 1
236.26 -> Our cases become 3
238.376 -> Okay
239.443 -> In this way he will say
240.623 -> That lets take 2 steps from here directly
243.934 -> Then take 1 and then take 1
245.193 -> So these become 4 cases
246.987 -> Now what can be the last case
249.704 -> He took 2 steps of two two
252.126 -> These become our 5 cases
254.132 -> So there are total 5 ways in it
257.093 -> In which he can climb 4 step stairs
260.801 -> Okay
261.714 -> Now similarly if we break it
263.486 -> If these were 3 stairs , then what would happen
265.739 -> Okay
267.644 -> If these were 3 stairs , then what would happen in it
269.208 -> Here the man in standing
271.623 -> Either I can take one step or 2 steps from here
274.872 -> Okay
275.896 -> If I will take 1 step
277.432 -> So I will reach to second number
278.806 -> And if I will take 2 steps, I will reach to third directly
281.914 -> Okay
282.826 -> So If I am standing here at first, so I have only 2 options
285.799 -> Okay
287.206 -> And If I am standing at 2nd
288.547 -> Then I have only 1 option
289.63 -> I can take only single step and not more than that
291.66 -> Our answer will be 3
295.118 -> If you will think, What we have to do? We have to see
297.297 -> If we are standing on the last one
299.824 -> Soo how many steps we can take
301.165 -> Means How many options do we have
303.604 -> If we see this n =4 case again
306.668 -> So if we get to know the ways of coming to 3rd plus 2nd, those were the ways to come to 4th
315.287 -> Because there is no way of coming other than that
317.338 -> Either you can jump 1 stair or 2 stair
319.437 -> If you will come to 2
321.923 -> You know these are the ways
322.935 -> Of coming to 2
323.626 -> And to come 3, these are the ways
324.958 -> So We will add these 2, we will come to 4th
326.549 -> Same to same is Fibonacci
328.688 -> That we did in last video
330.403 -> So when it is same to Fibonacci
332.666 -> Its recursive call will be f(n) = f(n-1) + f(n-2)
340.845 -> So think one time
342.95 -> That what will be the difference exactly
344.544 -> Means the Fibonacci series that we had
346.692 -> And in this series, what can be the difference
347.953 -> Think
350.007 -> You have thought
351.292 -> After pausing the video
352.368 -> So the difference is only that our starting point
355.278 -> Or our base case
357.766 -> That is different
359.641 -> There our base case used to be f(0) value 0
363.084 -> And f(1) value used to be 1
364.804 -> Here we have f(1) base case
368.015 -> Whose value is 1
370.18 -> And f(2) whose value is 2
371.63 -> Now why it is like
372.945 -> Lets understand that
373.736 -> You have only one stair
375.826 -> So you can come to this in only one way
377.901 -> That you climbed one step
379.52 -> Similarly of you have 2 stairs
381.61 -> What option do you have?
384 -> Either climb to 1
385.096 -> Come to 2
386.576 -> Or come to 2 directly by jumping
388.319 -> So there are 2 ways
389.982 -> Okay so lets do the question for 6
394.186 -> Okay
395.16 -> Lets do for 6
396.632 -> We will have 6
397.669 -> 6 will say that bring me 5
399.424 -> And bring me 4
401.474 -> Okay
402.497 -> Then 5 will say
404.238 -> Bring me 4 and 3
405.149 -> Four will say bring me 3 and 2
409.547 -> We know 2 is base case
411.332 -> So we will not go beyond this
412.233 -> Similarly 4 will again say
413.719 -> Bring me 3 and 2
415.713 -> This 3 will say bring me 2 and 1
418.66 -> This 3 will say bring me 2 and 1
422.568 -> Similarly 3 will again say that bring me 2 and 1
425.998 -> And you know about 2 , it is base case
428.423 -> So what we will do from here
431.212 -> We know 2 has 2
433.039 -> We will say our answer is 2
434.743 -> One will say my answer is 1
436.147 -> We will add these two
437.395 -> It will become 3
438.191 -> Here 3 will come
439.564 -> 2 will say answer is 2
441.109 -> So 2 will come
442.111 -> Again we will add these 2
443.256 -> 5 will come
443.903 -> If we will go to 5, here 5 will come
445.322 -> Right
446.513 -> Then 2 will say 2
448.156 -> One will say 1
449.082 -> Again 3 came
450.258 -> Okay
451.351 -> And from here 3 will say , answer is 3
454.153 -> Similarly 2, 1
455.888 -> 3 will come
457.689 -> This will come 2
459.667 -> After adding it will say 5
461.73 -> Now these two will be added
463.881 -> 5 and 3 will come 8
465.753 -> 5 will again come from here
468.254 -> We will again add these two
470.21 -> Our answer will come to 13
472.248 -> That should be for 6
474.455 -> So we did same things in it
476.939 -> We have done same steps
477.829 -> We read 3 steps
479.311 -> We are doing these 3 steps
481.122 -> We got to know base case
482.091 -> for f(1) and f(2)
484.48 -> when 2 and 1 is coming, we know for 2 there are two steps and for 1 there are one step
488.026 -> We applied recursive call
489.885 -> After that we did small calculations
491.472 -> Now lets code this
492.819 -> So if (n==1 || n ==2)
502.343 -> SO what we have to do
503.14 -> Return n
504.945 -> Okay
505.712 -> That if the value is 1, the output is 1 and if the value is 2 , then the output is 2
511.048 -> After that what we have to do
512.536 -> After that we have to do int
514.268 -> Recursive call
515.674 -> one
517.837 -> count ways
520.398 -> Bring me the answer
523.266 -> of n-1
526.495 -> int recursive call 2 bring me (n-2)
532.689 -> Then we will do int small calculation
535.28 -> We will tell it
537.252 -> That
538.262 -> Recursive call 1
541.087 -> We will tell it recursive call 1
544.233 -> plus
546.056 -> Recursive call 2
547.182 -> You will add them
548.836 -> So it will be your answer
550.547 -> That's it we will return here
552.415 -> Small calculation
555.179 -> Now lets try too compile it
557.807 -> Our expected output is 5
559.757 -> And this is 5
561.602 -> So our 5 answer has come
562.751 -> Similarly lets try running for 2-3 more
565.807 -> For custom input
567.284 -> So for 10, 89 should come and 89 is coming
573.342 -> Similarly lets try doing one more
575.094 -> Lets take a little bit big number
576.724 -> That if we try doing for 20
579.316 -> So it will come right for 20 also
581.32 -> Right
584.62 -> So our code has completed
586.59 -> If you have some doubts left, you can comment down
590.508 -> Your doubts will be solved
591.93 -> So this was all in this video
593.512 -> In next video, we will do a little bit more nice question
596.027 -> This was medium one
597.042 -> This was because , it is a question on DP
598.836 -> When we will study DP, then we will do it
601.862 -> Now we have solved recursive one
603.508 -> Now if I will submit
605.848 -> I am not submitting
607.219 -> So thank you so much for watching
607.949 -> Lets meet in next video
Source: https://www.youtube.com/watch?v=OpzAoNwwYJI