CIS 223
Assignment Number 6-S97

Trace of Towers of Hanoi Recursion

Reading: Carrano, Chapters 2 and 5. Anthology, Sec. 9.

Programming: This assignment is to be written out by hand.

Let n be the height of a tower to be moved from one tower to another and consider the Towers of Hanoi algorithm written as follows: 

void move_tower (n, from_tower, to_tower, aux_tower) 
	{    
	    if (n > 0) { 
		move_tower (n-1, from_tower, aux_tower, to_tower); 
		move_one_disk (from_tower, to_tower); 
		move_tower (n-1, aux_tower, to_tower, from_tower); 
	   } 
	}
If n = 3, the from_tower is t1, and the to_tower is t3, the initial steps of a trace of this function might read as follows: 
	move_tower (3, t1, t3, t2)
 
	   1. move_tower (2, t1, t2, t3) 
	   2. move_one_disk (t1, t3) 
	   3. move_tower (2, t2, t3, t1) 
 
	     1.1 move_tower (1, ??, ??, ??) 
	     1.2 move_one_disk (??, ??) 
	     1.3 move_tower (1, ??, ??, ??)
Your job is to complete the trace of the execution of this algorithm, including the designation of steps 1.1.1, 1.1.2, 1.1.3, 3.1, 3.2, 3.3 etc., etc., etc. Remember that the algorithm continues to recurse until n=0. You need not specify the from and to towers for the n=0 calls to move_tower. Just place a dash in place of these designations—e.g., 
 
	move_tower (0, --, --, --)

Due Date: To be determined.

Return to Previous Page