CS2 Lesson 18: Recursion (Again)

1. Project 3 Hints
2. Towers of Hanoi
   1. Algorithm
   2. Exercise
3. Homework

Project 3 Hints

• Implement the smaller pieces first: Die (with a roll method), Bid (the face value and number of dice), Player interface, HumanPlayer, RandomPlayer
• Make sure they all work on their own: write a short Main method that instantiates those objects and tests things out.
• Then try to put things together. See the slides from last time.
  • Get a bid from Player one.
  • Keep track of which player’s turn it is (use a variable to keep track of the current player; currently it’s player 2’s turn).
  • As long as the current player doesn’t call liar:
    • Ask the player for raise.
    • Output that.
    • Switch whose turn it is.
  • After someone calls liar:
    • Both players reveal their dice.
    • Count the number of dice with the particular face value that was bid on.
    • Determine who won: if there are at least as many dice with the face value that the bidder said, then the bidder wins. Otherwise, the challenger wins.
    • Might need object-oriented strategies to ensure that we can output the correct winner.

Towers of Hanoi

Towers of Hanoi is a game played with 3 pegs and $n$ disks (for some integer $n > 0$). The rules are:

• The goal is to move all the disks from one peg to another.
• No bigger disk can be placed on top of a smaller disk.

Click this link to play the game. Play the game with 3 disks. See if you can win in the minimum number of moves. Then play again with 4 disks. See if you can figure out the pattern and find a solution for the puzzle.

1. Come up with a recursive algorithm to solve this game.
2. How did they figure out the minimum number of moves needed? Does your algorithm end up giving that minimum?

Algorithm

Hopefully you got a chance to play around with that and you were able to figure out the algorithm. The real issue is that we need to move all the top $n - 1$ disks before we can move that last one. So how do we figure out how to do that? Recursion!

1. Base case: if $n = 0$, there is nothing to do!
2. Recursively move the first $n - 1$ disks from peg $1$ to peg $3$.
3. Move the bottom disk from peg $1$ to peg $2$.
4. Recursively (again) move the $n - 1$ disks from peg $3$ to peg $2$.

That means that to solve the problem for $n$ disks, you have to solve the problem for $n - 1$ disks twice, and add one extra step (to move that bottom disk). So if $S(n)$ is a function representing the number of steps in the solution for $n$ disks, then $S(n) = 2S(n - 1) + 1$.

Notice: if $S(0) = 0$, what is $S(1)$? $S(2)$? $S(3)$? $S(4)$? Do you see the pattern? (Think in terms of powers of 2!) Record your answer on BrightSpace!

Exercise

I partially implemented a “solver” for this game in the TowersOfHanoi class. Fill in the gaps in the solve method. You can use the moveDisk method which I implemented for you, but remember that there are recursive steps here. That means: you will need to call solve from within itself (recursively)!

If you make a mistake, and move a “large” disk onto a smaller one, the code will crash with an exception. So be careful! We will review the solution next time.

Homework

On BrightSpace, you will need to answer the question asked earlier in the lesson: come up with a formula (in terms of $n$) for the number of steps it takes to solve the Towers of Hanoi problem for $n$ disks. Notice that:

• $S(0) = 0$
• $S(1) = 1$
• $S(2) = 2 \times 1 + 1 = 3$
• $S(3) = 2 \times 3 + 1 = 7$

What’s the pattern?