CS 200
P1: Implementing Recursion using an explicit Run Time Stack
Overview
The object of this assignment is to implement recursion using an
explicit Run Time Stack. Copy the following code into an Eclipse
project:
StackIF.java, StackException.java and Frame.java are given.
Don’t change them. Only work on Hanoi.java.
Hanoi.java
The recursive solution to the Hanoi problem, recHanoi(), is given.
Don’t change it. You need to work on the iterative,
explicit stack based solution. Start implementing the getCount() and
initRTS() methods and the methods implementing the stack operations:
push(), pop(), and isEmpty(), as specified in StackIF.java.
Now you are ready to implement rtsHanoi using a Run Time Stack rts.
Study lecture 2: 02-stacks slides 18 to 27.
Initially, there is one Frame [state,n,from,to] on rts.
Keep popping frames until rts empty. When popping a frame:
- if n == 0 do nothing (stack frame has already been popped)
- else if frame in state 0:
Go into state 1 by pushing [1,n,from,to]
and call hanoi(n-1,from,via) by pushing [0,n-1,from,via]
- else if in state 1
Print disk n move (see recHanoi)
and go into state 2 by pushing [2,n,from,to]
and call hanoi(n-1,via,to) by pushing [0,n-1,via,to]
- else (in state 2) do nothing (stack frame has already been popped)
Testing and submitting your code
-
resDB2 contains the result for
input 2 in debug mode.
-
resDB3 contains the result for
input 3 in debug mode.
Use the Checkin webserver to exercise and submit your code.
Submit your Hanoi.java file.