# CS1027b Computer Science Fundamentals II

## Lab 8

### General lab instructions to help labs run smoothly

• Read through the lab instructions before coming to the lab.
• Do the pre-lab preparation.

Upon completion of this lab, you should be able to understand recursive thinking in the solution of a simple problem.

### Overview and preparation

Upon completion of this lab, you should be able to understand how recursive algorithms work. For prepation, review the lecture notes on recursion.

### Exercise 0

You should be able to answer the following questions correctly in order to be successful in Exercises 1 and 2.

Consider the string defined by `String sample = "CS 1027b";` What would be returned by each of the following method calls?
• sample.length()
• sample.charAt(1)
• sample.charAt(sample.length()-1)
• sample.substring(0, 1)
• sample.substring(0,sample.length())
• sample.concat(sample)

### Exercise 1

Download the file RecursionLab.java. Your task is to fill in the code for a recursive method that prints a string backwards. For example, for the parameter string "Java", your method would print "avaJ". The header of this method is ```public static void reversePrint(String inString)``` Note that the method is static, i.e. it is a class method, and will not be invoked on an object. (See the `main` method to see how it is invoked.)

Hints

• Think about the problem of printing a string in reverse recursively by considering an example string, say "abcd". To print it in reverse:
• The first character to be printed would be the character "d" (which is the last character of the string). We are then left with the problem of printing a smaller string, "abc" in reverse. (Note that it's the same problem, only with a smaller string)
• Print its last character, "c". We are then left with the problem of printing the smaller string "ab" in reverse.
• Print its last character, "b". We are then left with the problem of printing the smaller string "a" in reverse.
• Print its last character, "a". We are then left with the problem of printing the empty string in reverse.
• Generalize that into an algorithm for the method `reversePrint`
```if the parameter string is empty (the base case)
return from the method
else
print the last character of the parameter string
call reversePrint with the substring that does not include the last character as the parameter
```
You can simplify the algorithm, by instead using the test `if the string is not empty.` You should be able to write the algorithm using just the `String` methods `charAt`, `substring` and `length`.

### Exercise 2

Now you will write a recursive method that returns the reverse of a string. For example, for the parameter string "Java", your method would return the string "avaJ". The header of your method should be `public static String reverseString(String inString)` Add this method to the file `RecursiveLab.java`

Hints

• The algorithm should be
```if the parameter string is empty (the base case)
return the null string as the result string
else
result string is the last character of the parameter string, concatenated with
the reverse of the substring that does not include the last character
return the result string
```
You should be able to write the algorithm using just the `String` methods `charAt`, `substring`, `concat` and `length`.

Add the following code to the main method in RecursionLab.java to test your reverseString method:

```// test reverseString
String revString = reverseString(inString);
System.out.println(revString);
```

### Optional exercises (will not be marked)

Write a program that asks the user to input a string and then uses method `reverseString` to determine whether or not the string is a palindrome. A palindrome is a sequence of characters that reads the same both forwards and backwards, for example mom, radar, racecar.

Finally, write a recursive method with the header `public static boolean isPalindrome(String s)` that returns `true` if the parameter string is a palindrome and `false` if it is not.