JS 递归代码抛出最大调用堆栈大小错误

Question

我知道这可能是基础和简单的，但由于我是自学的，所以我想知道哪里出了问题，我认为这是最好的学习场所。

我正在尝试编写 return 为真或为假的递归代码。检查的条件是单词集是否可以组成给定的目标单词。

我不断收到的错误是：

 if (targetString.indexOf(dictionary[i]) == 0) {
                     ^

RangeError: Maximum call stack size exceeded
    at String.indexOf (<anonymous>)

我很确定代码的问题在某种程度上是我 returning 因为我总是觉得它很混乱。

我的代码是：

let targetString = "furniture";
let dictionary = ["fur", "ure", "nit"];
const tableData = {};

const canConstructRecursive = (targetString, dictionary) => {
  if (targetString == "") {
    return true
  }

  for (let i = 0; i < dictionary.length; i++) {
    if (targetString.indexOf(dictionary[i]) == 0) {
      shorterTargetString = targetString.slice(0, dictionary[i].length);
      return canConstructRecursive(shorterTargetString, dictionary);
    }
  }
  return false;
}

console.log(canConstructRecursive(targetString, dictionary));

我在学习递归，时不时感觉不懂return到next/previous递归调用的逻辑

如果有人能帮助我解决我做错的事情并改变我的思维方式，我将不胜感激。

我的想法是：

如果在那个阶段达到基本情况，则基本情况是 returned 否则循环遍历所有选项并且内部节点或上层堆栈需要 return 值到下层堆栈所以我是在里面做 return canConstructRecursive() 。如果即使在所有for循环的所有迭代的选项中，它都不是returned，最后还有return false。

提前致谢

Answer 1

原因是虽然你的变量名为shorterTargetString，但并不保证真的更短。如果 i 是 dictionary 中最短单词的索引，那么你的字符串不可能通过递归来变短。

错误是切片不应该start在0，而是after被匹配的部分，所以去掉第一个参数来自 slice 电话。

这将解决堆栈溢出错误。

其次，如果递归调用returns false你不应该放弃，而是继续尝试下一个单词。所以当你从递归中得到 true 时，只有 return 退出循环：

let targetString = "furniture";
let dictionary = ["fur", "ure", "nit"];
const tableData = {};

const canConstructRecursive = (targetString, dictionary) => {
  if (targetString == "") {
    return true
  }

  for (let i = 0; i < dictionary.length; i++) {
    if (targetString.indexOf(dictionary[i]) == 0) {
      shorterTargetString = targetString.slice(dictionary[i].length);
      if (canConstructRecursive(shorterTargetString, dictionary)) {
         return true;
      };
    }
  }
  return false;
}

console.log(canConstructRecursive(targetString, dictionary));

关于第二个修复的更多信息。

您的代码将无条件地 return 递归调用的值，即使它是 false。这不好：如果递归调用 returns false，调用者应该继续其 for 循环来尝试替代方案。

例如，我们向您的示例词典中添加一个单词：您会同意添加一个词典单词不应更改输入“家具”的结果。所以这里是：

["furn", "fur", "ure", "nit"]

但令人惊讶的是：您的代码现在 returns false 用于“家具”！这是因为“furn”数学，但是以“iture”作为第一个参数的递归调用没有找到进一步的匹配，所以它 returns false，现在调用者 also returns false。这是错误的。它应该放弃“furn”，而不是整个练习。它应该继续并尝试使用“毛皮”。这就是为什么退出 for 循环只应在成功时发生，而不应在失败时发生。只有全部个字典词都试过才能确认失败，所以for循环必须一直继续下去，只要没有递归成功。

Answer 2

用户 trincot 已经解释了您的代码有什么问题。在这里，我只想指出您的结构，类似于 for (...) {if (...) { if (...) {return true} } } return false，用 Array.prototype.some 和 && 语句可能会更好地处理。结合 t .indexOf (s) == 0 可能更清楚地表示为 t .startsWith (s) 的事实，并加入条件语句而不是 if 语句，我们可以得出我认为更优雅的结果公式：

const canConstruct = (t = '', ss = []) => 
  t == ''
    ? true
    : ss .some ((s) => t .startsWith (s) && canConstruct (t .slice (s .length), ss))

console .log (canConstruct ('furniture', ['fur', 'ure', 'nit'])) //=> true
console .log (canConstruct ('furniture', ['furn', 'fur', 'ure', 'nit'])) //=> true
console .log (canConstruct ('banana', ['b', 'ana'])) //=> false
console .log (canConstruct ('banana', ['ba', 'na'])) //=> true

JS 递归代码抛出最大调用堆栈大小错误

JS recursive code throwing maximum call stack size error

javascript

algorithm

recursion

data-structures

关于第二个修复的更多信息。