Beefy Boxes and Bandwidth Generously Provided by pair Networks
Problems? Is your data what you think it is?
 
PerlMonks  

Re: Recursion Confusion

by pemungkah (Priest)
on Apr 29, 2013 at 23:08 UTC ( #1031293=note: print w/ replies, xml ) Need Help??


in reply to Recursion Confusion

Let's look at the problem this way. I need to move N disks from A to B; I can use C if I want.

If I have one disk, that's easy: I just move it from A to B. Done, and I didn't need C. (That's the first part.)

If I have two, then I have to move the smaller disk out of the way (to peg C), move the biggest disk to peg B, then move the smallest disk to peg B again. Generalizing, I need to move the disks on A that are "in the way" to C (thereby getting them "out of the way"), using B as a workspace if I need it, move the disk I actually want to move to B, then move the stack on C to B using A for workspace if I need it. It might be clearer like this:

sub move_disks_from_one_peg_to_another_peg_using_a_third { my ($n, $peg_a, $peg_b, $peg_c) = @_; if ($n == 1) { print "Move disk #1 from $peg_a to $peg_b.\n"; return; } else { move_disks_from_one_peg_to_another_peg_using_a_third($n-1, $peg_ +a, $peg_c, $peg_b); print "Move disk #$n from $peg_a to $peg_b.\n"; move_disks_from_one_peg_to_another_peg_using_a_third($n-1, $peg_ +c, $b, $peg_a); return; } }
Notice that we have the necessary criteria in place for a recursive algorithm: we have a bottom-out condition (when $n == 1, move the single disk), and we have a recursive call that guarantees we reach bottom ($n is decremented on each subsequent call). This only partly solves the problem, though: the recursive algorithm has moved N-1 disks "out of the way", and we have to move them all again to put them in their final position; this is why we need the second call. This call is also guaranteed to bottom out, because it decrements $n each time it is re-called.

The four-disk solution visualization here should help a lot: the target peg in this visualization is #3; note how we have to move the top 3 disks out of the way, then put them back, and that we have to repeat this for each successively-higher layer.


Comment on Re: Recursion Confusion
Download Code

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://1031293]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others browsing the Monastery: (13)
As of 2015-07-29 22:47 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (269 votes), past polls