Recursion Basics: How to Solve Problems Recursively

recursionBasics.js

/* RECURSION ( when a function invokes itself to solve a problem )
  
  All recursive functions have the following characteristics:
 
  1) The method is implemented using if-else logic that leads to 
     different cases. 
  2) One or more base/terminating cases(the simplest case) are
     used to stop the recursion ex. if (n === 0) stop
  3) Every recursive call reduces the original problem, bringing
     it increasingly closer to the terminating base case until
     it becomes that case
 
  To solve a problem using recursion, you should break it into
  sub-problems. Note that each sub-problem is the same as the
  orginal problem but just smaller in size. You must be able to
  apply the same approach to each sub-problem to solve it recursively.
 
  PRACTICAL EXAMPLES OF RECURSION:
 
  ########################################
  EX.1: Consider drinking a cup of coffee */
 
  var drinkCoffee = function(cup) {
      if (cup.isEmpty())
          return console.log('cup empty');
      else {
          cup.takeSip();
          drinkCoffee(cup);
      }
  };
 
/*
  Assume cup is an object for a cup of coffee with methods isEmpty()
  and takeSip(). You can break the problem into two sub problems: one
  is to drink a full cup of coffee until it is empty and the other is
  to drink one sip. Both problems are of the same nature but one is 
  just smaller in size. The base or terminating case would be when
  the cup is empty.
 
  ########################################
  EX.2: Consider logging a message n times. 
 
  Break the problem into two subproblems:
 
      Subproblem 1: log the message one time
      Subproblem 2: log the message n-1 times
 
  Both subproblems are the same in nature(loggin a message), just one
  becomes incrementally smaller than the other.
  -Our base/terminating case would be when n === 0; */
 
  var logMessage = function(message, nTimes) {
      if (nTimes >= 1) {
          console.log(message);
          logMessage(message, nTimes - 1);
      }
      //base case is when nTimes === 0, recursion stops
  };
 
/*########################################
  EX.3 Check whether a string is a Palindrome ie. aibohphobia === aibohphobia
 
  What are our two subproblems?
  1)First check whether the 1st letter and the last letter of our
    string are equal.
  2)If they are, ignore the two end characters and check whether the
    rest of the substring is a Palindrome
 
  Once again, note how the second subproblem is the same as the first,
  just smaller in size.
 
  What would our base case be?
    We would have two in this case:
    1) Terminate when the two end characters are not the same
    2) Terminate when the string size(string.length) is < 2. */
 
  var palindrome = function(word) {
      word = word.split(' ').join('').toLowerCase(); //normalize string
      var isPalindrome = true,
          lastChar = word[word.length - 1]; // get last character
      //our base cases
      if (word.length < 2 || word[0] != lastChar)
          isPalindrome = false;
      else //our recursive call. use slice to make the problem increasingly smaller
          palindrome(word.slice(1, word.length - 1));
      //return our results, defaults to true unless proven otherwise
      return isPalindrome ? (word + ' is a palindrome') :
          (word + ' is not a palindrome');
  };
 
  console.log(palindrome('alex')); // alex is not a palindrome
  console.log(palindrome('aibohphobia')); //aibohphobia is a palindrome
  console.log(palindrome('Ma is as selfless as I am')); //maisasselflessasiam is a palindrome



  //HERE IS A MORE EFFICIENT PALINDROME METHOD THAT USES A RECURSIVE HELPER METHOD
  //This method avoids creating a new string(memory intensive) for every recursive call

  var palindromeEfficient = function(word) {
      var initializePalindrome = function(word) {
          var tempWord = word.split(' ').join('').toLowerCase();
          return isPalindrome(tempWord, 0, tempWord.length - 1);
      };
      var isPalindrome = function(tempWord, lowIndex, highIndex) {
          //if this returns true, it means it must be a palindrome
          if (lowIndex >= highIndex) //base case
              return true;
          else if (tempWord[lowIndex] != tempWord[highIndex])
              return false;
          else
              return isPalindrome(tempWord, lowIndex + 1, highIndex - 1);
      };
      return initializePalindrome(word) ? ('"' + word + '"' + ' is a palindrome') :
          ('"' + word + '"' +  ' is not a palindrome');
  };

  console.log(palindromeEfficient('daibohphobiad')); // "daibohphobiad" is a palindrome
  //notice how the orginal word is preserved instead of losing the spacing and punctuation as we did in the previous method
  console.log(palindromeEfficient('Ma is as selfless as I am')); //"Ma is as selfless as I am" is a palindrome

//EXAMPLES OF RECURSION
/*#############################*/
//factorial
var factorial = function(n) {
    //terminating case
    if (n === 0)
        return 1;
    else
        return n * factorial(n - 1);
};

console.log(factorial(10)); //3628800

/*#############################*/
//2^n
var twoN = function(n) {
    if (n === 0)
        return 1;
    else
        return 2 * twoN(n - 1);
};

console.log(twoN(10)); // 1024

/*#############################*/
//x^n
var powerX = function(base, exp) {
    if (exp === 0)
        return 1;
    else
        return base * powerX(base, exp - 1);
};

console.log(powerX(3, 3)); // 27

/*#############################*/
//1 + 2 + 3 + 4 + n
var addFactorial = function(n) {
    if (n === 0)
        return 0;
    else
        return n + addFactorial(n - 1);
};

console.log(addFactorial(6)); // 21

/*#############################*/
//caculate fibonnaci index



var fibonnaci = function(n) {
    if (n === 0)
        return 0;
    else if (n === 1)
        return 1;
    else
        return fibonnaci(n - 1) + fibonnaci(n - 2);
};

console.log(fibonnaci(9)); //34