CIS 1100 — Introduction to Computer Programming

Part One: Recursive Exercises

Motivation

Recursion is one of the most powerful tools in computer science. It takes a problem that may be very difficult to solve all at once and lets us solve just one part of it. Then we recursively use that logic on the rest of the problem. In the end, we have solved the greater problem just by doing a little bit of work at each step. Recursion can be used to solve enormous problems with just a few lines of code. In fact, there exist problems that can feasibly only be solved recursively! Recursion plays a major role in not just problem solving, but data structures too, which we will see later in the course. Although it’s conceptually difficult, recursion is an incredibly cool and rewarding thing to learn.

Applications to Other Fields

Recursion doesn’t exist only in computer science. Other fields, like math, linguistics, and logic, all use recursion. In linguistics, for example, we can build sentences out of phrases, and these phrases can contain themselves as subphrases. For example, we can have a phrase of “big friendly giant”, which consists of an adjective, “big”, and a subphrase of “friendly giant”, which consists of an adjective, being “friendly”, and a subphrase, being “giant”. This fact means that we can make sentences that are infinitely long - all we have to do is add another level of recursion to our phrases!

Goals

The purpose of this assignment is to gain practice with recursion. The specific goals are to:

Complete a set of recursion exercises
Practice writing recursive functions (and helper functions)
Use recursion to draw a cool fractal system (Sierpinski carpet)

Setting Up

In the Recursion Finger Exercise portion of this assignment, you will create a class of functions that each perform a different task in a recursive fashion. Solutions using iteration (for/while loops) will be given no credit. You are responsible for writing proper header comments for the class and for all the functions you will write.

You are given some JUnit tests that you can use to test your code, but you will also need to write some of your own test cases, as the tests you are given are not comprehensive nor representative of the complete testing suite you will be graded with.

You should create two (initially empty) java files in Codio - FingerExercises.java and Sierpinski.java. You should also see FingerExercisesTests.java, which contains the tests you have been given, and FingerExercisesStudentTests.java, which is where you will write your own test cases. If you need the original files, you can download them here.

Finger Exercises

For the exercises below, we have provided the method header and problem description. You may find it necessary to write helper methods for these methods if you think you need more input parameters than the provided public methods have.

Important: Note that, although there are 7 problems outlined, you only need to choose 5 of them to implement. You should comment out the tests in FingerExercisesTests.java for the functions you are not implementing, so that the file compiles.

Important: If you implement more than 5, we will grade the first 5 functions in FingerExercises.java only. Any additional functions will automatically fail the autograder - if you’d like to see the tests for later functions from the autograder, comment out the first ones you did.

Here’s an example of a problem that doesn’t use a helper method. In the code below, String.substring(x,y) is inclusive for x and exclusive for y.

public static boolean isPalindrome(String word) {

    // base case - length is 0 or 1, and therefore is a palindrome.
    if (word.length() <= 1) {
        return true;
    }

    // check if first and last are the same
    char firstChar = word.charAt(0);
    char lastChar = word.charAt(word.length() - 1);
    boolean firstAndLastMatch = firstChar == lastChar;

    // if they match, recurse on the string without the first and last letters
    return firstAndLastMatch && isPalindrome(word.substring(1, word.length() - 1));
}

We of course could have solved this with a helper like this:

public static boolean isPalindrome(String word) {

    // return our recursive helper since we want another parameter
    return isPalindromeHelper(0, word);
}

public static boolean isPalindromeHelper(int index, String word) {

    // base case is we are halfway through the word and it's still a palindrome
    if (index >= word.length() / 2) {
        return true;
    }

    char firstChar = word.charAt(index);
    char lastChar = word.charAt(word.length() - 1 - index);
    boolean firstAndLastMatch = firstChar == lastChar;

    // recurse on rest if they match - otherwise, we will return false
    return firstAndLastMatch && isPalindromeHelper(index + 1, word);
}

Both solutions are equally valid - if you want to solve a problem using a helper method, you will not be penalized for doing so if there exists an implementation without the helper. You should approach these problems in the way that makes the most sense to you.

Tip: Remember to start by thinking about the base case — the smallest, simplest problem possible. From there, work out a way to get from a larger input down to the base case.

Tip: Be aware of the invariants that are given. Invariants are properties that will always hold true for the given problem.

Tip: If you can’t decide whether a helper method will help make the solution easier, think about the arguments you want to pass in during a recursive call. If your arguments for a recursive call differ in number or type vs. the header of the function you want to help, think about how a helper can resolve that conflict for you.

1. Greatest Common Denominator (GCD)

Method Header: public static int gcd(int a, int b)

Problem Description: The Greatest Common Denominator (GCD) of two integers, $a$ and $b$, is the largest number that divides both values. One way to solve this problem is to find the prime factorization of both $a$ and $b$ and return the product of the common factors. That way takes a long time, and we can do it smarter! Euclid came up with an algorithm for this problem long before computer science existed.

If $a < b$, return $GCD(b,a)$
If $a = b$, return $b$
If $b = 0$ return $a$.
Otherwise, return $GCD(b, a \% b)$

Invariants: You may assume that $a$ and $b$ are non-negative integers. 0 is a non-negative integer, but you may also assume that it will never be the case that both $a$ and $b$ are 0. However, it is possible for one of the two inputs to be 0. That is, $GCD(0, 5)$ is valid, as is $GCD(5, 0)$, but $GCD(0, 0)$ is not.

Algorithm Explanation: One way to do GCD would be to start at 1 and keep track of the largest number that divides both values at each level. When we do that, we definitely get the right answer. Another way to think about it is subtracting by the smaller value until the bigger number is less than or equal to the smaller number. For example, say we have 40 and 12. 40 - 12 is 28, 28 - 12 is 16, 16 - 12 is 4, so the answer is 4. This process is very similar to take a modulo, as we essentially are finding the remainder after dividing the value.

This relies on the principle that the GCD of two values will not change if you replace the larger one with the difference of the larger and the smaller one. The intuition behind this is that if my GCD divides x and y, then it must be true that it will divide x−y, because x and y are just integer multiples of the GCD, so x−y is equivalent to some integer multiple of the GCD as well! For example, with 40 and 12, the GCD is 4. Let’s have the GCD be z, let 40=x, and 12=y. We therefore can say x−y=10z−3z=7z, and 7z is of course an integer multiple of the GCD!

If you’re still curious to learn more about Euclid’s algorithm, take a look at its wikipedia page, specifically the “Description” and “Proof of Validity” subsections!

2. Cumulative Sum

Method Header: public static int sumBetween(int a, int b)

Problem Description: The goal is to find the sum of the values from $a$ to $b$. In math, we would write this problem as $\sum_{i=a}^{b} i$. You must also do 2.1 if you choose this question.

Invariants: You can assume that $a \leq b$ for all inputs.

2.1

Method Header: public static int sumTo(int x)

Problem Description: Now, write another method to find the sum of values from 1 to $x$, inclusive. Think about how you can take advantage of prior code to solve this problem. Remember, you must also do 2 if you choose this question.

Invariants: You can assume that $x >= 1$.

3. Find Second Largest

Method Header: public static int findSecondLargest(int[] nums)

Problem Description: Given an array of integers, find the second largest value in the array. We are going to be implementing a helper function for this, with this method header:

private static int findSecondLargestHelper(int largest, int secondLargest, int index, int[] nums)

Note that we use Integer.MIN_VALUE here to pass in a default starting minimum value that will be updated as we find the second largest value.

public static int findSecondLargest(int[] nums) {
    return findSecondLargestHelper(Integer.MIN_VALUE, Integer.MIN_VALUE, 0, nums);
}

Invariants: You may assume that the array is not null and has at least 2 different elements.

Important: If the array is something like [2, 2, 1], you should return 2. The reason for this is as that if we removed the largest element, the new largest element would still be 2.

4. Sum of Digits

Method Header: public static int sumOfDigits(int x)

Problem Description: Write a recursive function to calculate the sum of the digits of number. For example, sumOfDigits(74296) should return 28 as 7 + 4 + 2 + 9 + 6 = 28.

Invariants: You may assume that $x \geq 0$.

5. Count Ways to Climb Stairs

Method Header: public static int countWaysToClimb(int stairs)

Problem Description: Given an amount of stairs to climb, calculate the number of ways to climb taking either 1 or 2 steps at a time. For example, if there are 4 stairs, we would return 5, as there are the following options:

1, 1, 1, 1
1, 1, 2
1, 2, 1
2, 1, 1
2, 2

Hint: Write out by hand the possibilities for small examples. See if you notice a pattern you can take advantage of.

Invariants: You may assume that the stairs >= 0. If stairs is 0, you should return 1.

6. Log

Method Header: public static int log(int base, int n)

Problem Description: A log operation is the inverse of an exponential operation. As a refresher, given some base $b$ and some value $n$, we can calculate $log_{b}n$ by seeing how many times we have to multiply $b$ by itself until we reach $n$. For example, $log_{10}1000 = 3$, and $log_{b}1 = 0$ for all $b$.

Invariants: Although you cannot assume that there exists an exact solution x such that $base^x = n$, you can assume that base <= n for all inputs, that base and n are positive integers greater than 1. That means no natural logs!

If there is no exact integer solution x, you should return the truncated answer - that is, if we are given log(2, 33), we should return 5, not 6. This is not as complicated as it sounds, and if you write out what the recursion would look like by hand, you’ll see why.

7. CountSubstrings

Method Header: public static int countSubstrings(String sequence, String word)

Problem Description: We want to find how many times a sequence appears in a particular word. For example, in the word “banana”, the sequence “na” appears two times, with “baNAna” and “banaNA”. We also have “ana” appear two times, being “bANAna” and “banANA” - note that this means that we can have overlaps between the starts of our sequences (this actually makes the problem easier!)

Invariants: You may assume that neither sequence nor word are null, and that both have positive lengths (0 is not positive). You may also assume that the strings are both all lowercase.

Hint: The function String.substring(x, y) will be helpful here.

//Example:
String className = "cis110";
String department = className.substring(0, 3);
String number = className.substring(3, className.length());
System.out.println(department); // prints "cis"
System.out.println(number); // prints "110"

Extra Credit

How Different?

Method Header: public static int howDifferent(String one, String two)

Problem Description: This is the most interesting problem of what we’ve seen so far. Given two strings, we want to find out what the least amount of changes we would have to make to one of the strings to get to the other. There are three ways we can change a string. 1, we can replace a letter with another letter. 2, we can delete a letter. 3, we can add a letter. Here are some examples to help make this clear.

Example 1: code, coder. We can add one letter to the first string, being an r, to make the strings match, so this should return 1.

Example 2: mouse, must. We see that both share the same first letter, so we don’t have to make any changes there. Then, we can delete the o in mouse, then, the next letter is s for both strings, and then we can change the e into a t to make both into must. That’s a total of 2 changes. There are other ways we could have transformed the first string into the second, but this is the one with the least changes, and that’s what we’re interested in.

Part Two: Finger Exercises Tests

For each of the 5 functions you completed in the previous section, you will write one test case to test your code. These test cases should be written in FingerExercisesStudentTests.java.

Motivation

JUnit is an industry-grade framework used by companies like Amazon and Google to test their Java code. JUnit is valuable because it lets us maintain enormous test suites that can run automatically and let us know if changes to our code breaks any of our functionality - this becomes super crucial as the projects you’ll be making in your CIS career will grow in size and complexity.

JUnit Reminders

As a review, JUnit works by comparing expected output to actual output on your functions and object state. Here’s an example:

public class ExampleTest {

    @Test
    public void testSumFunction() {
        assertEquals(11, Example.sum(5, 6));
    }

}

We can also test to make sure an exception is thrown properly. Using the same setup as above:

   @Test(expected = IllegalArgumentException.class)
    public void testException() {
        SomeClass.readNonnullFile(null);
    }

You’ll find the following functions from the JUnit library useful:

assertTrue(someConditon);
assertFalse(someCondition);
assertEquals(expectedValue, actualValue);
assertEquals(expectedDouble, actualDouble, deltaValue);
assertArrayEquals(expectedArray, actualArray);

Note that you can put multiple assert statements in one test. With multiple assert statements in a test, if a single one of them fail, the whole test will fail. However for this homework, the use of multiple assert statements is not expected nor needed. Multiple asserts will be useful in future homeworks.

Testing

To start, open FingerExercisesTests.java and take a look at the test cases that have already been given to you. The test cases that you write yourself must be different than the given cases - credit will not be given to a repeated case.

Write your test cases in FingerExercisesStudentTests.java. You are only required to write one new test per function, but we encourage you to write as many tests as you need to feel confident that your code works. Once you’ve written these, run them following the instructions given above and make sure they pass. We recommend testing your functions with multiple edge cases and varied input arguments to ensure that your code works for all possible scenarios.

Running JUnit on Codio

In order to run JUnit tests, go to Tools -> JUnit and click the blue “Execute All” button. After you’ve run them once, you can also click the blue “Re-execute” button. Each test will either say passed or failed - passed means your test worked, and failed means it does not. You can click on a failed test to see more information about the failure. Make sure to run the given tests from FingerExercisesTests.java as you go through the Finger Exercises. To do this, comment out the tests that you haven’t implemented yet - you should see comments inside FingerExercisesTests.java labelling the different sections to make this easier.

Part Three: Sierpinski

In this assignment, you will write a program Sierpinski.java that recursively draws a Sierpinski carpet using PennDraw. These instructions will walk you through the process step by step. You are not allowed to use PennDraw.setXScale(), PennDraw.setYScale(), or any scale changing in this assignment. Doing so will only make the assignment harder.

A. Setting up the recursive structure of `sierpinski()`

Write a function sierpinski() that takes two parameters, numLevels and halfSideLength. Your function should print both parameters, and then recursively call itself eight times with the arguments numLevels - 1 and halfSideLength / 3. The recursion should stop when numLevels is less than 1. Later, you will replace the print statement with a call to PennDraw.filledSquare().

Write a main() function that interprets its first command-line argument as numLevels. Have it call sierpinski(numLevels, 1.0 / 6.0). You may assume that your program will be run with exactly one command-line argument that is a positive integer.

Hint: Think about how many recursive calls you need to make.

B. Checkpoint

Running your program with the following command-line arguments should produce the following output:

java Sierpinski 0
(no output)

java Sierpinski 1
1 0.16666666666666666

java Sierpinski 2
0.16666666666666666
0.05555555555555555
0.05555555555555555
0.05555555555555555
0.05555555555555555
0.05555555555555555
0.05555555555555555
0.05555555555555555
0.05555555555555555

java Sierpinski 3
0.16666666666666666
0.05555555555555555
0.018518518518518517
0.018518518518518517
0.018518518518518517
0.018518518518518517
0.018518518518518517
0.018518518518518517
0.018518518518518517
0.018518518518518517
0.05555555555555555
0.018518518518518517
0.018518518518518517
0.018518518518518517
0.018518518518518517
0.018518518518518517
0.018518518518518517
0.018518518518518517
0.018518518518518517
0.05555555555555555
0.018518518518518517
0.018518518518518517
0.018518518518518517
0.018518518518518517
0.018518518518518517
0.018518518518518517
0.018518518518518517
0.018518518518518517
0.05555555555555555
0.018518518518518517
0.018518518518518517
0.018518518518518517
0.018518518518518517
0.018518518518518517
0.018518518518518517
0.018518518518518517
0.018518518518518517
0.05555555555555555
0.018518518518518517
0.018518518518518517
0.018518518518518517
0.018518518518518517
0.018518518518518517
0.018518518518518517
0.018518518518518517
0.018518518518518517
0.05555555555555555
0.018518518518518517
0.018518518518518517
0.018518518518518517
0.018518518518518517
0.018518518518518517
0.018518518518518517
0.018518518518518517
0.018518518518518517
0.05555555555555555
0.018518518518518517
0.018518518518518517
0.018518518518518517
0.018518518518518517
0.018518518518518517
0.018518518518518517
0.018518518518518517
0.018518518518518517
0.05555555555555555
0.018518518518518517
0.018518518518518517
0.018518518518518517
0.018518518518518517
0.018518518518518517
0.018518518518518517
0.018518518518518517
0.018518518518518517

C. Drawing the Sierpinski carpet in `sierpinski()`

Comment out the print statement in sierpinski(). Modify sierpinski() to take two additional arguments, x and y. Remember that if you have more than 85 characters on a single line, you need to break the line up. This can be done by putting a linebreak between arguments.

Now, we will actually draw the Sierpinski carpet. A Sierpinski carpet of order numLevels comprises of a solid square of half-length halfSideLength centered at (x, y) that is surrounded by eight smaller Sierpinski carpets, defined recursively.

Each smaller carpet should be of order numLevels - 1 and be one third the size of the original. They should be positioned to the left, right, top, and bottom of the center square, as well as top left, top right, bottom left, and bottom right. The distance between the center of the original square and the center of the smaller squares should be 2 * halfSideLength of the original in both the $x$ and $y$ directions.

Take a look at the examples in the next section to help you visualize what should be drawn.

You have already set up the structure of the function in the previous step. You just need to draw a square with the appropriate call to PennDraw.filledSquare() instead of printing, and to modify the recursive calls to take the correct inputs.

Finally, modify main so that it calls sierpinski with initial values of 0.5 for x and y.

Warning: Do not call PennDraw.setCanvasSize(), or PennDraw.save(). You will receive a large point deduction.

D. Checkpoint

Running your program with the command-line arguments below should produce the following output.

Input: java Sierpinski 1

Input: java Sierpinski 2

Input: java Sierpinski 3

Input: java Sierpinski 4

Input: java Sierpinski 5

Input: java Sierpinski 6

E. Optional: Animating

Once you have your Sierpinski carpet working, add calls to PennDraw.enableAnimation() and PennDraw.advance() into your sierpinski() function. (You are not required to animate your Sierpinski carpet, and it is not worth any points, but it is fun and will help you visualize the recursion. If you do add animation, leave it in your code: it will not affect our grading.) Experiment with different arrangements of the recursive calls to sierpinski().

Submissions

Please complete the readme and then submit FingerExercises.java, FingerExercisesStudentTests.java, Sierpinski.java, and recursive_readme.txt on Gradescope.

Note that we will only run tests for the first 5 finger exercises you completed - the rest will automatically fail. If your grade is a 20, that means you’ve passed all the tests that you should have. The Sierpinski.java file will be graded manually.

Part One: Recursive Exercises

Motivation

Applications to Other Fields

Goals

Setting Up

Finger Exercises

1. Greatest Common Denominator (GCD)

2. Cumulative Sum

2.1

3. Find Second Largest

4. Sum of Digits

5. Count Ways to Climb Stairs

6. Log

7. CountSubstrings

Extra Credit

How Different?

Part Two: Finger Exercises Tests

Motivation

JUnit Reminders

Testing

Running JUnit on Codio

Part Three: Sierpinski

A. Setting up the recursive structure of sierpinski()

B. Checkpoint

C. Drawing the Sierpinski carpet in sierpinski()

D. Checkpoint

Input: java Sierpinski 1

Input: java Sierpinski 2

Input: java Sierpinski 3

Input: java Sierpinski 4

Input: java Sierpinski 5

Input: java Sierpinski 6

E. Optional: Animating

Submissions

A. Setting up the recursive structure of `sierpinski()`

C. Drawing the Sierpinski carpet in `sierpinski()`