/** Lab 06. Writing recursive methods */
public class Rec {
    
    /** = " number of times c occurs in s */
    public static int number(char c, String s) {
        if (s.length() == 0)
            return 0;
        
        // { s has at least 1 character }
        if (s.charAt(0) != c)
            return number(c, s.substring(1));
        
        // { first character of s is c}
        return 1 + number(c, s.substring(1));
    }
    
    /** = String s with each character duplicated */
    public static String dup(String s) {
        if (s.length() == 0)
            return s;
        
        // { s has at least 1 character }
        return "" + s.charAt(0) + s.charAt(0) + dup(s.substring(1));
    }

    /** = " s but with the first occurrence of 
        character c removed (if present) */
    public static String removeFirst(String s, char c) {
        if (s.length() == 0)
            return s;
        
        // { s has at least one character }
        if (s.charAt(0) == c)
            return s.substring(1);
        
        // { the first character of s is not c}
        return s.charAt(0) + removeFirst(s.substring(1),c);
    }

    /** = " s but with all occurrences of character c removed */
    public static String removeC(String s, char c) {
        if (s.length() == 0)
            return s;
        
        // { s has at least one character }
        if (s.charAt(0) == c)
            return removeC(s.substring(1),c);
        
        return s.charAt(0) + removeC(s.substring(1),c);
    }
    
    /** = the reverse of s. e.g. rev("abc") is "cba".
          Do this one using this idea. To reverse a string
          that contains at least 2 characters, switch the
          first and last ones and reverse the middle.
     */
    public static String rev(String s) {
        if (s.length() <= 1)
            return s;
        
        // { s has at least two characters }
        int k= s.length()-1;
        return s.charAt(k) + rev(s.substring(1,k)) + s.charAt(0);   
    }
    
    /** = Fibonnaci number F(n).
          Precondition: n ³0.
          Definition: F(0) = 0, F(1) = 1, and
          for n > 1,  f(n) = f(n-1) + F(n-2).
          E.g. the first 10 Fibonnaci numbers are
             0, 1, 1, 2, 3, 5, 8, 13, 21, 34 */
    public static int Fib(int n) {
        if (n <= 1)
            return n;
        
        // {n > 1}
        return Fib(n-1) + Fib(n-2);
    }

    /** Compute b ** c, i.e. b multiplied by itself c times.
        Also called b "to the power" c.
        Precondition: c ³ 0
        Hints: b ** 0 = 1.
               if c is even, b**c == (b*b) ** (c/2)
               if c > 0, b**c =  b * (b ** (c-1)) */
    public static int exp(int b, int c) {
        if (c == 0)
            return 1;
        
        // { c > 0 }
        if (c % 2 == 0)
            return exp(b*b, c/2);
        
        // { c > 0 and c is odd }
        return b * exp(b, c-1);
    }
    
}