递归：当可能有多个子路径时，跟踪所有递归路径中的变量

Question

我正在尝试计算一个模式作为字符串的子序列出现了多少次，并且还保留了匹配发生的索引。

使用递归调用计数很容易。

function count(str, pattern, strInd, patternInd) {
    if (patternInd === 0) {
      return 1;
    }

    if (strInd === 0) {
      return 0;
    }

    if (str.charAt(strInd - 1) === pattern.charAt(patternInd - 1)) {
      const count1 = count(str, pattern, strInd - 1, patternInd - 1);
      const count2 = count(str, pattern, strInd - 1, patternInd);
      return count1 + count2;
    } else {
      return count(str, pattern, strInd - 1, patternInd);
    }
  }

为了保留索引，我的逻辑是在模式字符与字符串字符匹配时在递归调用中将 str 的当前索引推送到 "local indices array"，一旦模式完成，推送"local indices" 到 "global indices" 并为下一个递归路径重置 "local indices"。

重置本地索引是我面临的问题：

function count(str, pattern, strInd, patternInd) {
    if (patternInd === 0) {
      // when this path ends, add to list the indices found on this path
      globalIndices.push(localIndices);
      // reset the local indices
      localIndices = [];
      console.log("found");
      return 1;
    }

    if (strInd === 0) {
      return 0;
    }

    if (str.charAt(strInd - 1) === pattern.charAt(patternInd - 1)) {
      localIndices.push(strInd);
      const count1 = count(str, pattern, strInd - 1, patternInd - 1);
      const count2 = count(str, pattern, strInd - 1, patternInd);
      return count1 + count2;
    } else {
      return count(str, pattern, strInd - 1, patternInd);
    }
  }

这样它会在每次分叉后丢失之前的路径信息，因为一旦匹配的子路径被消耗，它就会从 localIndices 中删除，并且 localIndices 在分叉发生后开始跟踪匹配。

例如，str 是 "abab"，pattern 是 "ab" 然后我想 globalIndices = [[4,3], [4,1], [2,1]] 但是我会得到 [[4,3],[1],[2,1]]

我想重置"local indices"到之前的分岔点。

我的方向是否正确，或者这类问题是否需要完全不同的实施方式？

Answer 1

首先，当你收集索引时，你不需要保留一个计数，因为最终数组的长度将是计数：每个数组元素将对应一个匹配项，并且是一个列表相关指标。

您可以使函数的 return 值成为（部分）匹配的数组，并在回溯时使用额外的索引扩展每个数组（当该字符出现在匹配中时）：

function count(str, pattern, strInd = str.length, patternInd = pattern.length) {
    if (patternInd === 0) {
        return [[]]; // A match. Provide an array with an empty array for that match
    }

    if (strInd === 0) {
        return []; // No match. Provide empty array.
    }

    if (str.charAt(strInd - 1) === pattern.charAt(patternInd - 1)) {
        const matches1 = count(str, pattern, strInd - 1, patternInd - 1);
        const matches2 = count(str, pattern, strInd - 1, patternInd);
        // For the first case, add the current string index to the partial matches:
        return [...matches1.map(indices => [...indices, strInd-1]), ...matches2];
    } else {
        return count(str, pattern, strInd - 1, patternInd);
    }
}

console.log(count("abab", "ab"));

请注意，索引是 zero-based，因此它们比您提到的预期输出少一个。另外，索引是从左到右排序的，这似乎更有用。

总体思路

通常最好避免使用全局变量，并尽可能使用递归函数的 return 值。您从中得到的结果只会涉及递归调用访问的 "subtree" 。在上面的例子中，该子树是字符串和模式的较短版本。什么递归函数returns 应该和传递的参数一致（应该是那些参数的"solution"）。

Return 值可能很复杂：当您需要 return 多于 "one thing" 时，您可以将不同的部分放在一个对象或数组中，然后 return那。然后调用者可以再次将其解包到各个部分。例如，如果我们也在上面的代码中 returned 计数，我们会做：

function count(str, pattern, strInd = str.length, patternInd = pattern.length) {
    if (patternInd === 0) {
        return { count: 1, matches: [[]] };
    }

    if (strInd === 0) {
        return { count: 0, matches: [] };
    }

    if (str.charAt(strInd - 1) === pattern.charAt(patternInd - 1)) {
        const { count: count1, matches: matches1 }  = 
             count(str, pattern, strInd - 1, patternInd - 1);
        const { count: count2, matches: matches2 } = 
             count(str, pattern, strInd - 1, patternInd);
        // For the first case, add the current string index to the partial matches:
        return {
            count: count1 + count2,
            matches: [...matches1.map(indices => [...indices, strInd-1]), ...matches2]
        };
    } else {
        return count(str, pattern, strInd - 1, patternInd);
    }
}

应该总是可以解决像这样的递归问题，但如果它被证明太难，您可以作为替代方案，传递一个额外的 object-variable（或数组），递归调用将添加其结果：它就像一个收集器，逐渐增长到最终的解决方案。不利的一面是，不让函数有副作用违反了最佳实践，其次，此函数的调用者必须已经准备好一个空对象并将其传递以获取结果。

最后，不要试图为此类数据收集使用全局变量。如果这样的 "global" 变量实际上是闭包中的局部变量，那就更好了。但是，另一个选项仍然是首选。

递归：当可能有多个子路径时，跟踪所有递归路径中的变量

Recursion: keeping track of a variable in all recursion paths when multiple sub paths are possible

javascript

recursion

dynamic-programming

lcs

总体思路