/** 
 * A sampler of functions using recursion.
 * CSE 143 lecture, 4/06
 * Most of these are written as static methods to simplify their use,
 * since there is no particular object naturally associated with them. 
 * Also, many of the functions have a precondition that some parameter
 * is non-negative or something similar.  Those are omitted here to avoid
 * some clutter, but should be added in for more robust production programs.
 */
public class R {
  
  /** Print n stars iteratively */
  public static void iprint(int n) {
    for (int i = 0; i < n; i++) {
      System.out.print("*");
    }
    System.out.println();
  }
  
  /** Print n starts recursively */
  public static void rprint(int n) {
    if (n == 0) {
      System.out.println();
    } else {
      System.out.print("*");
      rprint(n-1);
    }
  }
  
  /** Print decimal digits of n, n>0, one per line, in reverse */
  public static void printDigitsRev(int n) {
    if (n > 0) {
      int rightDigit = n % 10;
      int rest = n / 10;
      System.out.println(rightDigit);
      printDigitsRev(rest);
    }
  }
  
  /** print decimal digits of n, n>0, one per line, in order */
  public static void printDigits(int n) {
    if (n > 0) {
      int rightDigit = n % 10;
      int rest = n / 10;
      printDigits(rest);
      System.out.println(rightDigit);
    }
  }
  
  /** return binary digits of integer n, n>0, as a string in order */
  public static String bits(int n) {
    if (n > 0) {
      int rightBit = n % 2;
      return bits(n/2) + rightBit;
    } else {
      return "";
    }
  }
  
  
  /** Calculate x**n iteratively */
  public static int pow(int x, int n) {
    int ans = 1;
    for (int k = 1; k <= n; k++) {
      ans = ans * x;
    }
    return ans;
  }
  
  /** calculate x**n recursively */
  public static int powr(int x, int n) {
    if (n == 0) {
      return 1;
    } else {
      return x * powr(x, n-1);
    }
  }
  
  /** calculate x**n recursively taking advantage of the identity
   *  x**2n = (x**n)**2 = (x**2)**n */
  public static int fastpow(int x, int n) {
    if (n == 0) {
      return 1;
    } else if (n % 2 == 0) { // if n is even
      return fastpow(x*x, n/2);
    } else { // n is odd
      return x * fastpow(x, n-1);
    }
  }
    
  
  /** print words[k], ..., words[length-1] recursively.
   *  use printWords(words,0) to print the entire array */
  public static void printWords(String[] words, int k) {
    if (k < words.length) {
      System.out.println(words[k]);
      printWords(words, k+1);
    }
  }
  
  /** print words[length-1], ..., words[k] recursively.
   *  use printWordsRev(words,0) to print the entire array backwards */
  public static void printWordsRev(String[] words, int k) {
    if (k < words.length) {
      printWordsRev(words, k+1);
      System.out.println(words[k]);
    }
  }
  
  /** Given n items, return the total number of ways that we can choose m
   *  things from those n items, assuming that the order in which we pick
   *  the items matters. */
  public static int permute(int n, int m) {
    if (n < 0 || m < 0 || m > n) {
      throw new IllegalArgumentException();
    }
    if (m == 0) {
      return 1;
    } else {
      return n * permute(n-1, m-1);
    }
  }
  
  /** Given n items, return the number of ways in which we can choose m
   *  items from the original n, i.e., n choose m. */
  public static int comb(int n, int m) {
    if (n < 0 || m < 0 || m > n) {
      throw new IllegalArgumentException();
    }
    if (m == 0 || n == m) {
      return 1;
    } else {
      return comb(n-1, m) + comb(n-1, m-1);
    }
  }
    
}