CSCI 136 :: Spring 2021

Recursion, Recursion, Recursion, ...

We love recursion. Recursion is a powerful design technique, but it can be a difficult concept to master, and it is worth concentrating on in isolation before using in large programs. Thus, this week's lab is structured as several small problems that can be solved separately from one another—although we suggest you work on them in the order given!

The goals of this lab are to:
• Practice writing recursive programs.
• Solve a variety of interesting algorithmic problems.
• Train your brain to think recursively.

Recursive solutions can often be formulated in just a few concise, elegant lines, but they can be very subtle and hard to get right. A small error in a recursive method gets magnified by the many recursive calls and so an incorrect method can have somewhat surprising behavior. Although each problem will have a fairly short solution, it may take you a while to find it—give it time!

A Note on Working With a Partner

There are multiple approaches for carrying out a programming assignment with a partner. In this course, the purpose is to provide the opportunity for two students to work jointly to develop and implement algorithms for solving problems. This is the approach we require partners to follow.

In particular, we prohibit partners from taking the approach of "dividing up the work" and then working separately on their individual "subprojects". Instead, we would like you to do pair programming: one student is assigned to be the typer, while the other looks on. The students work together to decide how to move forward at a given moment—the onlooker gives ideas and proofreads the code, while the typer discusses their thinking and writes the code. The two students switch roles every 5-10 minutes.

The Tao of Recursion

Take time to figure out how each problem is recursive in nature and how you could formulate the solution to the problem if you already had the solution to a smaller, simpler version of the same problem. You will need to depend on a recursive "leap of faith" to write the solution in terms of a problem you haven't solved yet. Be sure to take care of your base case(s) lest you end up in infinite recursion—which can have somewhat spectacular (not in the good way) results....

Also, as you'll see below, sometimes a method signature doesn't provide the right number or types of parameters to allow us to directly implement it recursively. In such situations we have that method call a recursive helper method, for which we can choose the most appropriate set of parameters. Note: this situation frequently arises when another party has specified the method signature in advance (welcome to the real world).

The great thing about recursion is that once you learn to think recursively, recursive solutions to problems seem very intuitive. (Did we mention that we love recursion...?) Spend some time on these problems and you'll be much better prepared when you are faced with more sophisticated recursive problems in the wild.

PRE-LAB Step 0: Warm-up Problems

Given the structure of this lab, a full design document is not required this week. However, as always, you should read through the lab carefully and think about how you will structure your solutions. If possible, sketch a written design for the warm-up problems described below, and bring it to lab.

Brainstorming can be very useful when learning to think recursively. This is why we encourage you to work with a partner in lab this week, if you'd like. You can work on the Prelab warm-up problems before lab with a larger group, even if you do not work with that group during the rest of the lab. Since the PRE-LAB problems will not be graded, you may discuss code, logic, and anything else (about those problems only) with your classmates.

PRE-LAB Warmup Problem 0.1: Digit Sum

Write a recursive method `digitSum` that takes a non-negative integer and returns the sum of its digits. For example, `digitSum(1234)` returns `1 + 2 + 3 + 4 = 10`. Your method should take advantage of the fact that it is easy to break a number into two smaller pieces by dividing by 10. Recall that integer division truncates (e.g., `1234/10 = 123`) and the mod operation yields the remainder (e.g., `1234%10 = 4`).

For these methods, we do not need to construct any objects. Therefore, you can declare them to be `static` methods and call them directly from `main`:

``````
public static int digitSum(int n) { ... }
``````

PRE-LAB Warmup Problem 0.2: Subset Sum

Subset Sum is an important and classic problem in computer science. Given a set of integers and a target number, your goal is to find a subset of those numbers that sum to the target number. For example, given the set `{3, 7, 1, 8, -3}` and the target sum `4`, the subset `{3, 1}` sums to `4`. On the other hand, if the target sum were `2`, we have a problem: there is no subset that sums to `2`. For this warm-up problem, we do not ask you to identify any particular subset; instead, we want you to return `true` if there exist one or more subsets that sum to the target number, and false otherwise. The prototype for this method is:

``````
public static boolean canMakeSum(int setOfNums[], int targetSum)
``````

Assume that the array contains `setOfNums.length` numbers (i.e., it is completely full). Note that you are not asked to print the subset members, just return `true` or `false`. You will likely need a helper method to pass additional information through the recursive calls. What additional information would be useful to track?

By the way, no one has yet discovered an efficient algorithm to solve this problem, where efficient means "runs in O(p(n)) time for some polynomial p(n))". If you are the first to do so, the Clay Mathematics Institute will pay you \$1,000,000. Even an algorithm that runs in O(n1000) time would qualify! Just sayin'....

Lab Programs

For each problem below, you must thoroughly test your code to verify it correctly handles all reasonable cases. For example, for the "Digit Sum" warm-up, you could use test code to call your method in a loop to allow the user to repeatedly enter numbers that are fed to your method until you are satisfied. Testing is necessary to be sure you have handled all the different cases. You can leave your testing code in the file you submit—there is no need to remove it.
For each exercise, we specify the method signature. Your method must exactly match that prototype (same name, same arguments, and same return type). You may need to add additional helper methods for some of these questions; these functions may have different arguments but must have the same return type. Your solutions must be recursive and contain no loops, even if you can come up with an iterative alternative.

Problem 1: Counting Cannonballs

Spherical objects, such as cannonballs, can be stacked to form a pyramid with one cannonball at the top, sitting on top of a square composed of four cannonballs, sitting on top of a square composed of nine cannonballs, sitting on top of a square composed of sixteen cannonballs, and so forth. Write a recursive method `countCannonballs` that takes as its argument the height of a pyramid of cannonballs and returns the number of cannonballs it contains. The prototype for the method should be as follows:

``````
public static int countCannonballs(int height)
``````

Note: Are there any pre-conditions to ```countCannonBalls(int height)```? For any of the `public` methods that have preconditions or postconditions, please document those in your comments, and check with an assertion.

Problem 2: Palindromes

Write a recursive method `isPalindrome` that takes a string and returns true if it is the same when read forwards or backwards. For example,

```	isPalindrome("mom")   → true
isPalindrome("cat")   → false
isPalindrome("level") → true
```

The prototype for the method should be as follows:

``````
public static boolean isPalindrome(String str)
``````

You may assume the input string contains no spaces.

Special cases: Is the empty string a palindrome? Does capitalization matter (e.g., is "Dad" a palindrome?). Please document your choice(s) in your comments so it is clear how your program is expected to behave.

Problem 3: Balancing Parentheses

In the syntax of most programming languages, there are characters that occur only in nested pairs, called bracketing operators. Java, for example, has these bracketing operators:

```            ( . . . )
[ . . . ]
{ . . . }
```

In a properly formed program, these characters will be properly "nested" and "matched". To determine whether this condition holds for a particular program, you can ignore all the other characters and look simply at the pattern formed by the parentheses, brackets, and braces. In a legal configuration, all the operators match up correctly, as shown in the following example:

```            { ( [ ] ) ( [ ( ) ] ) }
```

The following configurations, however, are illegal for the reasons stated:

```	( ( [ ] )      → The line is missing a close parenthesis.
) (            → The close parenthesis comes before the open parenthesis.
{ ( } )        → The parentheses and braces are improperly nested.
```

Write a recursive method

``````
public static boolean isBalanced(String str)
``````

that takes a string `str` from which all characters except the bracketing operators have been removed (precondition?). The method should return `true` if the bracketing operators in `str` are balanced, which means that they are correctly nested and matched. If the string is not balanced, the method returns `false`.

Although there are many other ways to implement this operation, you should code your solution so that it embodies the recursive insight that a string consisting only of bracketing characters is balanced if and only if one of the following conditions holds:

• The string is empty.
• The string contains "`()`", "`[]`", or "`{}`" as a substring and is still balanced if you remove that substring.

For example, the string "`[(){}]`" is shown to be balanced by the following chain of calls:

```          isBalanced("[(){}]")   →
isBalanced("[{}]")   →
isBalanced("[]")   →
isBalanced("")   → true
```

Hint: Using the above example, can you reason backwards about how the code might be structured?

Problem 4: Subsequences

Write a method:

``````
public static void subsequences(String str)
``````

that prints out all subsequences of the letters in `str`. For example:

```           substring("ABC") → "", "A", "B", "C", "AB", "AC", "BC", "ABC"
```

The order that you print them does not matter. You may find it useful to write a helper method, such as:

``````
protected static void subseqHelper(String str, String soFar)
``````

In our implementation, this helper is initially called as `subseqHelper(str, "")`. We use the variable `soFar` to keep track of the characters that currently in the subsequence we are building.

To process `str` you must:

• build all subsequences containing the first character (which you do by including that character in `soFar`), and
• build all subsequences not including the first character (leaving `soFar` unchanged).

Continue until `str` has no more characters in it.

Problem 5: Print In Binary

Although we are used to referring to numbers in decimal computers represent integers as sequences of bits. A bit is a single digit in the binary number system and can therefore have only the value `0` or `1`. The table below shows the first few integers represented in binary:

```          binary | decimal
-------|--------
0 | 0
1 | 1
10 | 2
11 | 3
100 | 4
101 | 5
110 | 6
```

Each entry in the left side of the table is written in its standard binary representation, in which each bit position counts for twice as much as the position to its right. For instance, you can demonstrate that the binary value `110` represents the decimal number `6` by following this logic:

```          place value   → 4   2   1
×   ×   ×
binary digits → 1   1   0
↓   ↓   ↓
4 + 2 + 0 = 6
```

Basically, this is a base-2 number system instead of the decimal (base-10) system we are familiar with. Write a recursive method

``````
public static void printInBinary(int number)
``````

that prints the binary representation for a given integer. For example, calling `printInBinary(3)` would print `11`, and `printInBinary(42)` would print `101010`. Your method may assume the integer parameter is always non-negative (precondition?).

Hint: You can identify the least significant binary digit by using the modulus operator with value 2 (i.e., `number % 2`). For example, given the integer 35, the value `35 % 2 = 1` tells you that the last binary digit must be `1` (i.e., this number is odd), and division by `2` gives you the remaining portion of the integer (`17`).

Hint: You will probably want to use the method `System.out.print` in the problem. It is just like `System.out.println`, but does not follow the output with a new line.

Problem 6: Extending Subset Sum

For the last problem, you are to write two modified versions of the `canMakeSum` PRE-LAB problem:

• Rather than returning `true` or `false`, change the method to print the members in a successful subset if one is found. You should do this without adding any new data structures (i.e. don't build a second array to hold the subset). Instead, use the "unwind" of the recursive calls.
``````
public static boolean printSubsetSum(int nums[], int targetSum)
``````
• Rather than returning `true` or `false`, change the method so that it returns the total number of all possible subsets. For example, in the set shown earlier, the subset `{7, -3}` also sums to `4`, so there are two possible subsets for the target value `4` (i.e., `{3, 1}` and `{7, -3}`).
In this method, you do not need to print all of the subsets, only return the number of subsets.
``````
public static int countSubsetSumSolutions(int nums[], int targetSum)
``````

`checkstyle` requirements:

For this week's lab, we will be adding one new `checkstyle` rule to the set of rules that we have used in previous weeks. We would like you to include Javadoc-style comments for each `public` method (it is OK to include them for `protected` and `private` methods as well, but it is not required). The description of the Javadoc comment format is available on the Oracle website, but we have replicated the important rules (for us in CS136) here:

• Each line above is indented to align with the code below the comment.
• The first line contains the begin-comment delimiter (`/**`).
• Write the first sentence as a short summary of the method
• An `@param` tag is "required" (by convention) for every parameter, even when the description is obvious.
• The `@return` tag is required for every method that returns something other than `void`, even if it is redundant with the method description. (Whenever possible, find something non-redundant (ideally, more specific) to use for the tag comment.)
• The `@pre` tag is used for preconditions, (when applicable)
• The `@post` tag is used for postconditions (when applicable)

In this lab, like last week, we have provided starter code that already contains Javadoc comments (however, we have left some parts for you to fill in). This will not always be the case in future labs, so please take this chance to familiarize yourself with the Javadoc format.

We STRONGLY ENCOURAGE you to run checkstyle early and often when developing your code, and try to program in a way that minimizes WARNING messages. The checkstyle rules that we use in this course are based on real-world style guides; internalizing good style practices will help us write more readable code.

In total, checkstyle will enforce the following guidelines:

• All class variables that are not `final` must be declared `private` or `protected` (i.e., no `public` member variables unless they are constants). (We don't expect this to be an issue this week.)
• All `public` methods must include a “Javadoc” comment (starts with `/**` and ends with `*/`; it should include descriptions of the function at the top, descriptions of each arguments after a `@param` and pre/post conditions after the `@pre` or `@post` tags).
• No methods should be longer than 30 lines (excluding whitespace and single-line comments).

To run `checkstyle`, you would type the following command at the terminal:

``````
\$ ./checkstyle
``````

The `./` is peculiar to Unix: it tells the terminal to look for the `checkstyle` program in the current directory. This command will run `checkstyle` on every Java program in your directory. To run `checkstyle` on a specific Java file, type:

``````
\$ ./checkstyle SomeFile.java
``````

Lab Deliverables

You (and your teammate, if you are working in a pair) should have a new private repository available to you on GitLab. Inside the repository, you should see the following files:

• `README.md`
• `Rubric.md`
• `Problems.md`
• `Recursion.java`

The `Recursion.java` file contains starter code, and you should write all of your functions inside that file. Since we are learning about running times and big-O analysis in lecture, for this lab, our `Problems.md` file will ask us to provide the running time (in big-O notation) for each method—with a brief justiﬁcation. These runtimes replace the typical thought questions for this week.

A note on `String` methods: Some of your methods will call `String` methods; therefore, you'll need to know the running time of the `String` methods in order to determine how long your method takes. Here are some tips:

• `indexOf` on a `String` takes O(n) time.
• `substring(a,b)` on a `String` takes O(b-a+1) time—that is to say, it takes time proportional to the size of the returned substring.
• `charAt` on a `String` takes O(1) time.

Let us know if you encounter any `String` methods whose running time you're unsure of.

As you complete portions of this lab, you should `commit` your changes and `push` them. Commit early and often. When the deadline arrives, we will retrieve the latest version of your code. If you are confident that you are done, please use the phrase `"Lab Submission"` as the commit message for your final commit. If you later decide that you have more edits to make, it is OK. We will look at the latest commit before the deadline.
• Verify your changes are visible on GitLab. You should see all changes reflected in the files that you `push`. If not, go back and make sure you have both committed and pushed.
We will know that the files are yours because they are in your `git` repository. Do not include identifying information in the code that you submit. We grade your lab programs anonymously to avoid bias. In your `README.md` file, please cite any sources of inspiration or collaboration (e.g., conversations with classmates). We take the honor code very seriously, and so should you. Please include the statement ```"I am the sole author of the work in this repository."``` in the comments at the top your Java files (or "we" if you worked with a partner).