CODEWITHSUNDEEP
javascriptfunctionrecursion
Ben Davidow
Ben Davidow

Reputation: 1215

Differentiate between an initial and successive call to a recursive function

My broad question is what's the simplest way to differentiate between an initial and successive call to a recursive function in JavaScript.

Lemme give an example...

Let's say I want the following function to return false if the string passed to the function in the initial call is empty. Is there a way to do this without adding in another parameter to the function?

function isPalindrome(str) {
   if (str.length <= 1) {
     return true;
   }
   if (str.charAt(0) !== str.charAt(str.length -1)) {
     return false;
   }
   return isPalindrome(str.substr(1, str.length - 2));
}

isPalindrome('') // returns true, but I want this to return false

Btw, I know the above function could be written more simply as:

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

But I'm reframing it as a recursive function to get at the broader question here...

Upvotes: 0

Views: 461

Answers (3)

RobG
RobG

Reputation: 147413

This is essentially the same as Bergi's answer but with the helper function declared inside isPalindrome so that it isn't used elsewhere.

A better example for a palindrome is that all punctuation should be removed and letters made all upper or lower case (so that comparisons are not case sensitive), but only on the first call. After that, it's a simple matter of comparing characters.

The length == zero part is also only handled once, the function isn't called recursively if there are no characters left to compare.

The following does initial processing, then calls an inner function.

A function declaration is used instead of a named function expression as the latter have undesirable side effects in IE.

  function isPalindrome(s) {

    // Initial processing only on first call
    // remove all punctuation
    s = s.replace(/[^a-z0-9]/ig,'').toLowerCase();

    return s.length == 0? false : doCheck(s);

    function doCheck(s) {

      if (s.length > 1) {

        if (s.substr(0,1) == s.substr(s.length - 1, 1)) {
          s = s.substr(1, s.length - 2);
          return s.length? doCheck(s) : true;

        } else {
          return false;
        }
      }
      return true;
    }
  }

  console.log(isPalindrome("Madam I'm Adam"));  // true
  console.log(isPalindrome("Madam I'm Addam")); // false

Upvotes: 0

Bergi
Bergi

Reputation: 664648

Don't try to distinguish different calls - the result of the function should not depend on side effects and definitely not on the call stack.

Instead, use a second function that does a little different thing:

function isPalindrome(str) {
   return str.length <= 1 ||
     str.charAt(0) == str.charAt(str.length-1) && isPalindrome(str.slice(1, -1));
}
function isNonEmptyPalindrome(str) {
   return str.length > 0 && isPalindrome(str);
}

Upvotes: 3

Paul
Paul

Reputation: 141837

You can have a nested function, even with the same name:

function isPalindrome(str) {

  // The code out here is for the initial call:
  if (str === '')
    return false;

  // Then do the recursive call
  return function isPalindrome(str) {
    // within this scope, isPalindrome refers to this function

    if (str.length <= 1) {
      return true;
    }
    if (str.charAt(0) !== str.charAt(str.length -1)) {
      return false;
    }
    return isPalindrome(str.substr(1, str.length - 2));
  }(str); // call this function immediately

}

For a general form:

function name(arg) {

    // Setup code before initial call
    //////////////////////////////

    var retVal = function name(arg) {
      // recursive routine code
    }(arg);

    // Cleanup code after recursion completes
    /////////////////////////////////////////

    return retVal;
}

Demo using factorial

Upvotes: 0

Related Questions