How to properly call a recursive function inside a for loop?

Question

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

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;
};  

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

Answer 1

There's an open question here, to my mind. Can we use the substrings multiple times or only once each? That is, should

canConstruct ("abcabc", ["ab", "abc", "cd", "def", "abcd"])

return true because we can break it down into abc-abc, using the second entry twice?

Or should it return false because we've already used up our abc for the beginning?

These two snippets are variants of your technique with a different style.

The first one assumes that we can use our substrings as often as necessary:

const canConstruct = (word, words) => 
  word.length == 0
    ? true
    : words .some (
        (w) => word .startsWith (w) && canConstruct (word .replace (w, ''), words)
      )

console .log (canConstruct ("abcdef", ["ab", "abc", "cd", "def", "abcd"]))  //=> true
console .log (canConstruct ("abcddc", ["ab", "abc", "cd", "def", "abcd"]))  //=> false
console .log (canConstruct ("abcabc", ["ab", "abc", "cd", "def", "abcd"]))  //=> true

The second one says we can only use each once:

const removeFirst = (x, xs, i = xs.indexOf(x)) =>
  i < 0
    ? [... xs]
    : [... xs .slice (0, i), ... xs .slice (i + 1)]

const canConstruct = (word, words) => 
  word.length == 0
    ? true
    : words .some (
        (w) => word .startsWith (w) && canConstruct (word .replace (w, ''), removeFirst(w, words))
      )

console .log (canConstruct ("abcdef",    ["ab", "abc", "cd", "def", "abcd"]))         //=> true
console .log (canConstruct ("abcddc",    ["ab", "abc", "cd", "def", "abcd"]))         //=> false
console .log (canConstruct ("abcabc",    ["ab", "abc", "cd", "def", "abcd"]))         //=> false
console .log (canConstruct ("abcabc",    ["ab", "abc", "cd", "abc", "def", "abcd"]))  //=> true
console .log (canConstruct ("abcabcabc", ["ab", "abc", "cd", "abc", "def", "abcd"]))  //=> false

Here we use a helper function, removeFirst which returns a copy of an array after removing the first instance of the given value.