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

• Draw memory diagrams that visualize the state of execution of a program involving multiple method calls and/or recursion.
• Develop recursive methods in Java given their specifications.
• 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.

Reminder: Discussion Guidelines

The work that you complete in discussion serves as a formative assessment tool, meaning it offers the opportunity to assess your understanding of the material and for our course staff to get a “pulse” on how things are going so we can make adjustments in future classes. Your grade in discussion is based entirely on attendance and participation; if you show up and you are actively engaged with the activity (working on the activity on your computer, discussing the activity with your group, asking and answering questions, etc.) for the entire 50-minute section period, you will earn full credit. If you complete the activity early, helping other students is a great way to further your own understanding. You do not need to submit any of the work that you complete during discussion.

Since discussion activities are not graded for correctness, we do not place any restrictions on resources that you may use to complete them, which include notes, books, unrestricted conversations with other students, internet searches, and the use of large language models or other generative AI. We advise you to be pragmatic about your use of these resources and think critically about whether they are enhancing your learning. Discussion activities are intended to serve as “strength training” for programming tasks we will expect on assignments and exams (and that you will encounter in future courses and careers), and their main benefit comes from critically thinking to “puzzle” them out.

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 (and, as a challenge extension, remove all non-alphanumeric characters).

Some examples of a Palindrome include:

• "racecar" is a palindrome.
• "Madam" is a palindrome (ignoring case).
• "hello" is not a palindrome.
• "a" is a palindrome (start thinking about base cases!).
• "" (empty string) is also a palindrome.

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.

Useful String Methods

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

1. 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).

1
2

String s = "hello";
int len = s.length(); // len is 5

1
2

String s = "hello";
int len = s.length(); // len is 5

2. 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).

1
2
3

String s = "Java";
char first = s.charAt(0);             // first is 'J'
char last = s.charAt(s.length() - 1); // last is 'a'

1
2
3

String s = "Java";
char first = s.charAt(0);             // first is 'J'
char last = s.charAt(s.length() - 1); // last is 'a'

3. 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(\texttt{endIndex} - \texttt{beginIndex})\), the length of the substring that is constructed and returned.

1
2

String s = "racecar";
String sub = s.substring(3, s.length() - 1); // returns the substring "eca"

1
2

String s = "racecar";
String sub = s.substring(3, s.length() - 1); // returns the substring "eca"

4. 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.

1
2

String s = "Madam";
String lower = s.toLowerCase(); // lower is "madam"

1
2

String s = "Madam";
String lower = s.toLowerCase(); // lower is "madam"

5. boolean isEmpty()

[Documentation] This method is a convenient shortcut that returns true if, and only if, length() is 0. It runs in \(O(1)\) time (constant, not depending on the length of the String).

1
2
3
4

String s1 = "";
String s2 = "a";
boolean b1 = s1.isEmpty(); // b1 is true
boolean b2 = s2.isEmpty(); // b2 is false

1
2
3
4

String s1 = "";
String s2 = "a";
boolean b1 = s1.isEmpty(); // b1 is true
boolean b2 = s2.isEmpty(); // b2 is false