CS161 Lab Week 7: Recursion

In this lab you will be writing recursive methods to

Print star patterns (wee!)
Find palindromes
Create recursive sequences

all without loops!

Start with this Java file:

public class Recursion {

    // Define methods here

    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));
    }
}

Implement the following methods and test them with the above main method.

public String starString(int n)

This method returns a String of stars (asterisks) with n stars on the first line, n-1 stars in the second line, and continuing until the last line has 0 stars. So, for a value of n=5, the String should be

*****
****
***
**
*

That last line is a blank.

public boolean palindrome(String word)

This method is given a String and returns true if the string is a palindrome and false otherwise. The result is true for "abccba", "abcba", "x y z y x", but not for "abc", "a bc", and "junk".

public int sequence1(int n)

This method returns the nth number in a sequence where each element is twice its predecessor, and starts with 1. The sequence is

1 2 4 8 16 32 64 128 ...

If n is 4, then this method must return 8.

public int sequence2(int n)

This method returns the nth number in a sequence where each element is the sum of the previous 3, and starts with 1,2,3. The sequence is

1 2 3 6 11 20 37 ...

If n is 5, then this method must return 11.

Remember, no loops! And also remember, recursive methods start with a a base case followed by the recursive case.