Let's now get into the code and write the recursive solution for solving the longest common subsequence
question.
So again this is going to be a recursive solution.
And we would need a helper function.
Let me just call it helper itself.
And to this function we will be passing index one and index two.
So these are two variables which will indicate the indices in text one and text two respectively that
we want to compare.
Okay.
So again let's write the details of this function later.
But we will write this function in a way that this will return the longest common subsequence okay.
So it will return the length of the longest common subsequence.
And over here we would have to call this function for the first time.
And when we call it for the first time, we either will be passing the first index for text one and
text two, or the last index for these two texts.
And again, it depends on how we write the recursive solution.
We have discussed many times that you can write the recursive solution, either going from zero to the
last index, or going from the last index to zero.
Okay.
Now over here, let's go from zero to the last index.
And therefore I will be passing zero comma zero.
And we can just in fact return whatever we get over here.
Because as we have mentioned this function over here, the helper function will return the longest common
subsequence.
So this is the skeleton of the approach that we are going to implement.
Now let's go ahead and write the details.
So for the helper function we will be writing the base case as well as the recursive case.
Now when it comes to the base case, as we have discussed in the previous video, it would be the case
when we are encountering the first invalid input.
And because we are going from zero to the last index, the invalid input would be the case where we
are going beyond the last index.
Okay.
So again over here let's define the length of text one and text two.
So let's say const n is equal to text one dot length and const m is equal to text two dot length.
Now over here, if index one is greater than or equal to n, then we would have hit an invalid input
okay.
And that would be the base case.
And in the case of text two that would be if index two is greater than or equal to m okay.
So if we have hit the base case then we can just return zero.
Because either of these texts, either text one or text two, does not have any more characters.
And if that is the case, there would be nothing in common between the two texts, right?
For example, let's say text one is a, b, c, and let's say text two is a, b, d, e f.
Now if we reach over here, which is beyond the last valid index for text one and for text two, if
we are over here, notice that we are actually comparing an empty string and f, and between these two
there are no common characters.
And that's why we can return zero over here.
Okay, now let's proceed to the recursive case.
What we will be checking over here is we will check if text one at index one is equal to text two at
index two.
So if these two are equal then we have found a common character.
And therefore we will just return one plus whatever we get when we call the helper function with higher
index one and index two.
So to this recursive call to the helper function, we will pass the inputs as index one plus one and
index two plus one.
Okay, now if this is not the case then as we have discussed we would have to increment only one index
at a time.
So we'll have to recursively call the helper function.
And in one case we will only increment index one.
And we will keep index two as it is.
And in the other case we will only increment index two.
So index one would be kept as it is.
And for index two we would pass index two plus one.
Okay.
Now between these two whichever gives us the higher value.
That would be what we return in this case okay.
And we have discussed this in detail in the previous video.
So over here let's return math dot max.
And the maximum between what we get over here and over here okay.
And that should be it.
This should help us solve the question.
Now let's go ahead and run this code and see if it's passing all the test cases.
And you can see that it's working.
It's passing all the test cases.