Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl: the Markov chain saw

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.

Log In?

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

How do I use this? | Other CB clients
Other Users?
Others imbibing at the Monastery: (1)
As of 2023-03-31 02:34 GMT
Find Nodes?
    Voting Booth?
    Which type of climate do you prefer to live in?

    Results (74 votes). Check out past polls.