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

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 的当前索引推送到递归调用中的“本地索引数组”，并且一旦模式完成，将“本地索引”推送到“全局索引”并为下一个递归路径重置“本地索引”。

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

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”，模式是“ab”，那么我想要 globalIndices = [[4,3], [4,1], [2,1]] 但我会得到 [[4, 3],[1],[2,1]]

我想将“本地索引”重置为之前的分叉。

我是在朝着正确的方向前进，还是这些问题需要完全不同的实现？

Answer 1

首先，当您收集索引时，您不需要保留计数，因为最终数组的长度将是计数：每个数组元素将对应一个匹配项，并且是相关索引的列表。您可以在回溯时使函数的返回值与（部分）匹配的数组匹配并使用额外的索引扩展每个数组（用于在匹配中使用该字符时）：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")); 请注意，索引是从零开始的，因此它们比您提到的预期输出少一。此外，索引从左到右排序，这似乎更有用。大概的概念通常，您最好避免使用全局变量并尽可能多地使用递归函数的返回值。你从中得到的只会涉及递归调用访问的“子树”。在上述情况下，该子树是字符串和模式的较短版本。递归函数返回的内容应该与传递的参数一致（应该是那些参数的“解决方案”）。返回值可能很复杂：当您需要返回多个“一件事”时，您可以将不同的部分放在一个对象或数组中并返回。然后调用者可以再次将其解包到各个部分。例如，如果我们还要在上面的代码中返回计数，我们会这样做：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);    }}应该总是可以解决像这样的递归问题，但是如果证明它太难了，您可以作为替代方法，传递一个额外的对象变量（或数组），递归调用会将其结果添加到其中：就像一个逐渐成长为最终解决方案的收集器。不利的一面是，不让函数产生副作用是违反最佳实践的，其次，此函数的调用者必须已经准备了一个空对象并传递它以获取结果。最后，不要试图将全局变量用于此类数据收集。如果这种“全局”变量实际上是闭包中的局部变量，那就更好了。但是，另一种选择是首选。