Recursive Interview Questions Tutorial (WIP)

The most important thing to learn is how to think recursively. This allows you to solve a large class of problems relatively simply. It's important to know for job interviews. I had interviewed at Google six months ago and because I botched an interview question that could have been solved recursively, the interviewer told the recruiter I "lacked fundamental understanding of computer science". 

To solve a problem recursively:

1)  Think about how to solve the problem for simple cases (base case). 

2)  Determine how to break down larger cases into smaller instances (recursive decomposition).

Remember that every recursive algorithm has two components: the base case and the recursive decomposition. 

Problem #1 Reverse A String

Base Case:  When the string is the empty string is it the same backwards as it is forwards

Recursive Decomposition: For strings, to shrink the string to make forward progress is the same as solving the problem for substrings of the string, and then combining the sub-solutions.

/* Returns the reverse of the indicated string. */
string reverseString(string line) {
 if (line == "")
  return "";
 else
  return reverseString(line.substr(1)) + line[0];
}

Problem #2 Count Spaces in A String

Base Case:  When the string is empty is cannot have a space so the count of spaces is 0.

Recursive Decomposition: Check character by character by working with substrings of the string, and then sum the counts of the strings. 

/* Returns the count of white spaces in a string*/
int countSpaces(string line){
  if (line.length() == 0)
    return 0;
  else
    return ((isspace(line[0]) ? 1 : 0) + countSpaces(line.substr(1)));
}

Problem #3 Find Last Occurrence of Character in String

Base Case: Well if you are at the end of the string and no characters follow, it must be the last occurrence if there is a match. 

Recursive Decomposition: Start at the end of the string and after each call remove the last character. 

/* Return the index of the last occurence of a character in the string */
int find_last_occurence(string line, char character){
  if (line[line.length()-1] == character)
    return (int)line.length();
  else if(line.length() == 0)
    return -1;
  else
    return find_last_occurence(line.substr(0,line.length()-1), character);
}

Spark Notes Article That I Thought Was Useful: http://www.sparknotes.com/cs/recursion/whatisrecursion/section2.rhtml

Problem #4 Traversing a Binary Tree. Inorder, preorder, postorder.

Problem #5 Print all subsets of a set. 

Problem #6 Print all alphanumeric combinations of a phone number. 

These are the slides that I found on the Stanford Engineering Everywhere site that I found useful to learn more about recursion.