Talk:Towers of Hanoi

recursion redirect?

Why does recursion redirect here? This isn't the only task that can be solved with recursion. I'd almost prefer to see a category dedicated to recursion, with pages with recursive examples added to that category. --Short Circuit 23:43, 7 November 2007 (MST)

I could try my hand at making it for you and finding articles that fall under the category. I may need a small amount of instruction to get me going though. --mwn3d 15:22, 8 November 2007 (EST)

Done. --Mwn3d 17:41, 27 January 2008 (MST)

Who or what is "Towers of Hanoi"?

There seems to be some assumption here that everyone and their aunt must be intimately familiar with the "Towers of Hanoi"

now I needed to do a Google search to get a clue as I can find no clue on this Wiki....

["http://www.google.com/search?hl=en&q=%22Towers+of+Hanoi%22&btnG=Google+Search"]

Verbose explanation for J

Here is one of the J implementations:

This could be rephrased as:

<lang j>H =: elsePart ` thenPart @. * elsePart=: i.@,&2 thenPart=: ({&0 2 1,0 2,{&1 0 2)@H@<:</lang>

First off, note that this rephrasing has introduced two new names and has also replace anonymous recursion ($:) with non-anonymous recursion (H) -- it would be bad to have the recursion happen purely within thenPart without the conditional which was in the original definition of H.

But, wait, why does else come before then? (For the same reason that 0 comes before 1:) The primitive @. uses its right argument to come up with an index which is used to select from the code fragments on the left.

In this case, the right argument to @. is * which returns 0 for zero arguments and 1 for positive arguments. So the test, in essence is: is the right argument greater than zero?

This means that elsePart only runs with a right argument of zero. And it looks like this:

In other words, it returns nothing. (But it is a carefully crafted nothing: it is a numeric array with two columns and no rows.)

Now let's consider thenPart with an argument of 1:

This is equivalent to:

Which, in turn, is equivalent to

Which, in turn, is equivalent to:

And { is J's indexing function, but since no actual indices are being used, this is equivalent to:

In other words, we have these two column arrays with no rows and between them we put a row that has the values 0 2. So the result looks like this:

Simple, no? (Or, it's simple once you get used to the idea of manipulating empty arrays which have structure but no elements. Until then this whole idea of working with nothing can seem a bit strange. But, if that bothers you, then maybe you can have some sympathy for how romans must have felt when they first encountered arabic numerals.)

Now, for the H 2 case, we know from the above that we are going to be evaluating:

And, 0 2 { 0 2 1 yields 0 1 Likewise 0 2 { 1 0 2 yields 1 2. Thus the result of H 2 is this array:

In other words, for H n, we find H n-1 and use that result twice:

First, we use it (the previous hanoi solution) keeping our starting point the same, and swapping the use of the other two pegs. Then (after we have moved our disk from peg 0 to peg 2), we use it again but holding the end point the same and swapping the use of the first two pegs.

(Some people might feel they should object to this remapping of results as inefficient, but this remapping does not make a difference to the big O efficiency, and in practice should be a minor concern.)

A bunch of sample codes are buggy

The bug is that they print ndisk, which is the number of remaining disks to be moved, as if it was the index of the disk to be moved. Can someone correct these bugs?