Previously we have discussed what recursion is and we have identified when to use recursion.
Now in this video, let's discuss a powerful concept called recursive leap of faith.
This concept will help us and understand recursion even better, and it also deals with how to actually
go about using recursion in coding interview questions.
Now, many times recursion feels like magic.
If you are just able to wrap your head around the basics of recursion, you will see that you will be
able to use this powerfully in solving a variety of coding interview questions.
And that's why many people think of recursion.
Like feel of it as if it's magic.
Now what are the steps in using recursion?
So the five steps in using recursion are these five steps over here.
And let's go through them one by one.
The first step is to understand the problem at hand.
Let's take an example.
Let's say you are asked to print a sequence that looks like this.
So you have 321123.
Now this is just an example.
Let's say you are given n and you need to print n, n, minus one, etc. up to one.
And then you have one, two etc. up to n.
So that's what is over here just for n equal to three.
The second step is to identify a subproblem.
We have seen that recursion is suitable when you are able to break the original problem into subproblems,
and solving the subproblems helps you to solve the original problem.
So the second step over here is to identify a subproblem.
Now identifying a subproblem will become more intuitive and you will be able to do it more and more
easier with more exposure to a wide variety of coding interview questions, which we will take care
of.
In this course.
We will go through a variety of questions in the future sections, but let's take it one step at a time.
So for this example over here, what would be the subproblem?
The subproblem would be to print 211 and two right.
So again if you had to do this like (543) 211-2345, notice that the subproblem for the original problem
is to print 43211234, and the subproblem of this would be to print three two, 1123, etc..
All right.
So that's the second problem which is second step which is to identify the subproblem.
The third step is the step of trust or faith, which is what we call the recursive leap of faith.
And this is actually what makes recursion feel like magic.
Or this is actually what makes recursion so powerful and so helpful in a wide variety of coding interview
questions.
So let's try to understand this step over here.
Now, the step of trust or faith is that you have to trust that this recursive call, which is like
if we replace solving this sub problem over here with a recursive call.
We have to trust that this recursive call will correctly solve a smaller version of your problem.
Again, we will come back and try to understand this using the example at hand.
So we have identified the problem.
We have identified a sub problem.
And we are saying in this step over here that if we replace solving the sub problem with a recursive
call, we trust that if we have correctly designed the function, then this will be taken care by itself.
So that is what this trust over here involves.
Now because we trust this, we don't need to mentally simulate or unroll the whole recursion.
Right.
So this is the power of recursion if you set it up correctly.
And if you have the correct base case as well, then it's going to take care of all the other smaller
sub problems without you having to unroll mentally.
All the various steps.
So this makes recursion extremely powerful.
Okay, so you assume your function works for simpler cases.
It will work for more complex ones.
So this is the step of the recursive leap of faith which makes recursion as we just now said, so powerful.
Now let's go through the remaining steps, and then let's come back to this example again to understand
this even better.
Step number four is to link the original problem and the sub problem.
Remember, in the previous video we had said that recursion is useful when solving the sub problem is
helpful in solving the original problem.
So that's what we're doing over here.
We are linking the sub problem to the original problem.
So in this case the original problem when n is equal to three is to print three, two, one, one,
two and three.
Now we have already taken care of 2112 because it's the sub problem.
And we trust that the recursive call is going to give us this output over here.
Now linking one and two would mean to ensure that if you're getting this, just ensure that you're getting
these parts as well in the output.
Again, more of this in a moment.
The final step over here is to ensure that you have the base condition correctly written out.
Because remember, for recursion you always need a base condition to avoid an infinite loop.
Now in this case, for this example over here, let's say the base case is for zero just return because
we just want to keep printing till one.
So for example over here 54321.
And then when you reach zero just return.
We don't want to print it.
All right.
So let's say that's the base condition over here.
Now of course you can write this in different ways.
But let's just go with this for now.
Now let's just make some space and revisit this problem over here.
So and let's go through the five steps again.
So we wanted to print 321123.
And we identified that the sub problem is 2112.
We trust that if we set the recursion recursive function correctly, if you write it correctly then
this over here is going to be taken care by the recursive call.
And then in step four we linked the sub problem.
And the main problem that means we already have this part.
And we just ensure that we get this also in the output for this example.
And then we had the base case that for zero return.
Let's now go ahead and write the pseudocode for this.
Let's say we call the function seek okay.
So seek for sequence.
And we have the input n over here.
And let's say we are giving three as the input now.
Over here.
We are going to replace 2112 with a recursive call to the same function.
Because remember recursion is a function calling itself.
So this over here is going to be written as seek with a smaller input.
Over here we have n.
So we're going to have an input closer to the base condition.
Let's say that's n minus one because if n is three two is equal to n minus one.
And then in step four we linked the original problem and the sub problem.
So we have to ensure that we get this and this three over here as well in the output.
All right.
And n is three right.
So this is n in the original problem.
So this over here linking one and two in the pseudocode is going to look like this.
Print n and then have the recursive call for n minus one to get this part over here.
And then again print n to get this three also printed.
So this is going to be the recursive case.
And then finally we need to ensure that we have the base condition.
So if n is equal to zero we're just gonna return.
So this is the base case.
And this over here is the recursive case.
Now this part over here is what we call the inductive step.
In simple terms induction which is a maths concept, is that if this is going to work for N then it's
going to work for n minus one or it's the trust.
All right.
It's the trust part.
If it's going to work for N it will work for n minus one as well.
So again it will work for n because we have set it up correctly.
Right.
So if you have printed n so we got this three over here.
Then we have done the recursive call to get this part over here.
And we have done again print n to get this three over here.
All right.
So this over here is how we can apply recursion in a wide variety of problems.
And again this will become more and more easy with a lot of practice.
Let's take one more example over here.
Let's say we want to find n factorial.
Now quick side note n factorial is just n into n minus one into n minus two up to one.
For example, three factorial is three into two into one.
Now notice that let's say n is equal to five.
We would want to find five factorial.
Notice that five factorial actually can be solved as five into four factorial.
Okay.
So the second step which is identify the subproblem in this case would be four factorial.
And it is the subproblem because if we know the value of four factorial, we can use it to solve the
original problem, which is to find the value of five factorial.
So four factorial is four into three into two into one.
Let's say you know the value of four factorial as 24.
Now you can use this 24 to find the value of five factorial, because five factorial is five into 24.
All right.
So we trust that if we set this up correctly such that it works for five factorial, then it's going
to work for four factorial etc..
Right.
So that's our step number three.
And we're going to link one and two which is five.
Factorial is equal to five into four factorial.
Or in general terms n factorial is going to be n into n minus one factorial.
Notice this n minus one factorial is going to be a recursive call.
All right.
So this four factorial which is n minus one factorial is going to be a recursive call.
And we trust that it's just going to work magically.
We don't need to mentally unroll it completely okay.
And again this over here is again is the inductive step.
If it's working for N and it's working for N because we have set it up correctly, that for n factorial
it's going to be n into n minus one factorial.
So if it works for n it will work for n minus one.
So that's induction.
Again it means that when we are trying to find n minus one factorial, this same thing over here is
going to take care of it as n minus one into n minus two factorial.
Okay.
And this is going to work because we are correctly setting it up and we are ensuring that there is a
base condition.
All right.
So that's very important when you set it up.
And the base condition over here let's say is if n is equal to one then just return one.
Because notice over here we don't want to go further okay.
So five factorial is five into four into three into two into one.
We don't want to go further and we stop over here.
So if n is equal to one then return.
Now we will see in a future video how to make it very intuitive to identify the base condition.
Basically, you can think of the base condition as the last valid input or the first invalid input,
but more of that in a future video.
So over here we have discussed the recursive leap of faith, which is what makes recursion so powerful
and sometimes causes people to feel about recursion as if it is magic.