Longest Common Subsequence — Recursion

The problem

Implement `lcsRecursion(stringA, stringB, lenA, lenB)`: return the length of the longest subsequence present in both strings. A subsequence preserves order but not adjacency — characters may be skipped, never reordered.

`"abcde"` and `"ace"` return `3` (`ace`). `"abc"` and `"abc"` return `3`. `"abc"` and `"def"` return `0`. Only the length is asked for; the subsequence itself needs the full table from two entries on.

The lengths arrive as parameters rather than being read off the strings, the same shape the knapsack recursion used. It's what makes the recursion expressible without slicing, and it's a small trap at the call site: nothing checks that `lenA` matches `stringA.length`, so passing a short value silently solves the problem for a prefix and returns a confidently wrong number.

The approach

The state is `(lenA, lenB)` meaning 'the LCS of the first `lenA` characters of A and the first `lenB` characters of B', and every step shrinks it from the right. The base case is either prefix being empty — an empty string shares nothing with anything, so `0`. Choosing to index from the end rather than carrying start offsets is what keeps the parameters as plain lengths, which is what makes them usable as array indices in the next entry.

When `stringA[lenA-1]` equals `stringB[lenB-1]`, the code returns `1 + f(lenA-1, lenB-1)` and explores nothing else. That's a real claim, not an optimisation: it asserts there is always an optimal LCS that pairs those two final characters. The exchange argument is short — take any optimal subsequence; if it doesn't use A's last character, the character it does match B's last character against sits earlier in A, and swapping in the later one keeps the length and the ordering intact. Since some optimal solution uses the pair, taking it can't lose.

When they differ, at most one of the two can be the endpoint of the answer, so the code branches on which one to discard and takes the max. Those two branches overlap heavily — both eventually descend into `(lenA-1, lenB-1)` — and that overlap is the entire repeated work. It's also the shape that tells you a memo table will help: the branches recompute each other's subproblems rather than partitioning the search.

The cost is `O(2^(m + n))` in the worst case, with `O(m + n)` of stack. The asymmetry between the branches is what makes this deceptive in testing: a match costs one recursive call and a mismatch costs two, so similar strings finish instantly and disjoint strings blow up. The naive version therefore looks fine on exactly the inputs you'd reach for while writing it, and falls over on the ones that arrive later.

Two small things in the code. The character comparison uses `==` where the length check four lines above uses `===`; both operands are single-character strings so the two are identical in behaviour here, but the inconsistency inside one function is the kind that gets copied. And the exported wrapper is currently a pure pass-through, adding nothing — it exists so that the public signature doesn't move when the memo table shows up in the next entry, which is a reasonable thing to set up early.

The solution

export function lcsRecursion(stringA, stringB, lenA, lenB) {
  return lcsRecursionHelper(stringA, stringB, lenA, lenB);
}

function lcsRecursionHelper(stringA, stringB, lenA, lenB) {
  if (lenA === 0 || lenB === 0) {
    return 0;
  }

  if (stringA[lenA - 1] == stringB[lenB - 1]) {
    return 1 + lcsRecursionHelper(stringA, stringB, lenA - 1, lenB - 1);
  }
  return Math.max(
    lcsRecursionHelper(stringA, stringB, lenA - 1, lenB),
    lcsRecursionHelper(stringA, stringB, lenA, lenB - 1),
  );
}

Time O(2^(m + n))Space O(m + n)