Problem Set 1 FAQ

Problem 6

When I run one of the recursive methods that I’ve written for problem 6, I get a NullPointerException. Do you have any idea of why that might be happening?

A NullPointerException occurs when you try to call a method using a reference variable with a value of null. For example, if you have a variable named str with a value of null and you call str.length(), you will get this exception because there is no object on which the length() method can be invoked. You may need to check first if the value of a reference variable is null before attempting to use it to call a method.
In one of my recursive methods for problem 6, I’m getting a StringIndexOutOfBoundsException. What am I doing wrong?

Don’t forget that the characters in a string have index values that go from 0 to length - 1. The exception means that your code is using an index from outside that range.
In one of my recursive methods for problem 6, I’m using the substring method to create a substring that has everything but the first character from the original string. I’m using the expression s.substring(1, s.length() - 1), but I seem to be losing characters at the end of the string as well.

Don’t forget that the second parameter to the substring method is non-inclusive. So if you want the last character to be included in the substring, your should use the expression s.substring(1, s.length()) – without the “- 1”. Alternatively, you could use the version of substring that only takes a start index: s.substring(1).
I’m having trouble figuring out how to structure the recursive case of one of the recursive methods for problem 6. Do you have any hints on how to do this?

One thing that can help is to consider what should happen for one or more concrete cases – as we did in the example problem that we covered in lecture.

For example, let’s say that you needed to write a recursive removeVowels method. As with many recursive methods that operate on strings, this method should make recursive calls on ever smaller substrings. For example, let’s say that we wanted to do removeVowels("movies")

This would lead to the following sequence of method calls:
```
removeVowels("movies")
    removeVowels("ovies")
        removeVowels("vies")
            removeVowels("ies")
                removeVowels("es")
                    removeVowels("s")
                        removeVowels("")
```
(The last call might not be needed. It depends on which base cases you choose to include.)

Then, once you have the sequence of method calls, you should think about what each of these separate method calls should return, treating them as if they were independent of each other. For example, what should removeVowels("ies") return – i.e., what string will result if the vowels in "ies" were removed? Based on these return values, you should be able to figure out how a given invocation of the method should use the return value from the recursive call to form its own return value.
One of my recursive methods for problem 6 is not working correctly. Do you have any suggestions?

Try tracing through some concrete examples of cases in which the your method is not returning the correct value. You might want to try adding some temporary printlns to see if that helps you to diagnose the problem. In particular, you could print what the method will return before it actually returns it. That will allow you to see when the wrong value is being returned.

In addition, if your method returns a value, make sure that you aren’t throwing away the return value of the recursive call. For example, consider this incorrect version of a recursive method that determines if a string is a palindrome – i.e., if it is a word like “radar” that reads the same in either direction:
```
public static boolean isPal(String s) {  
    if (s == null || s.equals("")) {  
        return true;  
    }  

    // recursive call -- the return value is thrown away
    isPal(s.substring(1, s.length() - 1)); 

    char first = s.charAt(0);
    char last = s.charAt(s.length() - 1);
    if (first != last) {
        return false;
    } else {
        return true;
    }
}
```
This version of the method makes the correct recursive call – looking at the substring consisting of everything except the first and last characters – but it throws away the value that is returned.

To avoid losing the return value of the recursive call, we can do one of two things:
1. assign it to a variable, and then do something with that variable
2. make the recursive call part of a return statement, if doing so makes sense. It may not always make sense – especially if the value that the current method call should return depends on the value that was returned by the recursive call.

Problem 7

I’m having trouble with the recursive trim method. Do you have any suggestions.

First, it’s worth noting that you will likely need an additional base case beyond our usual one for string inputs.

Given the description of what the method is supposed to do, for what cases besides the empty string would it be possible to return the correct solution without needing to make a recursive call?

Second, consider including more than one possible recursive call. The following concrete cases can help in coming up with the different possible calls:
- If the current call is
```
trim("  hello")
```
  what should the recursive call be – i.e., what smaller subproblem would bring me closer to one of my base cases, and would do so in such a way that I could use the solution to the subproblem to determine the solution to the current problem?
- If the current call is
```
trim("hello    ")
```
  what should the recursive call be?
- If the current call is
```
trim("  hello    ")
```
  what should the recursive call be?
Use these and other concrete cases to construct different possible recursive calls, and then include conditional code that makes the appropriate recursive call based on the current value of the input s.