JS recursive code throwing maximum call stack size error-CodePudding

I know this might be basic and simple but since I am self-learning, so I wanted to know what was wrong and I thought this is the best place to learn from.

I am trying to write a recursive code that returns true or false. The condition to check is if the set of words can make the given target word.

The error I keet getting is :

 if (targetString.indexOf(dictionary[i]) == 0) {
                     ^

RangeError: Maximum call stack size exceeded
    at String.indexOf (<anonymous>)

I am pretty sure that the problem with code is in a way I am returning because I always find it confusing.

my code is:

let targetString = "furniture";
let dictionary = ["fur", "ure", "nit"];
const tableData = {};

const canConstructRecursive = (targetString, dictionary) => {
  if (targetString == "") {
    return true
  }

  for (let i = 0; i < dictionary.length; i  ) {
    if (targetString.indexOf(dictionary[i]) == 0) {
      shorterTargetString = targetString.slice(0, dictionary[i].length);
      return canConstructRecursive(shorterTargetString, dictionary);
    }
  }
  return false;
}

console.log(canConstructRecursive(targetString, dictionary));

I am learning recursion and from time to time I feel I don't understand the logic of return to next/previous recursive call.

I would really appreciate it if someone could help me with what I am doing wrong and change my way of thinking.

My way of thinking is that:

the base case is returned if it is reached at that stage otherwise loop go through all the option and the inner node or upper stack need to return value to lower stack so I am doing return canConstructRecursive() inside for. If even in all options which is all iteration of for loop, it is not returned, there is return false at the end.

Thank you in advance

CodePudding user response：

The reason is that although your variable is named shorterTargetString, it is not guaranteed to be really shorter. If i is the index of the shortest word in dictionary, then there is no way your string will ever get shorter by recursing with it.

The mistake is that the slice should not start at 0, but after the part that was matched, so remove the first argument from the slice call.

This will solve the stack overflow error.

Secondly, if the recursive call returns false you should not give up, but keep trying with the next word. So only return out of the loop when you got true from recursion:

let targetString = "furniture";
let dictionary = ["fur", "ure", "nit"];
const tableData = {};

const canConstructRecursive = (targetString, dictionary) => {
  if (targetString == "") {
    return true
  }

  for (let i = 0; i < dictionary.length; i  ) {
    if (targetString.indexOf(dictionary[i]) == 0) {
      shorterTargetString = targetString.slice(dictionary[i].length);
      if (canConstructRecursive(shorterTargetString, dictionary)) {
         return true;
      };
    }
  }
  return false;
}

console.log(canConstructRecursive(targetString, dictionary));

More on the second fix.

Your code will unconditionally return the value of the recursive call, even when it is false. This is not good: in case the recursive call returns false, the caller should continue with its for loop to try alternatives.

Let's for instance add a word to your example dictionary: you'll agree that adding a dictionary word should not change the outcome for the input "furniture". So here it is:

["furn", "fur", "ure", "nit"]

But surprise: your code now returns false for "furniture"! This is because "furn" mathes, but the recursive call with "iture" as first argument does not find further matches, so it returns false, and now the caller also returns false. This is wrong. It should give up on "furn", but not on the whole exercise. It should have continued and tried with "fur". This is why the exit out of the for loop should only happen upon success, not upon failure. Failure can only be confirmed when all dictionary words have been tried, so the for loop must continue for as long as there is no recursive success.