Is there any solution for "too close to the limit" error while finding the longest common sequence?

Question

I'm tryin to find the longest common sequence between two very long sequences, but it gives an error "C stack usage 15924368 is too close to the limit" Here is the code:

lcs <- function(X, Y, m, n, dp) {
  if (m == 0 | n == 0) {
    return(0)
  }

  if (dp[m, n] != -1) {
    return(dp[m, n])
  }

  if (is.na(X[m]) == is.na(Y[n])) {
    dp[m, n] <- 1 + lcs(X, Y, m - 1, n - 1, dp)
    return(dp[m, n])
  }

  dp[m, n] <- max(lcs(X, Y, m, n - 1, dp), lcs(X, Y, m - 1, n, dp))
  return(dp[m, n])
}

dp <- matrix(-1, nrow = nchar(a) + 1, ncol = nchar(b) + 1)

longcs= lcs(a, b, nchar(a), nchar(b), dp)

and also is there any way to see the string? This code shows only the number.

Answer 1

I guess it would be better to avoid using the recursion for LCS, since R seems to have some limitations on the depths of recursions, and recursions are slow sometimes (especially when you need to copy large arguments that would not result in a copy in an iterative implementation, see the comment from @Konrad Rudolph).

---

If you have relative short strings X and Y to find the LCS, probably you can try the code below

• If you want to conut the length of LCS substring

lcsCnt <- function(X, Y, m, n, cnt = 0) {
    if (m * n == 0) {
        return(cnt)
    }
    if (substr(X, m, m) == substr(Y, n, n)) {
        cnt <- Recall(X, Y, m - 1, n - 1, cnt + 1)
    }
    return(max(cnt, Recall(X, Y, m, n - 1, 0), Recall(X, Y, m - 1, n, 0)))
}

• If you want to display the LCS substring

lcsStr <- function(X, Y) {
    if (nchar(X) * nchar(Y) == 0) {
        return("")
    }
    x <- substr(X, 1, 1)
    xs <- substr(X, 2, nchar(X))
    y <- substr(Y, 1, 1)
    ys <- substr(Y, 2, nchar(Y))
    if (x == y) {
        return(paste0(x, Recall(xs, ys)))
    }
    s1 <- Recall(X, ys)
    s2 <- Recall(xs, Y)
    ifelse(nchar(s1) > nchar(s2), s1, s2)
}

---

Example

> a <- "xstacky"

> b <- "@stack&over)flow//"

> lcsCnt(a,b, nchar(a),nchar(b))
[1] 5

> lcsStr(a, b)
[1] "stack"