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 \(base^{exp}\). 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 walk in a very special park. This park has dangers, but you are provided a map for the park in the form of a 2D array, such as the following:

The map is represented as an array. Each 1 indicates a stepping stone in the park on which you can safely step without adverse consequences. On the other hand, each 0 can be thought of as a shaft of infinite depth, so that if step on it, you fall forever and never make it back.

The park has only one entrance, labeled as Start in the above picture, and it forces you to begin your walk using the top left cell of the map.

In the beloved movie Indiana Jones and the Last Crusade, the titular character must navigate such stepping stones to makes his way to the Holy Grail. A misstep (from which he recovers) as well as his eventual success is shown here. In the above array, you can step safely on any 1 but stepping on any 0 will lead to a most unpleasant demise. Unlike Indiana, you will fall forever.

In spite of the dangers presented by this unusual park, you wish to take a stroll, beginning with the top left cell of the map (which is safe only if it contains a 1), and continuing inside the park using only safe cells. Indiana Jones had two prior movies, and so lots of experience, so that he could reasonably be asked to jump some distance over cells to find a safe path.

Your task is easier:

  • You can move from one cell to another only using cardinal directions, namely up, down, left, or right. You are not allowed to move diagonally.
  • You can only move one cell at a time: no skipping or jumping over cells!
  • You must step only on safe (marked with 1) cells.
  • Each interior cell can be bordered on each of its four cardinal sides by another safe cell. Thus there can be many paths one could take from the starting cell.
  • The safe cells of the map form no cycles. While the park can contain many paths, none of them would cause you to revisit a cell you have already used on your journey.
  • You will find a path through the park using the rules above, and then make your way back to the entrance retracing your steps. We are not concerned here with your return to the starting cell, only with the path you take until you have to turn back.
  • You will get hungry and thirsty along the way, and who knows which path you might take? We are thus concerned here with the longest possible path you might take, so that you can take the right amount of food and water for your journey.

How do we find the longest path in such a map? Let’s continue with our example.

Looking at the map you notice that the path is unique 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:

Visually, in this example, 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.

While visually it seems simple to compute the longest path, it is worth looking at this example again with recursion in mind. Remember our task in finding a recursive solution is to discover the substructure of a problem.

Consider finding the longest path but starting arbitrarily from the circled cell below. As depicted, we arrived at the circled cell from the cell above it.

Let’s assume we have four messengers named by the direction they would pursue from the circled cell. So let’s call the four messengers up, down, left, and right. Each messenger will look into going its assigned direction, and report back the longest path found recursively from the appropriate neighboring cell. Let’s see how these messengers work in this example:

  • The left messenger sees that it starts on a 0 cell, which is not safe, and so it immediately returns 0 as the longest path from that cell.
  • The right messenger eventually returns 3 as the longest path it finds. It does this using more recursion, but we count on recursion to do the right thing no matter where we start, so we count on the right messenger returning the correct answer of 3.
  • The down messenger returns 1 as the longest path from its starting point.
  • The up messenger must not be dispatched in this example! It would consider the cell from which we arrived at the circled cell, and that’s not allowed: there are no cycles in the graph. We can avoid calling the up messenger in one of two ways:
    • We can be told we arrived at the circled cell from above, and thus know not to send the up messenger.
    • Before dispatching its four messengers, the cell above the circled cell can temporarily change its contents to 0 so that the up messenger from the circled cell will surely return 0 as the longest path from itself. Recall that’s what happened to the left messenger because it started with a 0 present in the map initially. Any cell that temporarily changes its contents in this way must restore the 1 after its messengers return, prior to returning from its call.

In any case the up messenger in this example must report 0 as its longest path.

How does the circled cell compute the longest path from itself? It can take the information returned by the messengers, namely the longest path from each of those neighboring cells. The longest path from the circled cell is simply the max of the values returned by the messengers, plus 1 for the circled cell itself. In our example, this would be max(left,right,down,up)=max(0,3,1,0)=3+1=4. That value is returned by any call to the circled cell as the maximum path starting at the circled cell.

The substructure for this problem is that the solution at the circled cell is 1 more than the max of the values returned by up, down, left, and right. Each of the four messengers is attacking a slightly smaller problem than the problem found at the circled cell.

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.
  • The map can be arbitrarily large in either dimension.
  • 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.
  • Except for avoiding circular paths, branching within the map can be arbitrarily complex.

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. In the example above, this involved temporarily changing a cell’s contents from 1 to 0 but back again at some point.
  • Take some time to think about what conditions make up the base case before you begin. Recall that a base case is a condition under which a method does not call itself recursively. It may be helpful to view cells outside of the defined map as if they contained a 0.
  • 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. It is worthwhile thinking through how to solve this problem before coding!

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!