teaching machines

CS 245 Lab 4 – Recursion

September 25, 2013 by . 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 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: