Hey everyone, and welcome back.
Over here we are starting with a new topic which is recursion.
Now I have placed recursion right at the beginning part of this course.
Because recursion is a very important topic for any coding interview.
You will see that as you go on with this course, that recursion is in fact the parent of various other
topics such as backtracking, dynamic programming, greedy algorithms, divide and conquer algorithms,
etc..
Now more of that later in the course over here.
Let's try to spend some time and understand recursion thoroughly.
And then let's go ahead and take a look at a few interesting coding interview questions.
So let's get started.
Now these are the topics that we will be discussing over here to understand recursion thoroughly.
So let's get started.
The first question over here is what is recursion?
Now in simple terms, recursion is just a function calling itself until a base condition or a terminating
condition occurs.
Let's take an example to understand what is written over here.
Let's say you want to print the numbers from 1 to 5.
And if we were to write the pseudo code for this one way, of course to do this would be by having five
print statements.
But of course this is not an optimal way for various reasons.
For example, what if instead of five, you have 100 over here?
And even worse, what if you don't know this and if it's just a variable?
So we know that this is not an optimal approach.
Another approach to handle this would be to use recursion.
Now, if we were to write the pseudo code for this, it would look like this.
You have a function.
You can name it as you want.
I've not given it any name over here.
And you have the body of the function over here.
And you call the function over here with a particular input.
In this case we are calling the function with one.
Now when you come over here, when the control comes to the function over here n is equal to one.
And then inside you have a statement over here if n greater than five return.
But n is one.
So you don't execute this.
You come over here and you print n.
So n over here is one.
So you print one.
And then notice over here that inside the body of the function you are calling the function again recursively.
So that's what is function calling itself.
So over here we are calling the function again with a different input.
And again you will see that many times it's about making the input smaller.
Or a better way of saying that would be making the input closer to the base condition or the terminating
condition.
So over here we are calling the same function with one plus one which is two.
And once you are inside the function again n is not greater than five.
And we would be printing two.
And we would again call the same function with three which is two plus one.
So that's what we say function calling itself which is recursion in simple terms okay.
And again remember a base condition is very important for any recursive um solution.
Because if you don't have a base condition you would have created an infinite loop, right.
So you need the function calling itself to stop at some point, which is the base condition or the terminating
condition.
Now in this case, because we just want to print up to five, if n becomes greater than five we can
stop.
So this is the base condition.
And remember if you don't have a base condition you will get a stack overflow error.
Because computers don't have unlimited memory.
Memory is limited.
So you would get a stack overflow error if you have no base condition.
So we have seen that recursion is just a function calling itself, which is what we have over here until
a base condition, which is what we have over here.
So that's pretty much what recursion is in very simple terms.
Now let's think of when to use recursion.
If you have to solve a problem, and if you can see that the problem at hand can be divided into smaller
subproblems.
And if solving these subproblems can help you solve the original problem, then probably you should
be using recursion now.
It's also many times the case that these smaller subproblems would be of similar nature, or they would
be similar to the original problem at hand.
Now what do I mean with that?
Let's take an example.
Let's say you are given n and you want to find n factorial.
Now, if your n is five five, factorial is nothing but five into four into three, up to one or n factorial
is just n into n minus one, into n minus two, etc. up to one.
Now if you want to find n factorial and you're given n or let's say for simplicity, let's say you want
to find five factorial, okay?
Or let's say n is equal to five.
As an example, notice that if you can find the answer to a subproblem, let's say that's four factorial.
Again, notice four is less than five and it's closer to the terminating condition or the base condition.
So if you can find the answer to four factorial, you can find the answer to five factorial using the
answer that you find which is four factorial.
Because five factorial is equal to five into four factorial.
And over here four factorial is the subproblem which is of similar nature to the original problem,
and solving the subproblem helps us solve the original problem.
So four factorial is 24.
Now using this 24, we can find the original problem's answer, which is five factorial, because five
factorial is equal to five into 24.
So if the question at hand has these type of characteristics, then probably you can solve it using
recursion.
Now, I know that this is a lot of theory, but we will do a lot of practice questions and this will
become second nature to you.
So don't worry about that.
But again, let's take it step by step and let's proceed.
So we have seen what recursion is.
And we have seen from a high level when to use recursion.
Now let's take a look at the pseudocode of this, what we just now discussed over here for n factorial.
To understand this in a better manner before we move ahead and try to visualize recursion.
So if I were to write the pseudocode of what we just now discussed over here, let's say I have a function,
you can call it factorial or anything to save space over here.
I'm not writing any name for the function.
And let's say we are calling the function with five because we want to find, let's say five factorial.
Now inside the function we have the base condition or the terminating condition that if n is equal to
one, just return one, because five factorial, as we discussed, is five into four into three into
two into one, and then node is after one.
You don't need to go further.
So that's why if n is equal to one, return just one.
And again we will discuss as we go ahead in this lecture how you can systematically think of coming
up with the base condition.
But for now, because this is a very simple question, it's intuitive that if n is equal to one, we
can just return one.
So that's what we have seen over here.
So that's the base condition that we have.
And what would be the recursive case.
The recursive case would be if n is not equal to one we just need to make the input smaller or call
the function again recursively by having the input closer to the base condition or the terminating condition.
So that would be return.
We could just return function n minus one into n, right.
So if you want to find factorial five factorial we are just returning four factorial into n.
So n in this case is five.
So we have seen that five factorial is five into four factorial.
So to get this four factorial, we are recursively calling the function again with the input as n minus
one.
And then to multiply this five over here we have n into this part over here.
So this over here is the recursive case.
So whenever you think of a recursive solution, always try to think of the base case and the recursive
case.
So we have discussed some interesting things over here.
Now in the next video let's try to visualize this.