CSCI 136 Spring 2026

CSCI 136 - Spring 2026

Data Structures

Home | Lectures | Labs | Handouts | 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!

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 in real-world situations when another party has specified the method signature in advance.

PRE-LAB Step 0: Warm-up Problems

For this lab, we have some warm-up problems to help you complete the lab. These warm-up problems have similar structure to the problems on the real lab, but will not be graded—so there are no restrictions on how you solve them. You can work on the Prelab warm-up problems with other students or the TAs. Since the PRE-LAB problems will not be graded, you may discuss code, logic, and anything else (about those problems only) with your classmates. As with everything else in the class, you are not allowed to use LLMs to do these problems.

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 nums[], 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?

Lab Problems

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.

To encourage you to write tests for your methods, there is no autograder for you to test your code on this lab. You should write your own tests and use them to ensure that your code runs correctly.

For each exercise, we specify the method signature. You must keep the method signature the same (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.

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)

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. An empty space counts as a palindrome, and capital letters cound as distinct from lowercase (so "Dad" is not a palindrome). You will need to use the charAt() String method; see the Java String class description for details.

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 subsequences of str, one per line. For example, if we call:

           subsequences("ABC")

We should get the following lines as output. These lines may be in any order. Note that the first line is empty, to represent the empty string.
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 are 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. You will want to use Java String methods to help you here.

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)

Style requirements:

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). You can see details, as well as the other style requirements in the course, in the code style guide. Please check over your code and make sure you are following these requirements.

Task 7: Submit

Submit your code to Gradescope (Lab 04) and ensure it passes all autograder tests. For this lab, the autograder tests will not be very useful for debugging—you should write your own tests to ensure correctness.

It's time to add, commit and push your file. Enter each of the following commands into your terminal one at a time. (The pdf instructions from Lab00 have more extensive instructions for how to do this.)

git add Recursion.java
git commit -m "finished with lab 4"
git push

After you commit, log into evolene.cs.williams.edu. Click on your repo, then Lab04, then Recursion.java, and make sure that you can see the modifications you made. If you can see the changes, you're all set! If you finish early, please talk to one of the instructors to make sure everything is in the right place before you leave.