Assignment : More Recursive Puzzles

Assignment Setup

To create your repository go here. Then follow the same accept/import process described in Assignment 0.

More Recursive Puzzles

In this assignment you’ll be tasked with writing a few recursive methods. These recursive methods will rely on the concepts covered in the prep work and studio including:

  • Identifying the base case and recursive substructure of a problem
  • Tracing recursive execution
  • Comparing recursion with iteration
  • Using helper methods with recursion
  • Using recursion to divide and conquer

Some of the tasks below require you to sketch some things out using paper and pencil. Be sure to take note of these parts of the assignment, as you will be asked to show your work when you are ready to demo.

All of the methods that you are asked to complete can be found in the RecursiveMethods.java file. If you add any additional methods to this file, you are expected to add appropriate JavaDoc comments to these methods.

Since this lab is meant to reinforce the concepts relating to recursion, no loops are allowed for any reason. If you use a loop to solve a particular problem you will not receive any credit for that problem.

Dragon Curves

Dragon curves are a type of Fractal created by drawing lines in a particular pattern. These lines can be specified using a string with the following characters:

  • F or H represents forward motion in the current direction
  • + represents a 90 degree counter-clockwise turn
  • - represents a 90 degree clockwise turn

For example, the simplest dragon curve that can be represented is F-H which looks like this:

Further dragon curves can be generated by using the following rules:

  • Replace all F characters with F-H
  • Replace all H characters with F+H

If the F-H dragon curve above represents dragon(0) then further dragon curves would look like:

dragon(0) = F-H
dragon(1) = F-H-F+H
dragon(2) = F-H-F+H-F-H+F+H
dragon(3) = F-H-F+H-F-H+F+H-F-H-F+H+F-H+F+H

If we keep performing these substitutions then we’ll be able to generate more intricate dragon curves, like the one for dragon(3):

And this curve for dragon(10):

Your task is to create a recursive method dragon(int n) that generates dragon curves using the rules outlined above and returns the corresponding string.

Tips for completing this method

  • You will likely want to make use of some String methods to help you with the substitutions. We would suggest using the String.replaceAll() method.
    • An Example: "This is a String".replaceAll("is", "IS") would result in "ThIS IS a String". This example shows a String literal (the "This is a String"), but a String variable clould have been used instead.
  • Be careful with how you perform the substitutions. The substitution for F will introduce more H characters into the string, but we only want to perform a substitution on the original H characters, not these new ones.
  • Unit tests have been provided to you in the DragonTests.java file. Use them to check your work.
  • You do not need a helper method for this part (and should not use one).

Submitting this method

When you submit this problem you will be asked the following:

  • Do the provided DragonTests pass?
  • Can you identify the base case(s) in your code?
  • Can you identify the recursive step(s) in your code?

Exponents

Your next task is to complete a method exponent(int base, int exp) that recursively computes . Your code should work for positive and negative bases as well as positive and negative exponents (Hint: You may want to review the relationship between positive and negative exponents. Khan Academy has a great Negative exponents review). Unit tests have been provided in the ExponentsTests.java file that can be used to check your work.

Once you have completed your method, you should sketch out the execution of exponent(3, 4). Show every method call that is made and be sure to include every step that is involved in computing the final result. More detail is better!

Tips for completing this method

  • A helper method isn’t strictly required, but it may help you here.
  • Usage of Math.pow() or any other method to compute exponents besides recursion is not allowed for this problem.

Submitting this method

When you submit this method you will be asked the following:

  • Do the provided ExponentTests pass?
  • Did you create JavaDoc for your helper method (if you used one)?
  • Can you identify the base case(s) in your code?
  • Can you identify the recursive step(s) in your code?
  • Show and explain your work for the execution of exponent(3, 4)

Array Sum

Complete the method arraySum(int[] array) such that it computes and returns the sum of the given array. Unit tests have been provided in the ArraySumTests.java file that can be used to check your work.

Once you have completed your method, you should sketch out the execution of arraySum using the array [1, 3, 9, 7]. Show every method call that is made and be sure to include every step that is involved in computing the final result. More detail is better!

Tips for this method

  • This is not the first time you have seen this method, as arraySum was also part of Studio 5 . It is likely that you used iteration during the studio, however your iterative solution may still help you figure out the recursive solution. Note that the unit tests provided to you here are the same as the ones provided to you in studio: the functionality of the two methods should be exactly the same.
  • You should not need to create any arrays to solve this problem
  • You will probably want a helper method. Think about what additional information the helper method should track.

Submitting this method

When you submit this method you will be asked the following:

  • Do the provided ArraySumTests pass?
  • Can you identify the base case(s) in your code?
  • Can you identify the recursive step(s) in your code?
  • Can you explain why the helper method is necessary?
  • Did you provide JavaDoc comments for your helper method?
  • Show and explain your work for the execution of arraySum with the array [1, 3, 9, 7].

Max Path Length

As a break from studying you decide to go for a hike in the park. You are provided a map for the park in the form of the following 2D array:

The starting point of the path is in the top left corner of the map. Think of the map as an array, with a start at row 0 and column 0. The 1’s indicate paths that can be taken through the park while the 0’s indicate off trail areas that you are not allowed to visit.

You’re in no hurry to get back to your homework, so you decide that you want to take the longest possible path that you can find. Looking at the map you notice that the path is linear until a fork is reached at the circled location:

At this point you have a decision to make. There are two paths you could take:

It is fairly straightforward to determine which path is the longest by adding up the lengths of the two options:

  • Option #1: Red path (5) + blue path (2) = 7
  • Option #2: Red path (5) + green path (5) = 10

The green branch is the one that you should select in this situation as it leads to the longest possible path length of 10.

Complete the maxPathLength(int[][] paths) method such that it computes and returns the longest path length that exists in the given array. For the sake of this problem you can assume the following:

  • You will always start in the top left corner of the array (position (0, 0))
  • You are only expected to travel in the four cardinal directions (north, south, east, west). You cannot move diagonally.
  • There is no limit on the number of branches that may exist
  • The paths will never be circular, they will always have a clearly defined end. In other words, a path will never lead you to a place that you have already visited.

Unit tests have been provided in the MaxPathLengthTests.java file that can be used to check your work.

Tips for this method

  • You’ll probably want a helper method. Consider what extra parameters could be added to the helper method that will make the recursion easier.
  • You’ll likely want some way to mark that you’ve already visited a spot on the map. Feel free to change the values in the array for this purpose.
  • The base case here is a bit more complex than what we have seen before. Take some time to think about what conditions make up the base case before you begin.
  • This is an example of a divide and conquer algorithm, which means there will be multiple recursive calls in your method
  • Though this method is conceptually difficult, it does not require a large amount of code to complete. It is possible to complete this method in fewer than 20 lines of code.

Submitting this method

When you submit this method you will be asked the following:

  • Do the provided MaxPathLengthTests pass?
  • Can you identify the base case(s) in your code?
  • Can you identify the recursive step(s) in your code?
  • Did you create JavaDoc for your helper method?

Submitting your work

To submit your work come to office hours or class on an “Assignment day” and sign up for a demo via 131list.com. Be prepared to show them the work that you have done and answer their questions about it!