ITPEC FE Subject B October 2024 Question 7

Fill in the blanks for a recursive Longest Common Subsequence implementation.

The LCS algorithm compares two strings character by character from the end:

• •Base case: if either index is 0, return 0
• •Match: if str1[m] == str2[n], return 1 + lcs(str1, str2, m - 1, n - 1)
• •No match: return the maximum of two recursive calls — one reducing m, the other reducing n

In the else branch, the two calls must try all combinations of skipping one character:

So A = `n - 1` and B = `n`.

Why not others:
- (a) n, n − 1 — first call doesn't reduce any index (infinite recursion risk with m unchanged and n unchanged in that call)
- (b) n, n + 1 — increasing an index goes out of bounds
- (d) n − 1, n + 1 — increasing n is invalid
- (e) n + 1, n — increasing an index is never correct
- (f) n + 1, n − 1 — increasing an index is never correct

Key rule: In recursive LCS, when characters don't match, each branch must reduce exactly one index by 1 while keeping the other unchanged.

AI-generated — may contain errors