EX02 – Recursion!

0. Complete the Prerequisites

Before continuing on, make sure you’re caught up on the lectures through 5/17. Also, make sure you’ve completed the Java Warm-up, or EX01

1. Download New Course Material

“Pulling” course materials down from Upstream. As new lesson material or starter code for exercises is added to our central course repository, these are the steps you’ll take to download them into your own workspace repository.

1. Open the Git menu from along the top and select Pull
   • This should open a pop-up that is auto-populated with the correct options. The correct command is git pull origin main. We are pulling code from the course source repo into our local repo.
2. This downloads the latest course materials! It will succeed silently, so if nothing appears to happen it worked (and any new files will be available in the file explorer). If there was an error, you would see an error message pop up.

You should see in your exercises src folder an ex02 package with a Recursion class. This exercise involves writing three recursive methods. All the methods you write as part of this exercise will be static, or class, methods. This means that we do not need an instance of the Recursion class to invoke them, and can think of them as “globally” available to us.

2. Goodbye 110, hello 210

The first recursive method you will write will perform some recursive String manipulation to upgrade every occurrence of "110" in a String to "210". It returns a String and takes in a single String. Some example usages below.

upgrade("lol110lol") --> "lol210lol"
upgrade("1110110") --> "1210210"
upgrade("10101010") --> "10101010"
upgrade("") --> ""

3. Twins once removed

The second task is to write a method that recursively counts identical chars in String that are separated by another char. We are looking for pairs of matching chars within a String. So, the String "kaki" would have one pair – the two k’s. They are separated by the 'a' char. The String "aBaBa" has 3 total pairs. 2 pairs between 'a' chars and one pair of 'B's. Some example usages:

pairCount("kaki") --> 1
pairCount("10101010") --> 6
pairCount("zomg!1!1!") --> 3
pairCount("") --> 0

Pairs can also overlap, so we would expect the following:

pairCount("eeeee") --> 3

4. To sum or not to sum

The final recursive method involves recursively determining if any group of elements in array can be summed to some target, given some starting index. Some example usages:

sumToTarget(new int[]{8, 9, 5}, 0, 22) --> true
sumToTarget(new int[]{8, 9, 5}, 2, 22) --> false
sumToTarget(new int[]{8, 9, 5}, 0, 17) --> true
sumToTarget(new int[]{8, 9, 5}, 0, 18) --> false
sumToTarget(new int[]{8, 9, 5}, 0, 14) --> true
sumToTarget(new int[]{8, 9, 5}, 0, 13) --> true
sumToTarget(new int[]{8, 9, 5}, 1, 14) --> true
sumToTarget(new int[]{8, 9, 5}, 1, 13) --> false
sumToTarget(new int[]{}, 0, 0) --> true

Hints and Notes:

• All of these problems could be solved without recursion, however, any solution that is not recursive will not receive credit.

• You will probably want to make use of some of the String methods we’ve been looking at in class, like charAt and substring.

5. Make a Backup Checkpoint “Commit”

“Push” your work up to GitHub for backup. By creating “commits”, which you can think of as versioned checkpoints in your workspace, you are not at risk of losing your work. It’s easy to revert back to an old version or to restore your entire workspace on a different computer.

1. Select the Git menu along the top of your screen and then choose “Commit”.
2. Notice the files listed under Changes. These are files you’ve made modifications to since your last backup.
3. Ensure all the files that you’d like to backup are selected. Your cursor should be inside of a message box where you will write a nice description of the modifications you’ve made to your code, like “Finished EX02!”, and then hit the “Commit” button.
   • If you do not want to backup all changed files, you can select them individually. For this course you’re encouraged to back everything up.
   • IntelliJ might tell you there are some warnings or errors here, and you should just commit anyway!
4. If you open the Git at the bottom of your screen, you should see this commit added to your chain of git commits. However, it has just been added to your local main branch, and needs to be pushed to your remote backup.
5. Select the Git menu along the top of your screen again and then choose “Push”.
6. A pop-up should appear that displays: “main -> backup : main”, which means your latest local commit on the local main branch is going to be pushed to the main branch on the remote backup. If you see “main -> origin : main”, just click where it says origin and select backup. Hit the “Push” button.
7. If you want to see your backed up work on Github, navigate to the following URL but replace USERNAME with your GitHub username:
   • https://github.com/comp210-ss1-24/summer210-workspace-USERNAME
   • You can also verify it was pushed successfully by opening the Git view along the bottom of your screen and verifying the latest commit appears on the local and remote branches. (The text next to the tag icons should say backup & main, next to the latest commit message)

6. Submit to Gradescope for Grading

All that’s left now is to hand-in your work on Gradescope for grading!

Before doing so, you need to know that before an assignment’s deadline you can resubmit work as many times as you need to without penalty. Portions of assignments are autograded and will provide near-immediate feedback. We want you to resubmit as many times as it takes you in order to earn full autograding credit!

Login to Gradescope and select the assignment named “EX02 - Recursion” You’ll see an area to upload a zip file. To produce a zip file for autograding, return back to IntelliJ.

Mac Users

Along the bottom of your window, you should see an option to open a terminal integrated into IntelliJ.

Type the following command (all on a single line):

./submit.sh ex02

In the file explorer pane, look to find the zip file named “ex02_submission.zip”. If you right click on this file “Open in -> Finder” on Mac, the zip file’s location on your computer will open. Upload this file to Gradescope to submit your work for this exercise.

Windows Users

We are working on rewriting the script to work for Windows! Until then, please navigate to your course workspace in a File Explorer window. Then right click on the src folder in your exercises directory and compress the directory into a zip folder. You can name it “ex02_submission.zip”

When you upload it to Gradescope, please delete any files that showed up in the src/ folder that were not actually part of ex02.

Autograding will take a few moments to complete. For this exercise there will be no “human graded” component, but in future exercises and projects there will. Thus, you should expect to score 100 out of 100 possible points on this assignment. If there are issues reported, you are encouraged to try and resolve them and resubmit. If for any reason you aren’t receiving full credit and aren’t sure what to try next, come give us a visit in office hours!