Computer Science 2311
Fall 2009
Programming Assignment 5

About the assignment

This is an exercise in recursion. There are three parts. Write and test each part, and turn them all in.

Part 1

Write a function factorial(n) that returns 1*2*3*...*n. Start by writing a contract that tells what it returns. Then write the function definition using recursion. Do not use a loop. Use the following facts.

  factorial(0) = 1
  factorial(n) = n*factorial(n-1)   if n > 0

  public static long factorial(long n)

Now write a main method that reads an integer n and writes a table of the factorials up to n. For example, if it reads 6, it would show

   0        1
   1        1
   2        2
   3        6
   4        24
   5        120
   6        720

Test your program.

Part 2.

You computed greatest common divisors in lab 2. Say that gcd(m, n) is the greatest common divisor of m and n. Here are some facts about gcd.

  gcd(0, n) = n
  gcd(m, n) = gcd(n mod m, m)  when m > 0

  public static long gcd(long m, long n)

Now write a main method that reads two numbers and shows their gcd. For example, if it reads 36 and 10, it would say

  The greatest common divisor of 36 and 10 is 2.

Test your program.

Part 3

This part has you solve a puzzle.

A puzzle

The Towers of Hanoi puzzle has three posts and some number n of disks. Each disk has a hole in the middle, so that it can be put on a post, and the disks are of different sizes.

Initially, the disks are all stacked on the leftmost post, with larger disks closer to the bottom and smaller disks closer to the top. For example, if there are three disks, the puzzle starts out looking like this.

The object is move all of the disks from the leftmost post to the rightmost post. So when the puzzle is solved, it looks like this.

But there are some rules that must be followed.

1. Only one disk can be held in your hand at a time. The other disks must be on posts.

2. A disk can only be put down by placing it on one of the posts. For example, you can't put a disk on the table beside the puzzle.

3. No disk can ever be put on top of a smaller disk. You can only put a disk on top of one that is larger than it.

It is convenient to refer to the posts by names, such as L, M and R, for left, middle and right. Instructions to move three disks from L to R are as follows.

  Move a disk from L to R.
  Move a disk from L to M.
  Move a disk from R to M.
  Move a disk from L to R.
  Move a disk from M to L.
  Move a disk from M to R.
  Move a disk from L to R.

The program

Write a method with the following contract and heading.

//========================================================
// hanoi(n, start, end, extra) prints instructions to move
// n disks from post start to post end, using post
// extra for storage.  For example, hanoi(2,'L','R','M')
// writes
//   Move a disk from post L to post M.
//   Move a disk from post L to post R.
//   Move a disk from post M to post R.
//========================================================

public static void hanoi(int n, char start, char end, char extra)

Use recursion. Here are some ideas for that.

1. If n = 0 then you are asked to write instructions to move no disks. Just do not write anything at all.

2. If n > 0, then break the problem down into the following steps.

   1. Ask somebody else to move n-1 disks from start to extra, using end for storage. That stores the top n-1 disks out of the way, on the extra post, exposing the n-th disk on the start post.
   2. Write one line saying to move a disk (the n-th one) from start to end.
   3. Finally, ask somebody else to move n-1 disks from extra to end, using start as storage. That moves those disks from storage to the end, where they are now on top of the n-th disk.

Now complete the program by writing a main method that reads a number n from the user and writes instructions to move n disks from L to R using post M as storage.

Try your program. Does it work? Did the instructions actually do the job?

Turn in all three programs. Make sure your name is on each one.