javascript - 最长公共(public)子序列(为什么这个递归解决方案不起作用？)

Question

尝试编写与以下描述的类似的递归解决方案:http://www.geeksforgeeks.org/longest-common-subsequence/，但它不起作用。它输出一个。有人知道为什么吗？

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")

Answer 1

在 JavaScript 中，与(例如)Python 不同，在函数内分配变量不会将其隐式声明为局部变量。相反，您需要使用 var 关键字显式声明它；否则你会得到一个全局变量。

更具体地说，您的问题是这一行:

    res_1 = LCS_seq_req(str1_cut, str2)

具有改变全局变量str2_cut的副作用，导致这一行:

    res_2 = LCS_seq_req(str1,str2_cut)

计算出错误的值。如果您在正确的位置添加 var，您将得到正确的答案。

<小时/>

顺便说一句，Eric Lippert 写了一篇博文，https://ericlippert.com/2014/03/05/how-to-debug-small-programs/ ，它为如何自行调试此类问题提供了非常好的建议。