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

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会在分支发生后开始跟踪匹配。

例如，字符串是"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);
    }
}

应该总是可以解决这样的递归问题，但如果它被证明太难，您可以作为替代方案，传递一个额外的对象变量(或数组)，递归调用会将其结果添加到该对象变量(或数组)中:它就像一个逐渐增长为最终解决方案的收集器。缺点是，不让函数产生副作用与最佳实践背道而驰，其次，此函数的调用者必须已经准备好一个空对象并传递该对象才能获得结果。

最后，不要尝试使用全局变量进行此类数据收集。如果这样的“全局”变量实际上是闭包中的局部变量，那会更好一些。但尽管如此，另一种选择仍是首选。