Javascript recursive example

Question

I recently had an interview where you had to recursively go over a string, and if it contained an AB || BA || CD || DC, it had to be deleted from the array. You would recursively go over this as deleting the CD from ACDBB would give you an AB which you would then have to delete to return a B as a string.

This is what I have, and when I test it out, I see it comes up with the right answer deep in the loops, but it never populates back to the top.

What am I missing?

const LETTERS = [/AB/g, /BA/g, /CD/g, /DC/g];

const stringGame = (string) => {
    
    let newString = '';

    if(string.length <= 1) return string;


    LETTERS.forEach(regExToCheck => {
        if(string.match(regExToCheck)) {
            newString = string.replace(regExToCheck, '')
        }
        stringGame(newString);
    })

    return newString
}

// Expect answer: CAACC
console.log(stringGame('ABDCABCABAAABCCCD'))

Answer 1

The stringGame function doesn't have side effects, so the line in the loop here:

stringGame(newString);

doesn't do anything - you need to communicate the result of the recursive call back to the outer level.

A nicer way to approach this would be to combine the LETTERS into a single regular expression, and then to replace all matches with the empty string until the replacement produces no changes.

const LETTERS = [/AB/g, /BA/g, /CD/g, /DC/g];
const pattern = new RegExp(
  LETTERS
    .map(re => {
      const str = String(re);
      return str.slice(1, str.length - 2);
    })
    .join('|'),
);

const stringGame = (string) => {
  const newString = string.replace(pattern, '');
  return newString === string
    ? string
    : stringGame(newString);
}

// Expect answer: CAACC
console.log(stringGame('ABDCABCABAAABCCCD'))

(If you want to use the global flag in the constructed pattern, you'll have to account for the .lastIndex)

Answer 2

1. Move the recursion,
2. return the recursion, and
3. Add an essential condition to end recursion:

const LETTERS = [/AB/g, /BA/g, /CD/g, /DC/g];
const stringGame = (string) => {
  let newString = '';
  if (string.length <= 1) return string;

  LETTERS.forEach(regExToCheck => {
    if (string.match(regExToCheck)) {
      newString = string.replace(regExToCheck, '')
    }
  })

  // Moved, returned, and ended recursion
  return ('' === newString) ? string : stringGame(newString);
}

// Expect answer: CAACC
console.log(stringGame('ABDCABCABAAABCCCD'))

When recursing the function, i.e., when executing the function within itself, the return'ed value of that execution needs to be used, typically return'ed:

return stringGame(newString);

...in order for it to bubble back up the levels of recursion.

Also, since the replace() function is using a regex global replacement flag (g) all, for example, AB's, are being replaced in a single execution, so there's no need to recurse within the forEach() loop:

LETTERS.forEach(regExToCheck => {
    if(string.match(regExToCheck)) {
        newString = string.replace(regExToCheck, '')
    }
    stringGame(newString); // <-- double oops
})

Rather, recurse after the loop, AND return the value of the execution:

LETTERS.forEach(regExToCheck => {
    if(string.match(regExToCheck)) {
        newString = string.replace(regExToCheck, '')
    }
})
return stringGame(newString);

One more principle of recursive functions is providing exit strategies—define what conditions to end the recursion, bubble back up, and return a final result.

The only exit condition provided is:

if (string.length <= 1) return string;

Surely if there's only one character left no match will be found—a proper time to end recursion. However, and more importantly, there also needs to be a path to exit when there are more than one characters but no matches can be found.

There are multiple ways to determine this but in the case provided in the question the most expedient is when after looping through the regex/replace routine no changes were made to the string. Since with every recursion the stringGame() function instantiates an empty string (newString) if, after looping through the regex/replace routine, newString is still an empty string, this indicates there were no matches found and it's time to end recursion:

if ( '' === newString ) {
  return string;
}
else { 
  return stringGame(newString);
}

...otherwise, recurse.