CSCI 136 :: Spring 2021

Data Structures & Advanced Programming

Home | Schedule | Labs | Handouts | Links | CS@Williams

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.

If you have questions about this requirement, please ask us!

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:

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:

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:

                public static boolean printSubsetSum(int nums[], int targetSum)

                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:

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:

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

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:

The 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 file will ask us to provide the running time (in big-O notation) for each method—with a brief justification. 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:

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

Submitting Your Lab

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.

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