» CS 245 Lab 4 – Recursion

CS 245 Lab 4 – Recursion

September 25, 2013 by Chris Johnson. Filed under cs245, fall 2013, labs.

First, if you have checkpoints left over from last lab, get them inspected during the first 15 minutes of this lab.

Don’t forget to work in pairs! Where possible, please work with someone that you did not work with last week. The exchange of new ideas and perspectives is not an opportunity you want to rob yourself of.

Synopsis

In this lab, you will have methods call themselves. Recursion can simplify the solving of many kinds of problems that can be broken up into identical subproblems. You’ll work on two such problems in this lab.

When designing a recursive solution you need to think about two things:

The trivial cases. When is the problem so easy that I immediately can compute the answer? Perhaps you’ve got an empty String or list. Perhaps you’ve reached 0. Maybe you’ve gone past some threshold. In any case, the trivial solution is easy to solve. You may just need to return a fixed value. You may do nothing.
The general cases. When is the problem so complex that I feel like I need a loop or a sequence of redundant code to solve it? Here we tackle just one piece of the problem but make one or more recursive calls to solve the remainder.

The general pattern of a recursive method is this:

methodToSolveProblem(problem) {
  if problem is trivial to solve
    solve it
  else
    identify the self-similarity in the problem
    compute first self-similar step
    call methodToSolveProblem(problemRemainder)
}

Checkpoint 1

Let person A type.

Augment one of your file filter methods from last lab to recursively operate on a file’s subdirectories. The File class has a method that tells you if a given file is a directory. If so, call your method on it.

Checkpoint 2

Let person B type.

Tournament brackets are self-similar structures. As such, they can be drawn recursively:

to draw bracket:
  draw fill-in-the-blank line for winner
  if there were previous rounds
    draw diagonal arm to child bracket
    draw upper child bracket
    draw diagonal arm to lower bracket
    draw lower child bracket

Here’s one possible output:

A recursively drawn tournament bracket.

Reusing the custom JPanel drawing ideas we saw in lecture, create a JPanel that draws a bracket recursively. Keep the following points in mind:

Draw a bracket that goes from winner on the left to all contenders on the right—it gets taller as we go right. Draw it on paper to get a feel for the self-similarity.
When designing recursive solutions, you focus only on the current level of the problem. If you need to communicate information to the subproblems, you do so through parameters to the recursive calls. Since you need to be able to add parameters, you usually will need to write your own method. An overridden method like paintComponent doesn’t let you add parameters.
Your recursion must stop at some point.