Discussion 4: Recursive Methods

The goal of today’s discussion is to practice thinking recursively by developing some recursive methods involving Strings. You’ll also get some practice visualizing the call structure of a recursive method and using this to analyze its time and space complexity. As we will soon see, recursion is a powerful tool for developing sorting algorithms such as Merge Sort and Quicksort. It’s also useful when working with data structures such as trees and graphs, for which many natural traversal algorithms are most elegantly expressed recursively.

Learning Outcomes

  1. Visualize the state of the runtime stack in a program involving multiple method calls and/or recursion.
  2. Develop recursive methods in Java given their specifications.
  3. Determine the number of recursive calls and the maximum depth of the call stack of a recursive method and use these to compute its time and space complexities.

The isPalindrome() Method

A String is a palindrome if it reads the same forwards and backwards. For the purpose of this discussion, we’ll ignore case sensitivity.

By applying this definition, we can conclude that:

The goal of this discussion is to gain exposure to recursive thinking using a classic problem that can be defined in terms of smaller, structurally identical problems.

Exercise 1: Method Implementation
In this exercise, you'll develop a static method isPalindrome() that returns whether a given String is a palindrome.
Your task is to give a recursive implementation of this method. Before jumping into the code, it will be helpful to work through the following exercises that offer a structure for designing recursive methods. Some String methods that you may find helpful are listed at the end of this handout.
(a)
Input Formatting: It will be helpful to format the input Strings before we start our recursive implementation. Looking at the examples from earlier, how should we format the String?
(b)
Identify the Base Cases: Inside the isPalindrome() method, we should first check for the simplest possible inputs. When can we directly know that a String is a palindrome without needing to do any work?
(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?
(d)
Code up your Implementation: Use the answers from parts (a)-(c) to complete the recursive implementation of this method.
Exercise 2: Complexity Analysis
Given a String of length \(N\), let's think about the time and space complexities of the isPalindrome() method.
(a)
Describe the best-case and worst-case inputs of length \(N\). What properties will they have?
(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.
(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.
(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\)?
(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()?
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.
(a)
Define a recursive helper method rangeIsPalindrome(String s, int i, int j) that returns whether s.substring(i,j) is a palindrome, and use this to re-implement isPalindrome() (which should only handle the pre-processing and call this helper method).
(b)
What are the time and space complexities of this alternate definition?

Useful String Methods

Here, we summarize some methods from Java’s String class that may be useful for the problems that follow.

int length()

[Documentation] This method returns the number of characters comprising a String and runs in \(O(1)\) time (constant, not depending on the length of the String).

char charAt(int index)

[Documentation] This method returns the character located at the specified index within the String (where the first, leftmost index is 0). It runs in \(O(1)\) time (constant, not depending on the length of the String).

String substring(int beginIndex, int endIndex)

[Documentation] This method returns a new string that is a portion of the original string. The substring begins at beginIndex and extends to the character at endIndex - 1. The endIndex is exclusive. It runs in time \(O(\)endIndex - beginIndex\()\), the length of the substring that is constructed and returned.

String toLowerCase()

[Documentation] This method returns a new string in which all characters have been converted to lowercase. It runs in \(O(N)\) time, where \(N\) denotes the length of the String.