Discussion 4: Recursive Methods

Solutions

Download Solution Code download
Exercise 1: Method Implementation
(a)

Input Formatting:

It will be helpful to first format the input String s before we start our recursive implementation. Think carefully on how to format the String by looking at the examples above.

We can convert String s to lowercase, by reassigning s = s.toLowerCase();. This will make our palindrome computation case-insensitive.
(b)

Identify the Base Cases:

Inside the isPalindrome() method, first check for the simplest possible inputs. When can we directly know that a String is a palindrome without needing to do any work?

When a String has length 0 or 1, it is automatically a palindrome.
(c)

Implement the Recursive Step:

If the input is not a base case, you must shrink the problem and call the method again on a smaller piece. What smaller String should be the argument to this recursive call, and how do we obtain this smaller String? How should we use the result of the recursive call to finish our definition of the method?

When we check for a palindrome, we first must guarantee that the first character of the String is the same as the last character (which would become the first character if the String were reversed). After we confirm this, we need to check if the middle substring (after "peeling off" the first and last characters) is a palindrome. If it is, the entire String is a palindrome. We can obtain this middle substring via the call s.substring(1,s.length()-1). We should return true only when both checks (the outer characters and the middle substring) succeed, which we can accomplish with the boolean && operator.
(d)

Code up your Implementation:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

/**
 * Returns whether `s` is a palindrome (ignoring case-sensitivity), meaning it 
 * reads the same forwards and backwards. 
*/
static boolean isPalindrome(String s) {
  int len = s.length();
  if (len <= 1) {
    return true;
  }
  s = s.toLowerCase();
  return s.charAt(0) == s.charAt(len - 1) && isPalindrome(s.substring(1, len - 1));
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

/**
 * Returns whether `s` is a palindrome (ignoring case-sensitivity), meaning it 
 * reads the same forwards and backwards. 
*/
static boolean isPalindrome(String s) {
  int len = s.length();
  if (len <= 1) {
    return true;
  }
  s = s.toLowerCase();
  return s.charAt(0) == s.charAt(len - 1) && isPalindrome(s.substring(1, len - 1));
}
Exercise 2: Complexity Analysis
Given a String of length \(N\), let's think about the time and space complexity of the isPalindrome() method.
(a)

Describe the best-case and worst-case inputs of length \(N\). What properties will they have?

A best-case input will have different first and last letters. Since these are the first thing that are checked in the recursive case the method can return false before a recursive call is made. (Here, we're using the short-circuiting property of Java's && operator.)

For a String of length \(N\), the worst case happens when we need to inspect every character before recursing to a base case. This occurs for any string that is a palindrome.

(b)

Choose a worst-case input of length 8 and draw a memory diagram that depicts the state of the runtime stack at the point just before returning from the base case.

We'll use the input "abcddcba".
(c)

Based on your diagram, what are the maximum call stack depth and total number of recursive calls, both expressed in terms of \(N\)? Give both exact answers and big-O complexity classes.

Since the recursive case always makes at most one recursive call, the maximum stack depth and total number of recursive calls will be the same. As each recursive call "peels off" two characters from each the end of the String the total number of calls will be \(\lceil \frac{N+1}{2} \rceil = O(N)\).
(d)

Determine the runtime complexity of the non-recursive work done during the execution of the isPalindrome() method on a String of length \(k\). By summing this over all of the recursive calls in the stack, what is the overall time complexity of isPalindrome() in terms of the original input length \(N\)?

In our solution, computing the String's length and checking for (and executing the return in) the base case are an \(O(1)\) operations. Converting the String to lowercase is an \(O(k)\) operation. Comparing the first and last characters requires \(O(1)\) time. Finally, computing the substring for the recursive call argument requires \(O(k)\) time. Overall, this means the isPalindrome() method does \(O(k)\) non-recursive work for an input of length \(k\). Summing this over the recursive calls gives overall time complexity \(O(N^2)\) for an original input of length \(N\) (by a similar calculation to the hasDuplicates() method from lecture).
(e)

How much additional memory space is allocated during the execution of one call to isPalindrome() on a String of length \(k\)? By summing this over all of the recursive calls in the stack, what is the overall space complexity of isPalindrome()?

Constructing the lowercase String and the substring in each method call uses an additional \(O(k)\) memory. Summing this over the recursive calls (and adding in the \(O(N)\) space from the call frames, which is dominated anyway) gives overall space complexity \(O(N^2)\) for an original input of length \(N\).
Exercise 3: Improving the Complexity
We can improve both the time and space complexity of isPalindrome() by adopting a similar strategy to the "array views" that we saw in lecture. Define a recursive helper method rangeIsPalindrome(String s, int start, int end) that returns whether s.substring(start, end) is a palindrome, and use this to re-implement isPalindrome() (which should only handle the pre-processing and call this helper method), and analyze the time and space complexities of this alternate definition. 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

/**
 * Returns whether `s.substring(start, end)` is a palindrome. This method should 
 * be recursive and should not construct any new `String` objects during 
 * its execution. Requires that `s` consists of only characters from 
 * 'a'-'z', and `0 <= start <= end < s.length`.
 */
static boolean rangeIsPalindrome(String s, int start, int end) {
  if (end - start <= 1) {
    return true;
  }
  return s.charAt(start) == s.charAt(end - 1) && rangeIsPalindrome(s, start + 1, end - 1);
}

/**
 * Returns whether `s` is a palindrome (ignoring case-sensitivity), meaning it 
 * reads the same forwards and backwards.
 */
static boolean isPalindrome(String s) {
  s = s.toLowerCase();
  return rangeIsPalindrome(s, 0, s.length);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

/**
 * Returns whether `s.substring(start, end)` is a palindrome. This method should 
 * be recursive and should not construct any new `String` objects during 
 * its execution. Requires that `s` consists of only characters from 
 * 'a'-'z', and `0 <= start <= end < s.length`.
 */
static boolean rangeIsPalindrome(String s, int start, int end) {
  if (end - start <= 1) {
    return true;
  }
  return s.charAt(start) == s.charAt(end - 1) && rangeIsPalindrome(s, start + 1, end - 1);
}

/**
 * Returns whether `s` is a palindrome (ignoring case-sensitivity), meaning it 
 * reads the same forwards and backwards.
 */
static boolean isPalindrome(String s) {
  s = s.toLowerCase();
  return rangeIsPalindrome(s, 0, s.length);
}
In this alternate implementation, there are still \(O(N)\) recursive calls. However, now both the non-recursive work done in each call and the memory allocation in each call are \(O(1)\). This means results in improved \(O(N)\) time and space complexities.