如何在for循环中正确调用递归函数? [英] How to properly call a recursive function inside a for loop?

问题描述

我正在尝试实现一个将参数作为参数的方法:目标 string 和其中包含 string 值的 array .目的是检查是否可以使用数组的值(给定的目标字符串)进行构造.array中的单词可以根据需要使用多次.示例:

I'm trying to implement a method that takes as a parameter: target string and an array with string values in it. The goal is to check if it is possible to construct with array's value, the given target string.The words in array can be used as many times as we want. Example:

console.log(canConstruct("abcdef", ["ab", "abc", "cd", "def", "abcd"])); // suppose to return true

我们可以看到，通过将"abc" 和"def" 串联在一起，我们得到了"abcdef" 的目标字符串这是我的函数实现:

As we can see, by concatenating "abc" and "def" we get the target string of "abcdef" Here is my function implementation:

const canConstruct = function (target, wordBank) {
  if (target === "") return true;
  console.log(target);
  for (let word of wordBank) {
    if (target.startsWith(word)) {
      return canConstruct(target.replace(word, ""), wordBank);
    }
  }

  return false;
};  

第2行是此递归函数的基本情况，然后通过遍历数组检查它是否以数组元素开头，如果为true，则删除该特定子数组，并使用新的目标字符串和旧数组再次调用该函数，如果为false，则继续遍历整个函数，直到遇到基本情况为止.因此，再次使用前面的示例:

Line 2 is a base case for this recursion function, then by iterating through the array check if it starts with the array element, if true then remove that specific subarray and call again the function with the new target string and old array, if false keep iterating through entire function till it hits the base case. So again using the previous example:

console.log(canConstruct("abcdef", ["ab", "abc", "cd", "def", "abcd"]));  // return false

我变得虚假了，通过调试，我发现自第一次递归调用以来，它没有迭代整个数组.我得到以下输出:

I'm getting false, and by debugging I can see that it didn't iterate the whole array from since first recursive call. I get the following output:

abcdef
cdef
ef
false

推荐答案

即使您返回false 并以这种方式跳过所有其他组合，您也会为循环而烦恼.因此，根据您的情况，您只能找到一条路径

You are breaking for loop even if you return false and skiping all other combinations that way. So you are founding only one path, in your case

ab
cd

const canConstruct = function (target, wordBank) {
    if (target === "")
        return true;
    for (let word of wordBank) {
        if (target.startsWith(word)) {
            if (canConstruct(target.replace(word, ""), wordBank))//break it only if true
                return true;
        }
    }

    return false;
};
console.log("abcdef", canConstruct("abcdef", ["ab", "abc", "cd", "def", "abcd"]));

console.log("abc1def", canConstruct("abc1def", ["ab", "abc", "cd", "def", "abcd"]));

这篇关于如何在for循环中正确调用递归函数?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！