*Why*this works can best be seen by solving the puzzle with two pennies and three squares written on a piece of paper. Once you understand two pennies, three and up are solved exactly the same way.

All things are lawful, but not all things are profitable.

Norm Radder wrote:The code needs some comments describing why it is doing things in the order it does them.

Comments are good but you could use better names that clearly reflect the purpose of the variables/paramters. The method name could also be improved.

As described in this article: http://arlobelshee.com/good-naming-is-a-process-not-a-single-step/ selection of good names is a process. Further experimentation might lead to these choices:

You may have other preferences but that last one is probably what I'd settle on using.

This page http://www.javawithus.com/programs/towers-of-hanoi shows you other naming options and gives a detail explanation of the algorithm.

*Practice only makes habit, only perfect practice makes perfect.
Practice mindfully by doing the right things and doing things right.*— Junilu

[How to Ask Questions] [How to Answer Questions]

Henry

Henry Wong wrote:

As a side question, do you know what a Tower of Hanoi puzzle is? I actually once found one years ago in some small quaint town while on vacation. Part of me regrets now buying it, but the other parts know how tedious the solution is, and will never do it the correct way.

I assume you meant to write "Part of me regrets

**not**buying it, ... "

You don't strike me as one who would while away time just to know when the world is going to end anyway.

*Practice only makes habit, only perfect practice makes perfect.
Practice mindfully by doing the right things and doing things right.*— Junilu

[How to Ask Questions] [How to Answer Questions]

- 1

Lindsey, the second image you posted is EXACTLY what's wrong with most explanations, and why people don't get recursion. You need to forget about the individual movements, and think of the bigger picture. This is a much better explanation, I think:

Initial case:

|_ | |

|__ | |

|___ | |

|____ | |

|_ | |

|__ | |

|___ | |

|____ | |

Recursive step:

`(Move a smaller tower with the exact same algorithm)`

| | |

| |_ |

| |__ |

|____ |___ |

| | |

| |_ |

| |__ |

|____ |___ |

Work reducing step:

`(Reduce the amount of work to be done by moving a disk to its final location)`

| | |

| |_ |

| |__ |

| |___ |____

| | |

| |_ |

| |__ |

| |___ |____

Recursive step:

`(For this particular problem, we need to perform the recursive step a second time)`

| | |_

| | |__

| | |___

| | |____

| | |_

| | |__

| | |___

| | |____

Understanding recursion lies in believing that the recursive step "just works".

*The mind is a strange and wonderful thing. I'm not sure that it will ever be able to figure itself out, everything else, maybe. From the atom to the universe, everything, except itself.*

*Practice only makes habit, only perfect practice makes perfect.
Practice mindfully by doing the right things and doing things right.*— Junilu

[How to Ask Questions] [How to Answer Questions]

The original code has no constraints. It says nothing about allowing larger discs being placed on smaller ones. We all recognize it as the tower of Hanoi puzzle because we've been there.

The original code works, but I could write a piece of code that achieves the same thing much more easily by stacking the discs upside down on the second peg, and then restacking them upside down again a second time on the third peg.

In fact, the original code doesn't even have a goal. It solved a puzzle for which we don't know the outline.

*The mind is a strange and wonderful thing. I'm not sure that it will ever be able to figure itself out, everything else, maybe. From the atom to the universe, everything, except itself.*

Practice mindfully by doing the right things and doing things right.

[How to Ask Questions] [How to Answer Questions]

The algorithm says nothing about having to avoid placing a larger disc on a smaller one. Norm is pointing out that comments should make this clear.

Piet mentions that it's clear from the ordering of the initial pillar. You're siding with him. I disagree.

Never mind, I misread what everyone said. I agree with Norm that things could have been made clearer with comments. I agree with you and Piet that nothing is violated. The confusion stems because there wasn't a problem outline in the first place, and we assumed a problem because we're all familiar with the towers of Hanoi.

*The mind is a strange and wonderful thing. I'm not sure that it will ever be able to figure itself out, everything else, maybe. From the atom to the universe, everything, except itself.*

Some considerations about the order of moves:

if one disc - first (and only) move is origin to target tower

if two discs - first move is to the via tower

Does this make a rule on where to make the first move?

To move a tower of 4 disks, first move a smaller tower of 3 disks to the intermediate pole, then move the bottom disk to the target pole (a trivial step) then move the 3-disk tower to the target pole.

To move a tower of 3 disks, first move a smaller tower of 2 disks ...

To move a tower of 2 disks, first move a smaller tower of 1 disk ...

At each recursive step, you basically start with a new problem and forget there's actually any other disks involved besides the ones in the current smaller tower.

Practice mindfully by doing the right things and doing things right.

[How to Ask Questions] [How to Answer Questions]

- 2

So how do we move a tower of size 3 one peg to the right? Easy, we first move a tower of size 2 to the last peg (step 3), move the next disc to the second peg (step 4), and then move the tower of size 2 on top of the second peg as well.

So how do we move a tower of size 2? First we move a tower of size 1... etc. etc.

This is recursion. Divide the problem into smaller problems that you can solve with the same algorithm.

- 2

How do you move a tower of 4 disks from pole 1 to pole 3? (step 0)

1a. Move tower of 3 disks from 1 to 2 (step 7)

1c. then move tower of 3 disks from 2 to 3 (step 15)

How do you move a tower of 3 disks from pole 1 to pole 2? (subtask 1a, from step 0)

2a. Move tower of 2 disks from 1 to 3 (step 3)

2c. then move tower of 2 disks from 3 to 2 (step 7)

How do you move a tower of 2 disks from pole 1 to pole 3? (subtask 2a, from step 0)

How do you move a tower of 2 disks from pole 3 to pole 2? (subtask 2c, from step 4)

How do you move a tower of 3 disks from pole 2 to pole 3? (subtask 1c, from step 8)

5a. Move tower of 2 disks from 2 to 1 (step 11)

5c. then move tower of 2 disks from 1 to 3 (step 15)

How do you move a tower of 2 disks from pole 2 to pole 1? (subtask 5a, from step 8)

How do you move a tower of 2 disks from pole 1 to pole 3? (subtask 5c, from step 12)

How do you move a tower of 4 disks from pole 1 to pole 3? (step 0)

1a. Move tower of 3 disks from 1 to 2 (step 7)

**1b. then move disk 4 from 1 to 3 (step 8)**1c. then move tower of 3 disks from 2 to 3 (step 15)

How do you move a tower of 3 disks from pole 1 to pole 2? (subtask 1a, from step 0)

2a. Move tower of 2 disks from 1 to 3 (step 3)

**2b. then move disk 3 from 1 to 2 (step 4)**2c. then move tower of 2 disks from 3 to 2 (step 7)

How do you move a tower of 2 disks from pole 1 to pole 3? (subtask 2a, from step 0)

**3a. Move tower of 1 disks from 1 to 2 (step 1)****3b. then move disk 2 from 1 to 3 (step 2)**

3c. then move tower of 1 disks from 2 to 3(step 3)

3c. then move tower of 1 disks from 2 to 3(step 3)

How do you move a tower of 2 disks from pole 3 to pole 2? (subtask 2c, from step 4)

**4a. Move tower of 1 disks from 3 to 1 (step 5)**

4b. then move disk 2 from 3 to 2 (step 6)

4c. then move tower of 1 disks from 1 to 2 (step 7)4b. then move disk 2 from 3 to 2 (step 6)

4c. then move tower of 1 disks from 1 to 2 (step 7)

How do you move a tower of 3 disks from pole 2 to pole 3? (subtask 1c, from step 8)

5a. Move tower of 2 disks from 2 to 1 (step 11)

**5b. then move disk 3 from 2 to 3 (step 12)**5c. then move tower of 2 disks from 1 to 3 (step 15)

How do you move a tower of 2 disks from pole 2 to pole 1? (subtask 5a, from step 8)

**6a. Move tower of 1 disks from 2 to 3 (step 9)**

6b. then move disk 2 from 2 to 1 (step 10)

6c. then move tower of 1 disks from 3 to 1 (step 11)

6b. then move disk 2 from 2 to 1 (step 10)

6c. then move tower of 1 disks from 3 to 1 (step 11)

How do you move a tower of 2 disks from pole 1 to pole 3? (subtask 5c, from step 12)

**7a. Move tower of 1 disks from 1 to 2 (step 13)**

7b. then move disk 2 from 1 to 3 (step 14)

7c. then move tower of 1 disks from 2 to 3 (step 15)7b. then move disk 2 from 1 to 3 (step 14)

7c. then move tower of 1 disks from 2 to 3 (step 15)

Practice mindfully by doing the right things and doing things right.

[How to Ask Questions] [How to Answer Questions]

Practice mindfully by doing the right things and doing things right.

[How to Ask Questions] [How to Answer Questions]

Practice mindfully by doing the right things and doing things right.

[How to Ask Questions] [How to Answer Questions]

no, I mean that you could start with a pile where the largest disc is in the middle, on top of the smallest one, et cetera.

What you get is an identically ordered pile, on another pole.

We're so used to start with this nicely ordered pile in the TOH, that we tend to forget that the algo was derived from the rule that only a smaller disc could be placed on top of a larger. But having this algo now, that ordering is in fact irrelevant. I think we all mean the same, but this "mother of all recursion examples" keeps being confusing! And that makes it an evergreen

algo was derived from the rule that only a smaller disc could be placed on top of a larger.

I'm still having problems seeing how the algo was designed to follow that rule. Without that rule, a simpler algo would be: Move all from origin to via and then move all from via to target.

Another value that is not used when a person does the moves manually is the numdiscs variable. With my rewrite of the code using Stacks, could the algo use the contents of the Stacks vs numdiscs to control its execution? The use of that variable needs tobe explained for the OP and me to understand the algo.

Assuming the subtasks that move 3 disks never breaks the "no larger disk on top of a smaller one" rule, then this breakdown and all its subtasks never break that rule. When drilling down into the subtasks, you basically forget that you have any other disks besides the ones in the current subset and you still don't have to worry about breaking the "no larger on smaller" rule.

I guess Piet's point is that if you ignore the "no larger on smaller rule" and you have the same numbering of the disks but changed their sizes, the order in which the disks will be moved by this particular algorithm will be the same regardless. Say for example, if disk 1 was the biggest, disk 3, the second biggest, then disk 4, then disk 2 being the smallest. If you still stack these as disk 1, 2, 3, 4 from top to bottom then the textual description I generated a few posts ago would still correctly describe the solution.

Practice mindfully by doing the right things and doing things right.

[How to Ask Questions] [How to Answer Questions]

given a pile of discs, with the largest at the bottom and the smallest at the top, move the whole pile to another pole, maintining the ordering of course. This must be done one disc at a time, and with the proviso that we can only put a smaller disc on top of a larger disc.

Now, we must move the largest disc, sooner or later, and the only way to do so is to clear the way for that disc. So, move all the N - 1 smaller discs to the spare, then we can move the largest one to the target pole..

But then we're not finished: we still must move the N - 1 discs to the target pole as well. And that involves moving N - 1 discs to another pole, in essence are we now facing the same problem, albeit that we are nearer to our base case.

So, that is what the three line algo is doing: moving N - 1 discs to the spare, moving the largest one to the target, and moving the N - 1 discs also to the target.

And then we must read Stephans remark: since this whole recursion is way too complex for a human to follow, we have no alternative than to believe that it works! (well, after much testing, of course!).

And as a bonus (which is easily proven by induction): if we need f(N) moves to move a pile of N discs, then for a pile of N + 1 discs, we need: f(N) + 1 + f(N) moves, so we get the recurvie relation:

f(N + 1) = 2 * f(N) + 1.

And that boils down to a total of 2^N - 1.

You mean to say It should start with this?Piet Souris wrote:Maybe Ganesh can produce an identical drawing, but this time with a randomly ordered pile, performing the exact same moves, just for illustration purpose.

Being programmer.

Ganesh Patekar wrote:You mean to say It should start with this?

No, Piet means something like this:

Still start with all disks on one pole but not ordered by size

Practice mindfully by doing the right things and doing things right.

[How to Ask Questions] [How to Answer Questions]

this whole recursion is way too complex for a human to follow, we have no alternative than tobelievethat it works!

Assumingthe subtasks that move 3 disks never breaks the "no larger disk on top of a smaller one" rule

I don't see where my question about why the numdisc variable is used is answered

or why these method calls are in the code for when numdisc not equal to 1:

Ganesh Patekar wrote:not easy to understand practically by tracing how these values gets swapped as It uses stacks. It's been more than 7-8 hours I'm trying to understand how these value gets assigned to each other.

Think of the roles the pole plays in each iteration. A pole is either the origin, the target, or the spare/via pole. These roles change from one iteration to the next and each pole will play only one role in any given iteration.

Ging back to my textual description:

Study how the recursive calls are made because they reflect how the roles of the poles are changing from one level or recursion to the next.

When you start with the 4-disk tower, pole 1 is the origin, pole 2 is the spare, pole 3 is the target. The top-level call to entire solution is

`moveTower(4, 1, 2, 3)`. This starts the recursion.

When you do the first breakdown, the call becomes

`moveTower(n-1, origin, target, via) --> moveTower(3, 1, 3, 2)`

Notice how the roles that two of the poles play changed. When moving the subset with 3 disks, Pole 2, which was initially the spare pole, is now designated as the target pole. Pole 3, which was initially the target, is now designated as the spare.

Practice mindfully by doing the right things and doing things right.

[How to Ask Questions] [How to Answer Questions]

Generally, you have this:

How to move N disks from origin to target using spare?

a. Move subset of N-1 disks from origin to spare

b. Move the remaining disk from origin to target

c. Move subset of N-1 disks from spare to target

If you frame the degenerate case in terms of the above, you get

How to move 1 disk from origin to target using spare?

a. Move subset of 0 disks from origin to spare

b. Move the remaining disk from origin to target

c. Move subset of 0 disks from spare to target

Since moving 0 disks is basically a NO-OP (no operation), the degenerate case becomes simply:

a. --- nothing to do ---

b. Move the remaining disk from origin to target

c. --- nothing to do ---

Or simply:

- Move the disk from origin to target.

Practice mindfully by doing the right things and doing things right.

[How to Ask Questions] [How to Answer Questions]

Campbell Ritchie wrote:Good description but the code style is iffy, and I think there were two mathematical mistakes

I challenge you to find the three things I wasn't happy about.

He didn't consider:

Being programmer.

He did say that factorials were only defined for positive numbers.Ganesh Patekar wrote:. . .What If n is a negative number, no validation.

That was one of the things I noticed; he missed out 0! = 1. The other thing I noticed was related; I would have used 0 as the base case. In fact I would have said that the factorial is only defined for natural numbers, not integers. Since there is no such thing as a negative natural number, that would have given a simpler definition of the domain of the factorial function.What If n is 0 where 0! =1.

No, I think single‑letter arguments are all right when they do not mean anything special, soVariable name n rather number?

*n*meaning any number is OK. I prefer i, j, k, l, m, n for integers and get told off for not using

*x*,

*y*.

Of course the C chappies like single‑letter names because they can save on keystrokes.Campbell's Colleauges wrote:We're only interested in integers; we can usexandy. We're not writing Fortran.

He was writing C which doesn't have a big integer type builti‑in. My problem with the code was the use of return twice, when you can save lots of keystrokes with the ?: operator. I tried some C on Friday, so I should be able to find it and post it here. It's on a different computer, so please wait few minutes for that code. The unsigned keyword doesn't exist in Java®, but it prevents you from using negative numbers. I shall let you work out what −64 means.Return type should have been double Or BigInteger.

I shall let you explain the output for 64! and 66! and −64!Campbell's Computer wrote:[critchie@computer CPrograms]$ gcc -o factorial factorial.c

[critchie@computer CPrograms]$ ./factorial 66

66! = 0

[critchie@computer CPrograms]$ ./factorial 64

64! = 9223372036854775808

[critchie@computer CPrograms]$ ./factorial 21

21! = 14197454024290336768

[critchie@computer CPrograms]$ ./factorial -64

[“forgot” to quote output ]