Hello everyone and welcome back.
So in this video we're going to continue our discussion on recursion.
And I'm going to tell you about how we can deal with recursion questions whenever we are given an array
or a list.
So with respect to Python I think list also makes a lot of sense.
So let us make it list.
Now the basic understanding remains the same if you actually will think list or an array, right?
It is actually also something which we can break into a smaller problem.
Okay.
So we have to actually find out ways.
We have to find out ways that how we can break a list or basically given an array.
So I will be using them interchangeably.
You can actually just think that it is a homogeneous I would say case.
Right.
So you have to just actually think that how we can handle or make our problem smaller.
With respect to a list, a very good example of this, which we are also going to move further, is
that we can actually check if our arrays is sorted or not And make it even break into different parts.
Right.
So if I have given you a particular list or array and if somehow okay, you can check for a single element
if that is in correct order, maybe just by checking it's the element on the right or left, then you
can actually say and ask to do the other work.
And that is something which I have written is when whenever in arrays, we are dealing with a problem
that can be broken and individually apply to leftover part that is making the problem smaller, right?
This all is nothing but making the problem smaller.
The basic idea of our recursion.
We can use recursion there.
Okay, now majorly.
I will also be making sure to do some questions with you.
But before that, I want to actually give you an idea that how we divide our list or array.
Right?
So the very first way to divide a particular list or array is that we can actually work on the first
element or the last element and let recognition take care of the rest.
Right.
So normally here also the use case is gonna like the flow or the framework is gonna be the same.
We are first going to get and write a base case.
Okay.
So majorly that would be around if our size of our array is 0 or 1.
Like for example for a sorted problem, if the size of an array is 0 or 1, then of course that is sorted
right.
You don't need to check on that.
Then I will actually be picking up one of the elements and I will be working on that.
Like for example, let's say if I'm picking up the first element, I will be working on this particular
element.
We'll check that okay.
If it is smaller than this particular number, because if it is smaller, then that basically means
that this is at the right position.
And then I can call my recursion and ask it to get the answer for this particular or leftover array.
Right.
The same thing.
The same thing I can actually even do, I can do for my from my last element as well.
So nothing is changing, just I'm working on single element only still.
Just that I'm picking up the last element so I am able to actually break down my problem.
Now if this particular array will be sorted, this array or list.
And I have also made sure that this is also sorted.
Then I can of course write that the whole array is sorted.
Okay, so that is one of the way.
The second way actually stems from using the start or the end index.
Now the example for this is very good.
Example is binary search where we actually divide by I would say taking a medium okay.
Now in the start and end index we will be doing lots of questions in merge sort and quicksort.
Specifically they will be used a lot.
You have to understand one thing that sometimes it happens that we are dividing our arrays into two
parts.
And this is all I am just giving you as an introduction.
We will of course be doing lots of questions in this particular segment so that you are able to understand
each and every thing very effectively.
Okay.
There is a reason that I have created a separate section because as of now, now you have actually understood
everything with respect to the basics of recursion very well.
Head recursion, tail recursion, when to call, how to take the base case PMI in its extended form
and you are good to solve the basic and I would say major questions of your, uh, Recursion by using
that.
But whenever we are including list or an array, these are the common techniques which we will be using.
Okay, so the second technique is when we use start and end index.
So again this is just us breaking the problem smaller okay.
And this time I'm just basically asking.
So for a very good example can be actually I would say your binary search where I will be first looking
at the middle element based on that middle element.
I cannot take the call if I want to search in this half or this half.
Now to tell my particular function that, okay, how to look at a particular half.
I believe that this is a very good point.
If I am able to give a start and end index so I can ask it that, hey, start from here and end from
end till here, that is something now which will actually be some like way I have broken down my problem
and which recursion can work upon in a very similar way.
Of course I can break it down in separate parts as well.
So s1e1 and maybe let's say s2, e2 okay, get something which we have all kind of seen merge sort.
So don't worry on this.
I'm going to explain you properly, but I'm giving you these techniques.
I would say so because of two reasons.
First is you will also be then able to think a little bit on the solution, okay.
Because you will be aware that, okay, what are the common frameworks or techniques we follow.
Second is that whenever you are given a question in your interview, you will have some steps to actually
look forward to and you will be able to apply them and then take that call.
So in that way this is a lot helpful.
That is the exact reason, like when I, uh, taught like teach you two pointers, they also give you
all the different, different I would say techniques or uh, ways we can actually approach a two pointer
problem.
Okay.
Now moving forward, the last part is actually very analogous to the second part only.
But in this, instead of giving the start in the index, we will actually be just copying the array
like making a new array.
So like what I can do is from this particular thing I can make a new array and I can then send this
particular array.
Okay.
So let's say if I am just uh, checking if this is sorted or not, then again I can do this.
I can create a new array and send that to my function and it can return me.
Okay.
If it is sorted or not.
So this is actually just I would say an extension majorly.
We will try that.
We are able to write the second code.
I am going to teach you about complexity, specifically time and space complexity.
So in with that we will learn that why the second implementation is better.
And I think you can see the same as well.
Right.
We will be making so many of these arrays.
But again this is also some approach we should be aware of.
And that helps you to solve a question a little easily.
So in the initial when we will be solving the question, I might ask you to create a new array or list
by basically copying the elements.
Of course it is very easy in Python by just using the slicing I would say method.
And then we will move to the second part where we are giving the proper start and end index majorly.
We will see that most of the question we will be very good to solve by using this particular approach
in your, I would say, recursion with arrays.
And of course, if any particular other question will be there, we should be good to solve with our
basics as well, so you don't have to worry on that right now.
Let us solve one question.
Now let us solve one question so that the concepts are a lot more clear.
So the question is.
Write a program.
To check if A is sorted.
Okay.
Let me actually extend this question a little bit so that you are able to understand lots of things.
So we are also going to use recursion.
Of course we are going to write the recurrence relation.
We are going to write the recurrence relation.
And also make the recurrence uh basically recursion tree.
And let us solve it using both head and tail recursion.
So this will of course, be a very good refresher for all the things which we have learnt till now.
Okay, so this is one question where actually, of course it doesn't matter the way you are checking,
but we will see what is better in this particular case as well.
So yeah, I would like actually want you to try this question out first.
And in the next video I'm going to discuss the answer.
And I will actually be making all these things so that you can follow the overall thought process.
You can understand the same.
Again, I will repeat this one more time.
Please make sure that you are understanding and following the thought process, because if you actually
understand stuff, then you will be able to solve novel questions, any new question and be a better
coder and software engineer going forward.
Don't just stand behind the solution if you actually are.
I would say following everything, you will for sure feel that you have to understand and make sure
that you understand the basics and how to approach a problem rather than just, I would say, jumping
on the solution.
So please make sure that you follow that particular framework and understand the problem.
And in the next video, I'm going to make sure that I solve this in front of you so that you get a better
idea as well.
Okay, cool then.
Thanks a lot everyone.
Let's meet in the next video.