// Examples of different recursive methods.

public class recursive {

  public static void main(String[] args) {
    printTiles("", 6);
  }

  // Standard recursive power method
  public static int powera(int b, int e) {

    if (e == 0)
      return 1;
    else 
      return powera(b,e-1)*b;
  }

  // Slightly more efficient recursive power method. Performs less actual
  // mutliplications than the method above.
  public static int powerb(int b, int e) {

    if (e == 0)
      return 1;

    // Utilizes even exponent
    else if (e%2 == 0) {
      int sqrt = powerb(b,e/2);
      return sqrt*sqrt;
    }
    else
      return powerb(b,e-1)*b;
  }

  // Computes an exponent mod a particular value, recursively.
  public static int powermoda(int b, int e, int mod) {

    if (e == 0)
      return 1;
    else
      return ((b%mod)*powermoda(b,e-1,mod))%mod;
  }

  // Same as above, except slightly more efficient.
  public static int powermodb(int b, int e, int mod) {

    if (e == 0)
      return 1;
    else if (e%2 == 0) {
      int sqrt = powermodb(b,e/2,mod);
      return (sqrt*sqrt)%mod;
    }
    else
      return (powermodb(b,e-1,mod)*(b%mod))%mod;
  }

  // Searches for val in the sort int array list in between the array
  // indexes low and high, inclusive. If val is found, returns true.
  public static boolean search(int[] list, int low, int high, int val) {

    int mid;
    if (high < low)
      return false;
    else
      mid = (low+high)/2;
    
    if (val == list[mid])
      return true;
    else if (val > list[mid])
      return search(list, mid+1, high, val);
    else
      return search(list, low, mid-1, val);
  }

  // Counts the number of non-decreasing sequences of len numbers in the
  // array list that start with the number cur_val or higher in between
  // array indexes low and high.
  public static int incseq(int[] list, int cur_val, int low, int high, 
			   int len) {

    if (len == 0)
      return 1;
    else if (high < low)
      return 0;
    else {

      int bonus = 0;
      if (list[low] >= cur_val)
        bonus = incseq(list, list[low], low+1, high, len-1);

      return bonus+incseq(list, cur_val, low+1, high, len);
    }
  }

  // Prints out the number of "tilings" using 1 and 2 length tiles
  // of a strip of length n, where prefix stores what has already
  // been tiled.
  public static void printTiles(String prefix, int n) {

    // The tiling is all stored in prefix.
    if (n == 0)
      System.out.println(prefix);

    // Just need to add a tile of size 1 at the end.
    else if (n == 1)
      System.out.println(prefix+"1");

    // There are two options here, one tile of size two, or two
    // tiles of size one.
    else if (n == 2) {
      System.out.println(prefix+"2");
      System.out.println(prefix+"1,1");
    }

    // Otherwise, add one tile of size 2, and recursively tile the
    // rest, AND do the same with a tile of size 1.
    else {
      printTiles(prefix+"2,",n-2);
      printTiles(prefix+"1,",n-1);
    }

  }
}