Fun with Recursion

by Dr. Peter Wayne

Let's take a break from database programming and have a little fun. For those of you who are unfamiliar with the Towers of Hanoi problem, I'll state it for you:

In a temple in Hanoi, there have been 3 towers from time immemorial. 64 disks of decreasing size were placed in the first tower, with the largest on the bottom, and then each smaller one on top. The priests of the temple have to move all the disks from the first tower to the second tower. At no time may a larger disk be placed on top of a smaller disk. They may use the third tower as a temporary holding place for disks.
Each day, the priests are allowed to move one disk. When the last of the 64 disks is eventually placed on the top of the second tower, the end of the world will arrive.

• How many moves will it take to restack the disks?
• Can you devise a program to direct the priests?
• Can we represent the problem graphically in Alpha Five?

This is a tall order (yes, that was a pun.) We won't try the solution for 64 disks here - the reason will become apparent later - but we'll try the solution for a smaller number, say 7 disks. Our initial screen will look like this:

Figure 1. Initial state of Towers of Hanoi with 7 disks.
After pressing the Move disks button, the disks are progressively moved. Here is what the towers look like after 12 moves:
Figure 2. Towers of Hanoi after 12 moves.
To solve the Towers of Hanoi problem, we have to learn a little about 2 areas of coding that may be unfamiliar to many database programmmers: recursive programming and animation.

Recursion takes place when an entity is defined partly in terms of itself. For example, I could define my ancestors as my parents, plus all my parents' ancestors. This is a very complete definition, it is much shorter than trying to enumerate all my ancestors, and it captures the essence of the ancestral relationship. [Gertrude Stein's A rose is a rose is a rose is not really a recursion - it's a tautology.] In your high school math, you probably learned a definition for a factorial that is

n! = n *(n-1)* (n-2)* (n-3)*...*(1)

In a recursive definition, which Alpha Five supports, we can define a function, factorial(n), as n*factorial(n-1):

function factorial as N(n as N)
if n=1 then
	factorial=n
else
	factorial=n*factorial(n-1) 
end if
end function

? factorial(5)
= 120.000000
? 5*4*3*2*1
= 120.000000

A successful recursive function must have a way to end the recursion. The factorial(n) function ends the recursion when n=1. Click here for a nonrecursive coding of factorial().

With this in mind, we can now sketch out a recursive solution to the problem of moving n disks from pegA to pegB, using pegC as an auxiliary peg.
Actually, we don't even know now whether any solution exists! However, we can think about the solution in this way. Suppose we have 7 disks that we want to move from A to B, using C as an auxiliary. Now, let us hypothesize that we already know how to move 6 disks from A to C, using B as the auxiliary. If we know the answer to the 6-disk problem, then we move the 6 disks first, then move the remaining bottom disk from A to B, and then finish the problem by moving the 6 disks again from C to B. Remember, we are hypothesizing that we know the answer to the 6-disk problem!
But what if we don't know the solution to the 6-disk problem? Once again, we hypothesize that we know the solution to the 5-disk problem. If we know how to move 5 disks, then we know how to move 6. And so on backwards, until we arrive at the 1-disk problem.
The solution to the n-disk problem is then

• if n=1 then move the disk from A to B, otherwise
• move the top n-1 disks from A to C, move the remaining disk to B, and then move the pile of n-1 disks back to A from C. Then repeat the move from A to B, this time with only n-1 disks.

If the solution seems like cheating, it's because it is because we are not trained to think recursively recursively. The code for the script hanoi() to calculate the solution for 5 disks is:

''XBasic
dim shared moves as n

function towers as n(disks as n, frompeg as c, topeg as c, auxpeg as c)
dim shared moves as n
if disks=1 then
	ui_msg_box("","moves disk 1 from "+frompeg+" to "+topeg)
	moves=moves+1
else
	towers(disks-1,frompeg,auxpeg,topeg)
	ui_msg_box("","move disk "+alltrim(str(disks))+" from "+frompeg+" to "+topeg) 
	moves=moves+1
	towers(disks-1,auxpeg,topeg,frompeg)
end if
towers=moves 
end function

moves=0
ui_msg_box("5 disks",alltrim(str(towers(5,"source","destination","auxiliary")))+" moves required")
    

Script 1. Nongraphical solution of Towers of Hanoi

Now it's time to up the ante and present the promised graphical solution. You can start by creating a blank form and with 7 character variables, "disk1" through "disk7":
Figure 3. Create 7 form-level variables, one for each disk.

Next, place disk7 on the bottom left of the form. In Field Properties, Dimensions adjust the position and dimension of disk7 to be 2.2 inches from the top, 0.0 inches from the left, with a width of 2.0 inches and a height of 0.2 inches. The code that we will later write uses these values, so it is important to establish them properly.

Figure 4. Dimension field properties for the bottom disk.

Next, place the remaining disks, disk6 through disk1, on the form. Each subsequent disk is 0.2 inches less wide than the one below it, but it is the same height and is centered around the 1" horizontal mark. Choose distinctive colors for each disk:
Figure 5. All 7 disks are placed on the form.

Finally, place a button labled "Move disks" in the upper right hand corner of the form. It is very important that this button be placed in the extreme right of the form, because of a limitation in Alpha Five's form repainting routine. Alpha Five speeds up its form repainting by deciding how much of the form is occupied. If we don't place an object on the right hand side of the form, then Alpha Five considers that only the portion of the screen with the disks is occupied and needs to be repainted. As we move the disks around on the form, Alpha Five 3.04 will only repaint them if they fall in the "repaint zone." By placing this button (or any other object) on the extreme right of the form, we make sure that the repaint zone extends all the way across the form. See Figure 1 for the position of the Move disks button.

To move an object from one position to another, we will take advantage of the object properties of the form-level object. Each form-level object has several object properties which you can discover through looking at the Xbasic Explorer.

In this view of the Xbasic Explorer, we have "drilled down" to the object properties of the disk1 form-level object. Among these properties are several that specify the object's position on the form: left, width, top, and height.
We'll use these position properties to move our disks around on the form. We'll also use the object's fill.forecolor property to erase the vestiges of the object from its old position. If we don't explicitly erase the disk from its old position, Alpha Five will sometimes leave pieces of the object behind during script execution. These extraneous unrepainted pixels will all be repainted when the script finishes, but we don't want to wait until the end of the script, so we'll force an explicit recoloring.

The script to move the disks follows the outline of Script 1 with the addition of the object repainting code. Here is the new code with comments:

''XBasic
CONSTANT NDISKS=7
dim shared peg[3] as n

' array of disk widths
dim shared w[NDISKS] as n
 w[7]=2.0
 w[6]=1.8
 w[5]=1.6
 w[4]=1.4
 w[3]=1.2
 w[2]=1.0
 w[1]=0.8

' horizontal positions of of each peg
dim shared spindle[3] as n  
SPINDLE[1]=1
SPINDLE[2]=3
SPINDLE[3]=5

' top position of each disk
dim shared t[NDISKS] as n
t[1]=2.2
t[2]=2.0
t[3]=1.8
t[4]=1.6
t[5]=1.4
t[6]=1.2
t[7]=1.0

if this.text="Reset disks" then
	goto reset 
end if

' initialize each peg with number of disks on the peg
peg[1]=NDISKS
peg[2]=0
peg[3]=0

' this function moves a disk object from the top of one peg to another
function move_to_peg as l(disknum as n, frompeg as n, topeg as n)
CONSTANT NDISKS=7
dim shared peg[3] as n
dim shared t[NDISKS] as n
dim shared w[NDISKS] as n
dim shared spindle[3] as n
dim dsk as p
dim dskname as c
dskname="disk"+alltrim(str(disknum))
dsk=obj(dskname)
oldcolor=dsk.fill.forecolor
dsk.fill.forecolor="gray"
dsk.refresh()
peg[frompeg]=peg[frompeg]-1
peg[topeg]=peg[topeg]+1
lpos=spindle[topeg]-0.5*w[disknum]
tpos=t[peg[topeg]]
dsk.object.left=lpos
dsk.object.top=tpos
dsk.fill.forecolor=oldcolor
dsk.refresh()
sleep(.1)
move_to_peg=.t.
end function

dim shared moves as n

function towers as n(disks as n, frompeg as n, topeg as n, auxpeg as n)
dim shared moves as n
if disks=1 then
	'ui_msg_box("","moves disk 1 from "+alltrim(str(frompeg))+" to "+alltrim(str(topeg)))
	move_to_peg(1,frompeg,topeg)
	moves=moves+1
else
	towers(disks-1,frompeg,auxpeg,topeg)
	'ui_msg_box("","move disk "+alltrim(str(disks))+" from "+alltrim(str(frompeg))+" to "+alltrim(str(topeg))) 
	move_to_peg(disks,frompeg,topeg)
	moves=moves+1
	towers(disks-1,auxpeg,topeg,frompeg)
end if
towers=moves 
end function

' "Move disks" script begins here
moves=0
towers(NDISKS,1,2,3)
ui_msg_box("","It took "+alltrim(str(moves))+" moves")
this.text="Reset disks"
end

' reset is called after the disks are moved once
' it moves all the disks back to their initial positions
reset:
peg[1]=NDISKS
peg[2]=0
peg[3]=0
for i=1 to NDISKS
	diskname="disk"+alltrim(str(i))
	dsk=obj(diskname)
	lpos=spindle[1]-0.5*w[i]	
	dsk.object.left=lpos	 
	dsk.refresh()
next
this.text="Move disks"
end

Script 2. Script to move the disk objects on a form
The script dynamically changes the button text from its initial Move disks to Reset disks after the script has run. It also tells you the number of moves required.
Experimentation with different values of n gives the following results:

Table 1. Relationship between disks and moves

Inspection of the above table shows that 2n-1 moves are required to move n disks. Can we prove that? Certainly. Let us remember how we derived the recursive procedure in the first place. Take the problem of moving 3 disks. We move 3 disks from A to B by moving the top 2 disks from A to C, moving the bottom disk from A to B, and then moving the 2 disks from C to B. That is, to move 3 disks, we move 2 disks twice and then have one more move. The number of moves for n disks is then 2*(number of moves for n-1 disks)+1. Since only 1 move is needed for 1 disk, we know that for 1 disk, we need 21-1 moves. For 2 disks, we double that and add one, that is, 2*(21-1)+1, or 22-2+1, which finally becomes 22-1 moves. And so on for 3 disks up to n disks, for which the formula 2n-1 holds.

So - how long will it take the priests to move all 64 disks from the first tower to the second tower? We can use the Interactive window to calculate the number of days (remember, the priests only move one disk per day). Then, using the value of 365.25 days in a year, we can calculate the number of years, and finally, considering the age of the universe as 15 billion years, how much longer we can expect to continue before the priests finish:

days=2^64-1
? days
= 18446744073709552000.000000

years=days/365.25
? years
= 50504432782230120.000000

universe_lives=years/(15*10^9)
? universe_lives
= 3366962.185482

So the universe is only one 3-millionth of its way towards its end. That is reassuring, and should give Alpha Software enough time to come out with Alpha Five version 4!
Too tired to design the form, or just want to see what it looks like? Click here to download the Towers of Hanoi form and script.

7/14/98 - pkw

Don't forget, we need your feedback to make this site better!

Return to home