Hello all and welcome back.
So in this video we are going to continue our discussion on recursion and arrays.
And we're going to solve the question on the screen to check if an array is sorted as.
The same will help us to better understand how to approach questions when we are dealing with list or
array in a recursion.
So let's get started.
So the question is actually in front of us.
The question asks us to check if a array or a list basically is sorted, but we have to do the same
using recursion and have to also define a recursion relation recursion tree.
And of course do that same via head or tail recursion.
So let us try to first do it and define go to the code.
So def check sorted.
Let's say I will be getting a list which can be r or let me make it L1.
And for the time being let me pass 2579 ten maybe.
So this works fine right?
So we will be checking if this particular list.
We can see that it is sorted.
We have to check the same recursion right.
So let us break down this problem.
The way we break down each and every of I would say recursive problem.
The very first one is the base case.
So base case.
As of now I think I have already discussed in the last class as well.
And I'm making sure that in this course I'm giving you lots of practical examples and then explaining
the concepts.
So please make sure that you also solve and think in this particular manner.
Only the base case is actually when size is equals to one or size equals to zero.
Because if you actually think about it, if the size is equals to 0 or 1, then for sure the array will
be sorted, right?
Like there is no way it can not be sorted in that way.
So we can just quickly write the same as well.
So what I can do is if my L1 dot sorry length of my L1 equals zero or length of my L1 equals one, then
I can just return true.
Okay, so we should just print the same as well.
So we get our answer.
I can just return true.
Now, if we actually think of the next step, it is on making the recursion call, right?
Recursion call or I would say or.
Induction hypothesis or recursive call.
I think it makes sense that I can ask my recursion.
I can ask my recursion to check.
If so, I hope you have done slicing very nicely everyone.
So we can slice our list like this.
Right?
So let me just maybe.
Yeah, just for the time being, what I want to show is like, let's say if my list is one, two, three,
four, five.
Now if I print l two of.
One and all this this is going to slice my list.
Right.
So you will see 2345.
The reason for that is it's this is a zero index.
Then first index.
And what exactly is happening is that I am just taking all the elements starting from first index.
So this has been very nicely covered in the same I would say course in slicing.
So please make sure that you see that once.
So I will be sending my list.
I will be sending my list but we'll be removing the first element.
So I am actually making sure that I am working on the first element.
And then of course, yeah, like the recursion can take care of the rest, right?
So let's say I get my answer here.
Let's say I get my answer here because I'm returning something.
So it's good if I catch the same as well.
Now if we pay attention can we now return this answer.
Can I return my this answer?
I think no, right.
Because I have not done my work as of now.
I have not done or I have not checked.
So, for example, what would have happened is that in the recursion call, we would have sent these
elements and let us say it would have returned.
True.
Now you don't have to question how you will get this as true.
That is something which I have been stressing upon a lot.
The same will follow on recursion with arrays as well arrays or list as well.
You don't have to question once you have written and made this call.
The beauty of the framework.
The way I'm explaining you, you do not need to question that.
You just need to write your logic.
Now, if your answer is true, right, that will be still.
You need to check for this first element.
Okay, still you need to check for this first element.
Now in the case when this is two of course your whole array is sorted.
But what if the this particular element is ten.
Then of course your answer should be false.
Right?
So and to just show you what the problem will be if we just return it as of now, let me run it.
We are getting it as true.
And if I run it now, we are again getting it as true.
So it is saying that yes, this, this array is also sorted.
But I think we can see the same.
Right.
This is not sorted at all.
So what exactly we have to do is we have to also make sure that we are doing our work as well here.
So if L1 of zero okay.
So I am just thinking in terms of this list, the list which I have, I do not care what recursion would
have done.
Let me first write the code and then we can think on that.
Okay, if this is less than the first element, if this is less than the first element, then I can
just return whatever.
I am getting the answer right.
I can just return whatever I am getting as answer.
Else I can return false.
I can return false.
See, I can write else here that would be helpful if this is true.
If this is actually happening and you can just check for equal to as well, I am taking strictly sorted.
So if this is two and two it is not sorted in my terms.
But if the question requires like that then you can put equal to here as well.
So it is returning you the answer right.
It is returning the answer as it is.
Because see this is true.
It won't have any effect.
If the answer will be true, then it will remain true.
If the answer will be false, then it will remain false.
Okay, but when this is not true, then of course my answer is surely going to be false, right?
So that is why I am returning false here and now.
This code is going to work perfectly well.
But first let me actually write.
And first let me actually make that a recursion tree.
And then it will be making sense to check for this.
Right.
So let me make the recursion tree for you now everyone.
So this is actually going to be my array.
This is going to be my array 257.
I think it was nine and ten, right?
Two.
Five.
Seven.
Nine and ten.
Right.
So first I am making a call.
First I am making a call.
But this time I am just sending five, seven, nine and ten.
In the next I am also again making.
All this time I am just sending seven, nine, ten again.
I will be making a call, just sending nine and ten.
And finally one of my last function is going to just get the element ten.
Now when it gets the element ten, I have written in the base condition that you are sorted right.
If you have just a single element, then for sure it makes sense that you are going to be sorted and
it is going to return true.
Now this second last function, what it is going to do is it is before returning the answer.
The way I have written my logic right, the way I have written my logic, and I am making this all on
the nodes so that you also get this and you are able, better able to revise everything.
The way I have written my logic, it will before returning this answer, or before even changing this
answer.
It is going to check if L1 zero is greater or less than L1 of one.
In this particular case, this is the list and nine does seems to be less than ten.
So it's actually also going to return true only.
Now this function is going to check for seven less than nine because this is zero one and two here.
And it is going to return true again.
In a similar fashion you can see that five is less than seven.
So this is also going to return true.
And now finally my two is less than five.
So it is also written as true whichever I was getting.
And the final answer is true.
Now again I did not think of any of this while I was writing the code.
I just made my problem smaller and assumed that recursion is going to work fine, and I am able to write
the code perfectly while using the same thing.
And you can, as you can see on the screen, right?
As you can see on the screen.
So if I am running it for 25, seven, nine, ten, it's going to be this way.
Now you can just quickly think that if this is 20, if this 20 is here, then of course this condition
will fail and I will be sending false.
If let's say this would have been 90, then I would be sending false from here.
And basically what would have happened is that each and every value would have been false only okay.
So it will be returning false false false.
The false would have propagated to the top.
Okay.
So I hope this is clear.
Now I am just going to copy this whole function and make your understanding a little bit more better
okay.
So check 42 I am writing it now.
Just one thing I want to actually understand is that don't you think that if, let's say the case was
if, let's say.
The case was something like 25, seven, nine and ten.
Now, don't you think here that you should first do your work?
Because let's say if the first element is not only sorted, the first element is 20 and five is not
only sorted.
Why should we make function calls.
Deep down I would say to all the methods.
All these functions, let's say if this would have been a thousand, uh, long, uh, array.
Right.
1000 long array or list, you would have created 1000 such functions where the first and the foremost,
like you are able to see that, hey, this is not sorted, but still you are waiting for everyone else
to get the answer.
So what I am actually kind of trying to explain is that in this particular case, as I have already
explained to you, that we can also do our work before and for this particular question, don't you
think that we should do something like this?
So what I am telling you is that we should first do our work and check.
So if my L1 of zero, if my L1 of zero is less than L1 of one, then this means that my particular case
is sorted, right?
This means that my particular this point, the one which I have to take care.
This is sorted right?
And if this is sorted, if this is sorted then I can return.
Check sorted to L1 One, right?
So I am just asking that.
Hey, I have checked for myself.
This is sorted.
Please just get the answer, okay?
And if this is not sorted then I should be good to return false.
So this is a little bit better implementation in a way that and the reason for this is pretty straightforward.
And I can show you that as well.
So let me make L two is equals to I for I n.
Again this is a I think you have an idea.
This is list comprehension.
So pretty sure that you have learned about this as well okay.
So range.
Okay.
So let me just show you what L3 is.
L3 is a very big list starting from 10,000 something.
Now see if I send L3 in this particular question.
If I send in my check sorted if I send L3 okay.
Or let me just write this here I am I'm getting that recursion depth is exceeded because it will be
trying to make 10,000 such functions, right?
This thing will be making 10,000 times, but if on the similar side I call just check 42, it's going
to give me the answer.
The reason is that I am making sure that I am able to do my work first, and I am able to handle such
large input as well.
The very first one is of course not sorted.
It's 10,000 and then nine, nine, nine nine, so it is going to return false in the very starting only
it doesn't have to create all those functions.
Okay.
So this is actually the very good implementation.
You can even make it a little bit more better.
So you can just check if it is going to be false.
You can just check if it is not following this particular thing.
And then you can just help and use call this particular thing on this like this.
Right.
So proper use case of recursion where you are just calling this okay without any accumulator or anything
because you are returning this answer.
But yes you are.
Just call this you have done all your work, you have checked for yourself.
Okay.
And because you have checked it, you don't need to.
Now do anything.
Whatever the answer is coming, you can just return that.
Okay.
So I hope this overall understanding now overall both and every cases are clear.
So in how you can do the same thing.
This is kind of a recursion tree as well.
Okay.
This is a recursion tree as well.
To talk about the recurrence relation it can actually be something like this.
So recurrence relation is going to be something like this where let us say to check sorted.
Okay.
Check sorted.
A particular L1 what we can do is we can just write L1 of zero less than L1 of one.
And we are going to call check sorted.
On L1 and the rest of the list.
Right.
So this overall basically is kind of a recurrence relation.
And the above is like of course we can draw the notes in circle form and this will actually tell you
a tree.
Again here this.
The call is getting made in a single I would say direction.
So that is fine.
You can draw it like this as well.
But you should actually be able to understand.
And after understanding you should see that okay.
If you can able to write this in a tail recursion for if you are able to actually follow this or you
can do some optimization or not.
So that is what my overall expectation from you will be if you are trying to, I would say code this
kind of a solution.
Again, these are easy questions as of now.
Yes, we can do them via iteration as well, but I want to make sure that I first hone your skills on
these kind of questions so that when we will be discussing difficult questions moving forward, you
will be actually feeling them very easy because you have a kind of learn, I would say, recursion in
a very step by step manner.
Okay, so great everyone.
I hope this is clear as well.
In the next class now we are going to discuss another question.
I am going to help you to do another question in a similar manner, and that will help you in understanding
recursion with list or arrays a lot better.
Okay.
So thank you very much everyone.
Let's meet in the next video.
Thank you.