Recursion

Recursion is a programming technique that involves solving a problem by breaking it down into smaller subproblems. In the context of the Longest Common Subsequence problem, recursion can be used to find the length of the longest common subsequence between two strings.

Let's take a look at a recursive approach to solve the Longest Common Subsequence problem:

1public class LongestCommonSubsequence
2{
3    public static int FindLCS(string str1, string str2)
4    {
5        return FindLCSRecursive(str1, str2, 0, 0);
6    }
7
8    private static int FindLCSRecursive(string str1, string str2, int index1, int index2)
9    {
10        if (index1 == str1.Length || index2 == str2.Length)
11        {
12            return 0;
13        }
14
15        if (str1[index1] == str2[index2])
16        {
17            return 1 + FindLCSRecursive(str1, str2, index1 + 1, index2 + 1);
18        }
19        else
20        {
21            int length1 = FindLCSRecursive(str1, str2, index1 + 1, index2);
22            int length2 = FindLCSRecursive(str1, str2, index1, index2 + 1);
23            return Math.Max(length1, length2);
24        }
25    }
26}
27
28string str1 = "AGGTAB";
29string str2 = "GXTXAYB";
30int longestCommonSubsequence = LongestCommonSubsequence.FindLCS(str1, str2);
31Console.WriteLine("Longest Common Subsequence: " + longestCommonSubsequence);

In the above code, we define a LongestCommonSubsequence class that contains a FindLCS method to find the length of the longest common subsequence between two strings. The FindLCS method calls the FindLCSRecursive method, which takes two string parameters, str1 and str2, and two integer parameters, index1 and index2, representing the current indices in str1 and str2 respectively.

If the current indices reach the end of either string, we return 0, indicating that there are no more elements to consider in the subsequence. If the characters at the current indices are equal, we increment the length by 1 and recursively call the FindLCSRecursive method with the incremented indices. If the characters are not equal, we make two recursive calls, one with the incremented index in str1 and the same index in str2, and the other with the same index in str1 and the incremented index in str2. We then return the maximum length from these two recursive calls.

Let's see how this recursive approach works for finding the longest common subsequence between the strings "AGGTAB" and "GXTXAYB":

1string str1 = "AGGTAB";
2string str2 = "GXTXAYB";
3int longestCommonSubsequence = LongestCommonSubsequence.FindLCS(str1, str2);
4Console.WriteLine("Longest Common Subsequence: " + longestCommonSubsequence);

When we run the above code, it will output:

1Longest Common Subsequence: 4

In this case, the longest common subsequence between "AGGTAB" and "GXTXAYB" is "GTAB", which has a length of 4.

Recursion is a powerful technique for solving problems, but it can be inefficient in some cases. In the next section, we will learn about dynamic programming, which can optimize the solution for the Longest Common Subsequence problem.

xxxxxxxxxx

Console.WriteLine("Longest Common Subsequence: " + longestCommonSubsequence);

public class LongestCommonSubsequence

{

    public static int FindLCS(string str1, string str2)

    {

        return FindLCSRecursive(str1, str2, 0, 0);

    }

​

    private static int FindLCSRecursive(string str1, string str2, int index1, int index2)

    {

        if (index1 == str1.Length || index2 == str2.Length)

        {

            return 0;

        }

​

        if (str1[index1] == str2[index2])

        {

            return 1 + FindLCSRecursive(str1, str2, index1 + 1, index2 + 1);

        }

        else

        {

            int length1 = FindLCSRecursive(str1, str2, index1 + 1, index2);

            int length2 = FindLCSRecursive(str1, str2, index1, index2 + 1);

            return Math.Max(length1, length2);

        }

    }

}

​

string str1 = "AGGTAB";

string str2 = "GXTXAYB";