How to create a recursive function that checks every substring?

Question

How can I find all the substrings in any given string using a recursive function? I know how to do it using 2 for loops, but I don't know how to do it using recursion. Every substring needs to be checked for whether it's a palindrome. Here is my non iterative solution.

console.log(palindromeIterative("madam"));

function palindromeIterative(word) {
  let noOfP = 0;

  for (let i = 0; i < word.length; i++) {
    for (let j = i + 1; j <= word.length; j++) {
      noOfP = palindromeIterativeHelper(word.substring(i, j), noOfP);
    }
  }

  return noOfP;
}

function palindromeIterativeHelper(word, noOfP) {
  if (word === word.split("").reverse().join("") && word.length > 1) {
    console.log(word);
    noOfP++;
  }

  return noOfP;
}

Your recursive function should check the given string to see if it's a palindrome, then loop through every substring that is one character shorter and call itself on that substring. For example, if your string is "ABC" (3 chars long), the function would check "ABC" for palindrome-ness, then call itself twice: first by passing "AB", then by passing "BC" (i.e. all the substrings that are 2 chars long). When the string to be checked is only one characters long, the function no longer recurses. — kmoser, Nov 10 '20 at 02:34
I answered a similar question just yesterday. Perhaps it helps? https://stackoverflow.com/a/64760183/1244884 — customcommander, Nov 10 '20 at 07:30

score 0 · Answer 1 · answered Nov 10 '20 at 03:02

Here is the recursive version. This may not be the best-optimized solution but this will solve the problem stated above.

let str = "forgeeksskeegfor"
let noOfP = 0;
let getSubstrings = (str) => {
  let countPalindrome = (str) => {
    if (str.length < 2)
      return
    else {
      if (str == str.split("").reverse().join("")) {
        console.log(str);
        noOfP++;
      }
      countPalindrome(str.substring(0, str.length - 1))
    }
  }
  countPalindrome(str)
  if (str.length < 2) {
    return noOfP;
  }
  return getSubstrings(str.substring(1))
}
console.log(`Total Palindromes : ${getSubstrings(str)}`)

Aadit M Shah · Answer 2 · 2020-11-11T11:41:30.147

Here's what I would do:

const sublists = (list, rightmost = true) => {
    if (list.length === 0) return [];
    const result = [list, ...sublists(list.slice(0, -1), false)];
    if (rightmost) result.push(...sublists(list.slice(1), true));
    return result;
};

const isPalindrome = string => string.length > 1 &&
    string.split("").reverse().join("") === string;

const palindromes = string => sublists(string).filter(isPalindrome);

console.log(palindromes("malayalam"));

Here's how it works. We perform a depth first search. For each string, we recursively remove the last letter. For the rightmost string at each level, we also recursively remove the first letter. After we generate the list of all the substrings, we filter those substrings which are palindromes.

malayalam
|        \
malayala  alayalam
|         |       \
malayal   alayala  layalam
|         |        |      \
malaya    alayal   layala  ayalam
|         |        |       |     \
malay     alaya    layal   ayala  yalam
|         |        |       |      |    \
mala      alay     laya    ayal   yala  alam
|         |        |       |      |     |   \
mal       ala      lay     aya    yal   ala  lam
|         |        |       |      |     |    |  \
ma        al       la      ay     ya    al   la  am
|         |        |       |      |     |    |   | \
m         a        l       a      y     a    l   a  m

The above diagram is a visualization of the recursive call stack of the sublists function for the string malayalam. The palindromes are highlighted in bold.

How to create a recursive function that checks every substring?

2 Answers2