P is for Practical PerlMonks

### Re: Recursion Confusion

by rnewsham (Chaplain)
 on Apr 27, 2013 at 07:12 UTC ( #1030933=note: print w/replies, xml ) Need Help??

Sometimes I find with recursion it helps to add some tracking to help visualise what path is being followed.

Hope this helps

```use warnings;
use strict;

my \$ndisks = 3;
hanoi( \$ndisks, 'A', 'C', 'B', 0 );

sub hanoi
{
my( \$n, \$start, \$end, \$extra, \$depth ) = @_;

print "\t"x\$depth . "n=\$n, start=\$start end=\$end extra=\$extra\
+n";

if( \$n == 1 )
{
print "\t"x\$depth . "Move disk #\$n from \$start to \$end
+\n";
}
else
{
\$depth++;
print "\t"x\$depth . "Calling hanoi 1\n";
hanoi( \$n-1, \$start, \$extra, \$end, \$depth);
print "\t"x\$depth . "Move disk #\$n from \$start to \$end
+\n";
print "\t"x\$depth . "Calling hanoi 2\n";
hanoi (\$n-1, \$extra, \$end, \$start, \$depth);
}
}

```n=3, start=A end=C extra=B
Calling hanoi 1
n=2, start=A end=B extra=C
Calling hanoi 1
n=1, start=A end=C extra=B
Move disk #1 from A to C
Move disk #2 from A to B
Calling hanoi 2
n=1, start=C end=B extra=A
Move disk #1 from C to B
Move disk #3 from A to C
Calling hanoi 2
n=2, start=B end=C extra=A
Calling hanoi 1
n=1, start=B end=A extra=C
Move disk #1 from B to A
Move disk #2 from B to C
Calling hanoi 2
n=1, start=A end=C extra=B
Move disk #1 from A to C

Replies are listed 'Best First'.
Re^2: Recursion Confusion
by live4tech (Sexton) on Apr 29, 2013 at 03:55 UTC

Thank you for this, your post was one of the most helpful replies. Although it is clear that I can see exactly WHAT is going on and WHEN by the method you demonstrate, I still do not have a real understanding of WHY the events are occurring when they do or WHY the values are what they are at those points. I don't think any amount of tracing or visualization of program flow will explain this. Perhaps I will never really understand this type of recursion.

Don't worry recursion is a difficult thing to grasp at first. I have been using recursion for years and it still gives me a headache.

It sounds like your problem is understanding how you are getting the order of output that you are. You expect to see output in a order for example 1,2,3,4 but are seeing what you think is 1,3,4,2. This is a common trap with thinking about recursion. An easy way to get that code mixed up would be to expect the call I have commented as "hanoi 2" to be executed immediatly after the call to "hanoi 1". This is not the case at that point the sub hanoi is called so you will either hit the other condition in the if or call hanoi 1 again. The calls to hanoi 1 will continue until n==1 then that path ends and then the call hanoi 2 is made.

With most programming problems reducing the complexity to a small number of iterations can be the best way to visualise what is happening. However sometimes with recursion you need it to have more iterations to be able to see the pattern. Try increasing the number of disks in my example code, somewhere between five and ten should be enough. That should help you see the pattern of what the code is doing.

Create A New User
Node Status?
node history
Node Type: note [id://1030933]
help
Chatterbox?
 [choroba]: Morning! [Corion]: [Corion]: Yesterday I've been mulling over how to best generate HTTP requests from permutations of values but I haven't found a nice API for passing in the "template" of the HTTP request yet. I guess I'll have to do a SoPW for that [Corion]: The API itself will basically be my \$iter = generate_http_requ ests(method => 'GET', url => '/settings/:name', headers => ???, get_params => ['foo','bar']), but I'm not sure how to parametrize values in the headers and how to specify lists of ... [choroba]: On the other hand, lots of options to receive the requests :-) [Corion]: ... values to be used. For example, I think for headers, one would want to have various kinds of Content-Encoding headers, but for the get_parameters one would have various kinds of Bobby Tables [choroba]: What about [metadoc:// Algorithm::Loops]? [Corion]: choroba: Yeah, but handing off the request to Dancer,Plack, Mojolicious,LWP is easy once I have the data filled into some structure ;)) [Corion]: choroba: I'm using that to generate the permutations, but I don't know how the user can pass the intended values to my function in a sane way

How do I use this? | Other CB clients
Other Users?
Others making s'mores by the fire in the courtyard of the Monastery: (5)
As of 2017-01-17 08:12 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
Do you watch meteor showers?

Results (152 votes). Check out past polls.