A step-by-step explanation is what I am looking for.
Okay. (but you could have produced this yourself; see Devel::Trace):
But, whilst that may help you wrap your head around an existing recursive implementation, it probably won't help you with writing your own recursive routines.
The trick to understanding and using recursion is to avoiding trying to 'run the loops' in your head, and instead think about the subroutine in snapshots. That is to say, imagine each of the situations (states) that could exist at the point of entry to the subroutine and then what needs to be done to move that state to the next state.
So for the routine above the are two states:
- $n == 1
If there is only one disc, then all that is required is to move that disc directly from the $start to the $end and exit.
- $n != 1
Start with the simplest situation, of $n == 2.
In this case, there are three steps required:
- Move the top disc from the $start to the $extra.
This can be achieved by pretending that there is only one disc to move and that the $extra is the $end. In this way, we can call ourselves and the first state handler (above) will do the work.
So reduce the count to one, switch the $end for the $extra and call ourselves recursively.
- Move the second disc from the $start to the $end
With the top disc out of the way (on $extra), we can now move the second disk from the $start to the $end unimpeded.
(The print statement does the "work" for this step!)
- Move the top disc from the $extra to the $end
So, again reduce the count to one; but this time, pass $extra as the $start and $end and the end.
And the job is done for 2 discs.
For three discs, we only need to do: the above two disc procedure but from $start to $extra; followed by the one disc procedure from $start to $end; followed by the two disc procedure from $extra to $end.
And by now, you should be able to see that by passing in $n == 3, that is exactly what happens.
With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.
Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
Read Where should I post X? if you're not absolutely sure you're posting in the right place.
Please read these before you post! —
Posts may use any of the Perl Monks Approved HTML tags:
Outside of code tags, you may need to use entities for some characters:
- a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
Link using PerlMonks shortcuts! What shortcuts can I use for linking?
See Writeup Formatting Tips and other pages linked from there for more info.
| & || & |
| < || < |
| > || > |
| [ || [ |
| ] || ] ||