How to code an recursion function from an iterative approach?

Question

How would I be able to code the same code below while using recursion, I did it with an iterative approach and I would really appreciate it if someone can help me code it using recursion thankyou! Here's my code:

function returnNumberOfPalindromes(word) {
  function checkForPalindrome(chunk) { 
    let chunkArray = [];
    for (const letter of chunk) { 
      chunkArray.push(letter);
    }
    if (chunkArray.reverse().join('') === chunk) {
      tally += 1;
    }
  }
  let tally = 0;

  for (let index1 = 0, index2 = 2; index1 <= word.length; index1++, (index2 = index1 + 2)) {
    for (; index2 <= word.length; index2++) { 
      let chunk = word.slice(index1, index2); 
      checkForPalindrome(chunk);
    }
  }
  console.log(tally);
}

returnNumberOfPalindromes("kayak");
returnNumberOfPalindromes("aya");
returnNumberOfPalindromes("appal");
returnNumberOfPalindromes("addadaadd");

Answer 1

A series of refactorings

Over a series of refactorings, we're going to end up with this code:

const isPalindrome = (s) =>  
  s.length == 0 ? true : s[0] === s[s.length - 1] && isPalindrome(s.slice(1, -1))

const countPalindromicPrefixes = (s) =>
  s.length < 2 ? 0 : (isPalindrome(s) ? 1 : 0) + countPalindromicPrefixes(s.slice (0, -1)) 

const countPalindromes = (s) => 
  s.length < 2 ? 0 : countPalindromicPrefixes(s) + countPalindromes(s.slice(1))


console .log (countPalindromes ("kayak"));
console .log (countPalindromes ("aya"));
console .log (countPalindromes ("appal"));
console .log (countPalindromes ("addadaadd"));
console .log (countPalindromes ("madamimadam"));

Each step has a snippet (hidden by default so this isn't too long) showing that we haven't broken anything so far.

Starting Point

The initial code looks like this:

function returnNumberOfPalindromes(word) {
  function checkForPalindrome(chunk) { 
    let chunkArray = [];
    for (const letter of chunk) { 
      chunkArray.push(letter);
    }
    if (chunkArray.reverse().join('') === chunk) {
      tally += 1;
    }
  }
  let tally = 0;

  for (let index1 = 0, index2 = 2; index1 <= word.length; index1++, (index2 = index1 + 2)) {
    for (; index2 <= word.length; index2++) { 
      let chunk = word.slice(index1, index2); 
      checkForPalindrome(chunk);
    }
  }
  console.log(tally);
}

function returnNumberOfPalindromes(word) {
  function checkForPalindrome(chunk) { 
    let chunkArray = [];
    for (const letter of chunk) { 
      chunkArray.push(letter);
    }
    if (chunkArray.reverse().join('') === chunk) {
      tally += 1;
    }
  }
  let tally = 0;

  for (let index1 = 0, index2 = 2; index1 <= word.length; index1++, (index2 = index1 + 2)) {
    for (; index2 <= word.length; index2++) { 
      let chunk = word.slice(index1, index2); 
      checkForPalindrome(chunk);
    }
  }
  console.log(tally);
}

returnNumberOfPalindromes("kayak");
returnNumberOfPalindromes("aya");
returnNumberOfPalindromes("appal");
returnNumberOfPalindromes("addadaadd");

Fixing the for-loops

There is something very odd about updating the initial index of the inner loop as part of the increment of outer one. This is much more common, and I dare say, much more logical:

  for (let index1 = 0; index1 <= word.length; index1++) {
    for (let index2 = index1 + 2; index2 <= word.length; index2++) { 
      let chunk = word.slice(index1, index2); 
      checkForPalindrome(chunk);
    }
  }

function returnNumberOfPalindromes(word) {
  function checkForPalindrome (chunk) { 
    if (chunk.split('').reverse().join('') === chunk) {
      tally += 1;
    }
  }
  let tally = 0;

  for (let index1 = 0; index1 <= word.length; index1++) {
    for (let index2 = index1 + 2; index2 <= word.length; index2++) { 
      let chunk = word.slice(index1, index2); 
      checkForPalindrome(chunk);
    }
  }
  console.log(tally);
}

returnNumberOfPalindromes("kayak");
returnNumberOfPalindromes("aya");
returnNumberOfPalindromes("appal");
returnNumberOfPalindromes("addadaadd");
returnNumberOfPalindromes("madamimadam");

Simplifying checkForPalindrome

Much of the work being done in checkForPalindrome is unnecessary. String.prototype.split already turns a string into an array of characters. So we can change that part to just:

  function checkForPalindrome (chunk) { 
    if (chunk.split('').reverse().join('') === chunk) {
      tally += 1;
    }
  }

function returnNumberOfPalindromes(word) {
  function checkForPalindrome (chunk) { 
    if (chunk.split('').reverse().join('') === chunk) {
      tally += 1;
    }
  }
  let tally = 0;

  for (let index1 = 0; index1 <= word.length; index1++) {
    for (let index2 = index1 + 2; index2 <= word.length; index2++) { 
      let chunk = word.slice(index1, index2); 
      checkForPalindrome(chunk);
    }
  }
  console.log(tally);
}

returnNumberOfPalindromes("kayak");
returnNumberOfPalindromes("aya");
returnNumberOfPalindromes("appal");
returnNumberOfPalindromes("addadaadd");
returnNumberOfPalindromes("madamimadam");

Make local function a pure function

Our internal function checkForPalindrome is not returning a value. Instead, it is updating the state of tally. That makes it harder to understand. Let's change that to make checkForPalindrome return true or false, and update tally based on that result:

  function checkForPalindrome (chunk) { 
    return chunk.split('').reverse().join('') === chunk
  }

      if (checkForPalindrome(chunk)) {
        tally += 1
      }

function returnNumberOfPalindromes(word) {

  function checkForPalindrome (chunk) { 
    return chunk.split('').reverse().join('') === chunk
  }

  let tally = 0;

  for (let index1 = 0; index1 <= word.length; index1++) {
    for (let index2 = index1 + 2; index2 <= word.length; index2++) { 
      let chunk = word.slice(index1, index2); 
      if (checkForPalindrome(chunk)) {
        tally += 1
      }
    }
  }
  console.log(tally);
}

returnNumberOfPalindromes("kayak");
returnNumberOfPalindromes("aya");
returnNumberOfPalindromes("appal");
returnNumberOfPalindromes("addadaadd");
returnNumberOfPalindromes("madamimadam");

Pulling that internal function out

Still focused on checkForPalindrome, we can note that it's now a useful function to determine if a string is a palindrome. So we might as well pull it out of the guts of our main function and make it stand-alone.

But a common convention for a function returning true or false is to name it starting with is. In this case, isPalindrome definitely makes more sense. So we change to this:

function isPalindrome (word) { 
  return word.split('').reverse().join('') === word
}

and

      if (isPalindrome(chunk)) {
        tally += 1
      }

function isPalindrome (word) { 
  return word.split('').reverse().join('') === word
}

function returnNumberOfPalindromes(word) {

  let tally = 0;

  for (let index1 = 0; index1 <= word.length; index1++) {
    for (let index2 = index1 + 2; index2 <= word.length; index2++) { 
      let chunk = word.slice(index1, index2); 
      if (isPalindrome(chunk)) {
        tally += 1
      }
    }
  }
  return tally;
}

console .log (returnNumberOfPalindromes("addadaadd"));  //=> 7

Turning this recursive

Now for the big step. We want to make this recursive. Let's examine what our main loop is doing:

  for (let index1 = 0; index1 <= word.length; index1++) {
    for (let index2 = index1 + 2; index2 <= word.length; index2++) { 
      let chunk = word.slice(index1, index2); 
      if (isPalindrome(chunk)) {
        tally += 1
      }
    }
  }

This code is looping twice through the indices, finding all the substrings starting at index 0, then all starting at index 1, then all starting at index 2, etc. For each one it tests if the string is a palindrome, and if it is, we increment the tally.

This sort of double-looping will almost certainly mean that we have a double recursion going on too. So we can think about it as having two functions.

One function takes a string and looks at all the prefixes of that string (for instance for "goat", the prefixes would be "goat", "goa", "go", and "g") and counts the number of those that are palindromes. If the word is fewer than two characters long, then it has no palindromes and we return 0, and otherwise we include 1 if the word is a palindrome, 0 if it's not and add it to the result of a recursive call that drops off the last character:

function returnNumberOfPalindromicPrefixes(word) {
  if (word .length < 2) {
    return 0
  }
  return (isPalindrome(word) ? 1 : 0) + returnNumberOfPalindromicPrefixes(word.slice(0, -1)) 
}

The second function recurs on the beginning of the string. Again if the word is fewer than two characters long, we again return 0. Otherwise we add the result of calling the prefix function to a recursive call on the string formed by dropping our first character:

function returnNumberOfPalindromes(word) {
  if (word .length < 2) {
    return 0
  }
  return returnNumberOfPalindromicPrefixes(word) + returnNumberOfPalindromes(word.slice(1))
}

function isPalindrome(word) { 
  return word.split('').reverse().join('') === word
}

function returnNumberOfPalindromicPrefixes(word) {
  if (word .length < 2) {
    return 0
  }
  return (isPalindrome(word) ? 1 : 0) + returnNumberOfPalindromicPrefixes(word.slice(0, -1)) 
}

function returnNumberOfPalindromes(word) {
  if (word .length < 2) {
    return 0
  }
  return returnNumberOfPalindromicPrefixes(word) + returnNumberOfPalindromes(word.slice(1))
}

console .log (returnNumberOfPalindromes("kayak"));
console .log (returnNumberOfPalindromes("aya"));
console .log (returnNumberOfPalindromes("appal"));
console .log (returnNumberOfPalindromes("addadaadd"));
console .log (returnNumberOfPalindromes("madamimadam"));

Interlude

At this point we have reasonable code. We have refactored it into recursive functions that are fairly logical and fairly clear. (It's also very similar to the answer from Applet123.)

This may be plenty for you (or for your instructor.)

But I think there are more useful changes to be made. Think of the next few steps as nice-to-haves.

Function naming

This may sound trivial, but the names returnNumberOf<Whatever> are pretty horrible. Much better would be count<Whatever>, numberOf<Whatever> possibly sizeOf<Whatever>.

I will choose the first one, which will give us the names countPalindromicPrefixes and countPalindromes.

function isPalindrome (word) { 
  return word.split('').reverse().join('') === word
}

function countPalindromicPrefixes(word) {
  if (word .length < 2) {
    return 0
  }
  return (isPalindrome(word) ? 1 : 0) + countPalindromicPrefixes(word.slice(0, -1)) 
}

function countPalindromes(word) {
  if (word .length < 2) {
    return 0
  }
  return countPalindromicPrefixes(word) + countPalindromes(word.slice(1))
}

console .log (countPalindromes("kayak"));
console .log (countPalindromes("aya"));
console .log (countPalindromes("appal"));
console .log (countPalindromes("addadaadd"));
console .log (countPalindromes("madamimadam"));

More modern JS

Using arrow functions rather than function declarations cleans up a lot of code. Conditional (ternary) operators also do. Using these we can turn something like this:

function countPalindromes(word) {
  if (word .length < 2) {
    return 0
  }
  return countPalindromicPrefixes(word) + countPalindromes(word.slice(1))
}

into this:

const countPalindromes = (word) => 
  word .length < 2 ? 0 : countPalindromicPrefixes(word) + countPalindromes(word.slice(1))

and do something similar for the other functions.

const isPalindrome = (word) =>  
  word.split('').reverse().join('') === word

const countPalindromicPrefixes = (word) =>
  word.length < 2 ? 0 : (isPalindrome(word) ? 1 : 0) + countPalindromicPrefixes(word.slice(0, -1)) 

const countPalindromes = (word) => 
  word.length < 2 ? 0 : countPalindromicPrefixes(word) + countPalindromes(word.slice(1))


console .log (countPalindromes ("kayak"));
console .log (countPalindromes ("aya"));
console .log (countPalindromes ("appal"));
console .log (countPalindromes ("addadaadd"));
console .log (countPalindromes ("madamimadam"));

Parameter naming

We're using the parameter name "word" here for our functions. But do we truly mean for this to be a word? The sentence "A man, a plan, a canal: Panama!" is widely described as a palindrome. (While it doesn't fit our test, we could easily fix it up to do so by lowercasing the value and removing any non alphabetic characters before doing the current test.) And in fact, I added a test case to these, which captures a version of another classic palindrome, "Madam, I'm Adam."

So the input could be a word or a sentence? Perhaps a phrase as well? People talk sometimes about numbers being palindromic, ones such as 2112. So "word" is not the right name for these. Ours seems to take an arbitrary string. So we should rename the parameter to something capturing that. Perhaps "str"? Perhaps "string"? I'm going to suggest something more radical. We really don't know the type, and it's a one-line function, so a single-character name that still gives a flavor of "string" seems perfectly reasonable here. I will choose "s". Do note that there are those who abhor this idea. That might include your instructor, so be careful. (If someone objects, you can always point them to an article on this idea, Descriptive Variable Names: A Code Smell, by John DeGoes. But they might still start throwing things at you, so be wary.)

So we might write these this way:

const countPalindromicPrefixes = (s) =>
  s.length < 2 ? 0 : (isPalindrome(s) ? 1 : 0) + countPalindromicPrefixes(s.slice(0, -1)) 

const isPalindrome = (s) =>  
  s.split('').reverse ().join('') === s

const countPalindromicPrefixes = (s) =>
  s.length < 2 ? 0 : (isPalindrome(s) ? 1 : 0) + countPalindromicPrefixes(s.slice(0, -1)) 

const countPalindromes = (s) => 
  s.length < 2 ? 0 : countPalindromicPrefixes(s) + countPalindromes(s .slice(1))


console .log (countPalindromes ("kayak"));
console .log (countPalindromes ("aya"));
console .log (countPalindromes ("appal"));
console .log (countPalindromes ("addadaadd"));
console .log (countPalindromes ("madamimadam"));

Do all the things recursive

I wouldn't do the following except for a class assignment. We already have a working version of isPalindrome, one that is readable and efficient. But since this is clearly a recursion assignment, it might be nice to write a recursive version of isPalindrome as well.

To do that, we can think about this recursively by noting that a string is a palindrome if the first and last characters match and the string in between is also a palindrome. The empty string is here considered a palindrome, as is a single-character string. (The first and last characters in this case, point to the same place, so of course they're the same.) We could write it like this:

const isPalindrome = (s) =>  
  s.length == 0 ? true : s[0] === s[s.length - 1] && isPalindrome(s.slice(1, -1))

Note that for the general problem here, we didn't consider 1-character substrings as palindromes, but that's handled in the main functions. isPalindrome happily reports them as such, which seems appropriate.

const isPalindrome = (s) =>  
  s.length == 0 ? true : s[0] === s[s.length - 1] && isPalindrome(s.slice(1, -1))

const countPalindromicPrefixes = (s) =>
  s.length < 2 ? 0 : (isPalindrome(s) ? 1 : 0) + countPalindromicPrefixes(s.slice (0, -1)) 

const countPalindromes = (s) => 
  s.length < 2 ? 0 : countPalindromicPrefixes(s) + countPalindromes(s.slice(1))


console .log (countPalindromes ("kayak"));
console .log (countPalindromes ("aya"));
console .log (countPalindromes ("appal"));
console .log (countPalindromes ("addadaadd"));
console .log (countPalindromes ("madamimadam"));

Answer 2

I'm not going to write checkForPalindrome recursively since it's trivial to do:

function checkForPalindrome(str) {
  // we can use .split("") to convert to an array of characters
  return str.split("").reverse().join("") == str;
}

function palindromesAtStart(str) {
  // lengths 0 and 1 can't be palindromes
  if (str.length < 2) {
    return 0;
  }
  // if it's a palindrome add 1
  const diff = checkForPalindrome(str) ? 1 : 0;
  // now shorten the string and check again
  return diff + palindromesAtStart(str.slice(0, -1));
}

function returnNumberOfPalindromes(str) {
  if (str.length < 2) {
    return 0;
  }
  // total palindromes is palindromes at start plus palindromes not at start
  return palindromesAtStart(str) + returnNumberOfPalindromes(str.slice(1));
}


console.log(returnNumberOfPalindromes("kayak"));
console.log(returnNumberOfPalindromes("aya"));
console.log(returnNumberOfPalindromes("appal"));
console.log(returnNumberOfPalindromes("addadaadd"));

Essentially, the palindromes in the string can either include the first index, or not include the first index. So, we can write a simple recursive function (palindromesAtStart) to count the number of palindromes which include the first index and add that to the number of palindromes which don't include the first index.