Beefy Boxes and Bandwidth Generously Provided by pair Networks
Clear questions and runnable code
get the best and fastest answer

comment on

( #3333=superdoc: print w/replies, xml ) Need Help??
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:

  1. $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.

  2. $n != 1

    Start with the simplest situation, of $n == 2.

    In this case, there are three steps required:

    1. 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.

    2. 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!)

    3. 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.

In reply to Re: Recursion Confusion by BrowserUk
in thread Recursion Confusion by live4tech

Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":

  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • 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:
    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
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?

    What's my password?
    Create A New User
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others musing on the Monastery: (6)
    As of 2019-02-18 18:49 GMT
    Find Nodes?
      Voting Booth?
      I use postfix dereferencing ...

      Results (100 votes). Check out past polls.