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:
()", "[]", 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:
soFar), and
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:
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)
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}).
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:
/**).
@param tag is "required" (by convention) for
every parameter, even when the description is obvious.
@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.)
@pre tag is used for preconditions, (when
applicable)
@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:
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.)
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).
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.mdRubric.mdProblems.mdRecursion.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 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:
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.
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.
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).