public class Recursion {
	
    /* Precondition: n > 0
       Postcondition:  returns the nth number in a sequence where each
       element is twice its predecessor, and starts with 1.
    */
    public int sequence1(int n){
	if (n == 1)
	    return 1;
	return 2 * sequence1(n-1);
    }

    public int sequence1a(int n){
	return sequence1aHelper(n,1);
    }
	
    public int sequence1aHelper(int n, int value) {
	if (n == 1)
	    return value;
	return sequence1aHelper(n-1,value*2);
    }
    
    /* Precondition: n > 0
       Postcondition:  returns the nth number in a sequence where each
       element is the sum of the previous 3, and starts with 1,2,3
    */
    public int sequence2(int n){
	if (n == 1)
	    return 1;
	if (n == 2)
	    return 2;
	if (n == 3)
	    return 3;
	return sequence2(n-3) + sequence2(n-2) + sequence2(n-1);
    }
		
    public int sequence2a(int n){
	return sequence2aHelper(n, 1,2,3);
    }
		
    public int sequence2aHelper(int n, int v1, int v2, int v3) {
	if (n == 1)
	    return v1;
	if (n == 2)
	    return v2;
	if (n == 3)
	    return v3;
	return sequence2aHelper(n-1,v2,v3,v1+v2+v3);
    }

    /* Precondition:  word is an instance of String
       Postcondition:  returns true if word is a palindrome, and false otherwise
    */
    public boolean palindrome(String word){
	if (word.length() == 0 || word.length() == 1)
	    return true;
	if (word.charAt(0) != word.charAt(word.length()-1))
	    return false;
	return palindrome(word.substring(1,word.length()-1));
    }
	
    /* Precondition: n >= 1
       Postcondition: returns the appropriate star pattern for the value of x
    */
	
    public String starString(int n){
	if (n == 0)
	    return "";
	return nstars(n) + "\n" + starString(n-1);
    }
	
    public String nstars(int n) {
	if (n == 0)
	    return "";
	return "*" + nstars(n-1);
    }


    //======================================================================
    public static void main(String args[]){

	Recursion rec = new Recursion();

	System.out.println("sequence1(5) = " + rec.sequence1(5) + ". It should be 16.");
	System.out.println("sequence1(7) = " + rec.sequence1(7) + ". It should be 64.");

	System.out.println("sequence2(4) = " + rec.sequence2(4) + ". It should be 6.");
	System.out.println("sequence2(7) = " + rec.sequence2(7) + ". It should be 37.");


	System.out.println("\'car\' is a palindrome?: " + rec.palindrome("car"));
	System.out.println("\'racecar\' is a palindrome?: " + rec.palindrome("racecar"));
	System.out.println("\'hannah\' is a palindrome?: " + rec.palindrome("hannah"));
	System.out.println("\'banana\' is a palindrome?: " + rec.palindrome("banana") + "\n");
		
	System.out.println(rec.starString(5));
    }
}