Pathologically Eclectic Rubbish Lister PerlMonks

### Re: Recursion Confusion

by BrowserUk (Pope)
 on Apr 27, 2013 at 07:36 UTC ( #1030936=note: print w/replies, xml ) Need Help??

in reply to Recursion Confusion

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.
/c

Create A New User
Node Status?
node history
Node Type: note [id://1030936]
help
Chatterbox?
 [choroba]: when you're waiting for something, you sleep for \$x, then \$x * 2, then \$x * 2 * 2, etc. up to a max or timeout [erix]: right. yeah, sounds useful [choroba]: it's handy when most of the times you get the response back almost immediately, but in rare cases, it can take longer time [choroba]: in this particular case, we're fetching messages from Kafka

How do I use this? | Other CB clients
Other Users?
Others exploiting the Monastery: (10)
As of 2018-04-19 15:11 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
My travels bear the most uncanny semblance to ...

Results (74 votes). Check out past polls.

Notices?