CODEWITHSUNDEEP
javascriptrecursion
gskang
gskang

Reputation: 27

Longest common subsequence (Why does this recursive solution not work?)

Trying to write a similar recursive solution to the one described on: http://www.geeksforgeeks.org/longest-common-subsequence/ but it does not work. It outputs one. Anyone have an idea of why?

LCS_seq_req = (str1, str2) => {

  m=str1.length;
  n=str2.length;

  str1_cut = str1.slice(0, m-1)
  str2_cut = str2.slice(0, n-1)

  if (m===0 || n===0) {
    return 0
  }
  else if (str1.slice(m-1, m) === str2.slice(n-1, n) ) {
    return  LCS_seq_req(str1_cut, str2_cut) + 1
  } else {
    res_1 = LCS_seq_req(str1_cut, str2)
    res_2 = LCS_seq_req(str1,str2_cut)

    return Math.max(res_1, res_2)
  }

}
LCS_seq_req("AGGTAB", "GXTXAYB")

Upvotes: 0

Views: 469

Answers (2)

Sangbok Lee
Sangbok Lee

Reputation: 2228

I looked at the Naive recursive Python implementation of LCS problem you give and converted Python code into JS code. Hope it will help.

LCS_seq_req = (str1, str2, m, n) => {
  if(m == 0 || n == 0)
    return 0;
  else if(str1.charAt(m-1) === str2.charAt(n-1))
    return 1 + LCS_seq_req(str1, str2, m-1, n-1);
  else
    return Math.max(LCS_seq_req(str1, str2, m, n-1), LCS_seq_req(str1, str2, m-1, n));
}

var X = "AGGTAB";
var Y = "GXTXAYB";
console.log(LCS_seq_req(X , Y, X.length, Y.length));  //6

Upvotes: -1

ruakh
ruakh

Reputation: 183466

In JavaScript, unlike (say) Python, assigning to a variable inside a function does not implicitly declare it as a local variable. Instead, you need to explicitly declare it using the var keyword; otherwise you get a global variable.

More specifically, your problem is that this line:

    res_1 = LCS_seq_req(str1_cut, str2)

has the side-effect of mutating the global variable str2_cut, causing this line:

    res_2 = LCS_seq_req(str1,str2_cut)

to compute the wrong value. If you add var in the right places, you'll get the right answer.

Incidentally, Eric Lippert has written a blog post, https://ericlippert.com/2014/03/05/how-to-debug-small-programs/, which gives very good advice for how to debug this sort of problem on your own.

Upvotes: 2

Related Questions