/**
 * Collection of recursive methods included in the final review session
 * for CS 1110 - Fall 2010 on Dec. 8, 2010.
 * @author Nathan Lloyd (nsl6@cornell.edu)
 */
public class recursiveMethods {
  
  /** 
   * = String representation of integer with commas added
   */
  public static String addCommas(int n) {
    if (n < 0)
      return "-" + addCommasHelper(-n);
    return addCommasHelper(n);
  }
  
  /** 
   * = String representation of integer with commas added
   * Precondition: n >= 0
   */
  private static String addCommasHelper(int n) {
    // Base case
    if (n < 1000)
      return "" + n;
    
    // Recursive Case
    String number = "" + n;
    return addCommasHelper(n/1000) + "," + number.substring(number.length()-3);
  }
  
  /** 
   * = the complement of n, formed by replacing each decimal digit of n by 10-n.
   * ie. the result for the integer 93723 is 17387. 
   * Precondition: n > 0 and no digit of n is 0
   */
  public static int complement(int n) {
    // Base Case
    if (n < 10)
      return 10 - n;
    
    // Recursive Case
    return complement(n/10) * 10 + (10 - n%10);
  }
  
  /** 
   * = number of digits for n, with no leading 0’s. 
   */
  public static int length(int n) {
    // Base case
    if (n == 0)
      return n;
    
    // Recursive Case
    return 1 + length(n/10);
  }
  
  /** 
   * = n reduced to a single digit (by repeatedly
   * summing its digits).
   * Precondition: n > 0 
   */
  public static int addUp(int n) {
    // Base case
    if (n < 10)
      return n;
    
    // Recursive Case
    return addUp(n/10 + n%10);
  }
  
  // Below is an additional problem covered that is not in the slides, this is a
  // solution to the Spring 2010 Final exam question 5 (with a slightly different
  // implementation of the helper function).
  
  /**
   * = s compressed such that duplicates are replaced with the count
   * of how many occurances that character has in a row.
   * ie. "aaaaabbbbbccccccaaax" is compressed to "a5b5c6a3x1"
   */
  public static String compress(String s) {
    // Base case
    if (s.equals(""))
      return "";
    
    // Recursive case
    int x = eqChar(s);
    return "" + s.charAt(0) + x + compress(s.substring(x)); 
  }
  
  /**
   * = the number of time the character at index 0 occurs in a
   * row at the start of the String s.
   */
  private static int eqChar(String s) {
    char c = s.charAt(0);
    int i = 0;
    while (i < s.length() && s.charAt(i) == c)
      i++;
    return i;
  }
}