Recursion Confusion

[live4tech]

Hello all! I have never completely understood recursion. I have some understanding of what happens when you have one simple recursive call in a subroutine like the following:

sub factorial 
{
   factorial
   my ($n) = @_;
   return 1 if $n == 0;
   return factorial($n-1) * $n;
}

The sub factorial is called again and again until $n is equal to 0. Then the 1 is returned and all the past calls are then 'really' executed in reverse order, producing the factorial of the number $n.

OK. But I do not understand how recursion works when there is more than 1 recursive call in a subroutine, like the following:

sub hanoi 
{
   my ($n, $start, $end, $extra) = @_;
   if ($n == 1) 
   {
      print "Move disk #1 from $start to $end.\n";
   } 
   else 
   {
      hanoi($n-1, $start, $extra, $end);
      print "Move disk #$n from $start to $end.\n";
      hanoi($n-1, $extra, $end, $start);
   }
}

The output will be:

Move disk #1 from A to C.
Move disk #2 from A to B.
Move disk #1 from C to B.
Move disk #3 from A to C.
Move disk #1 from B to A.
Move disk #2 from B to C.
Move disk #1 from A to C.

Can anyone explain precisely why this is the output. If the first recursive call were called over and over untill $n==1 and then they 'fell' back and all the calls were executed in reverse order, the third line of output does not make sense. Is the next recursive line then executed? A step-by-step explanation is what I am looking for.

Thank you!

[BrowserUk]

A step-by-step explanation is what I am looking for.

Okay. (but you could have produced this yourself; see Devel::Trace):

<Reveal this spoiler or all in this thread>

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.

/c

[rnewsham]

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

[live4tech]

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.

[rnewsham]

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.

[kcott]

G'day live4tech,

You don't say where you got these subroutines from but the originals (except for an errant factorial line in the first) come from Mark Jason Dominus' book "Higher-Order Perl" (see his home node for links to various versions). A description of recursion starts at the beginning of Chapter 1; section 1.3 describes the Tower of Hanoi puzzle.

[Athanasius]

When hanoi is called with $n > 1, the code in the else clause runs as follows:

1. first recursive call with $n - 1
2. The print statement you say “does not make sense”
3. second recursive call with $n - 1

Update: My initial explanation with $n == 3 was wrong. Simpler to let $n == 2:

So with $n initially set at 2, (1) is executed. It recursively calls hanoi with $n == 1. At this point the if clause executes, and the function returns. Next, (2) produces the output that is confusing you. Then (3) produces another recursion; when this returns, the initial call to hanoi also returns, and the function is complete.

(Where I got confused earlier:) For each recursive call to hanoi where $n > 2, an additional else clause comes into play, adding its own print statement to the output.

Perhaps this helps: Every output statement where $n == 1 is written by the print statement in the if clause. Every other output statement (where $n > 1) is written by the print statement sandwiched between the two recursive calls in the else clause.

Clear now? ;-)

[Laurent_R]

Well, to understand recursion, you first need... to understand recursion. ;-)

More seriously, various useful and valuable suggestions have been made by others above, like using the Devel::Trace module or adding useful print statements to follow what is going on. Another way to try to understand this type of things, that I am using quite frequently when I have trouble to understand how a program works, is to run the program step by step under the Perl debugger. The most useful options to start with may be s, c, n and r to control the flow of your program, p and x to print the value of variables or expressions, and w to add a watch on a variable. Use the h option (help) to better understand what these other options do. Or type perldoc perldebug for more help on the debugger.

[tobyink]

I think perhaps your confusion stems from thinking that there is only one variable called $n. In fact, each call to your function creates a brand new $n variable.

Study this. Note that I never add anything to $n - only subtract from it. Now run it to see the output:

use strict;
use warnings;

sub counter
{
    my ($n) = @_;
    
    print "N is $n\n";
    
    if ($n > 0) {
        counter($n - 1);
    }

    print "N is $n\n";
}

counter(4);

[derby]

To understand recursion, see Re: Recursion Confusion.

update: ... okay ... not really recursion but ...

[LanX]

OMG ... some bots parsing the monastery just crashed with memory leaks!

[Laurent_R]

Very good point.

:-)

[karlgoethebier]

@derby:

...that's why i don't recurse ;-)

Regards, Karl

[Anonymous Monk]

A tip from Visualizing recursion with the fib() example is to use Devel::TraceCalls
Read more... (675 Bytes)

TRACE: main::hanoi( 3, 'A', 'C', 'B', 0 )
TRACE: +-main::hanoi( 2, 'A', 'B', 'C' )
TRACE: | +-main::hanoi( 1, 'A', 'C', 'B' )
Move disk #1 from A to C.
Move disk #2 from A to B.
TRACE: | +-main::hanoi( 1, 'C', 'B', 'A' )
Move disk #1 from C to B.
Move disk #3 from A to C.
TRACE: +-main::hanoi( 2, 'B', 'C', 'A' )
TRACE: | +-main::hanoi( 1, 'B', 'A', 'C' )
Move disk #1 from B to A.
Move disk #2 from B to C.
TRACE: | +-main::hanoi( 1, 'A', 'C', 'B' )
Move disk #1 from A to C.

[karlgoethebier]

James: "Oh, must I, Miss Sophie?" Miss Sophie: "James, please, please..." (from Dinner for one by Lauri Wylie)

This doesn't really help and i'm shure that i'm about loosing friends but: some recurse and some don't. I don't.

So take this just as addendum and for fun:

• Towers of Hanoi at Wolfram
• Non-recursive solution

Regards, Karl

[sundialsvc4]

The key to understanding recursion is to realize where the my variables that are declared within a sub actually live:   “on the stack,” which also contains information needed to return from a subroutine call.   When any subroutine calls itself, directly or indirectly, i.e. “recursion,” each instance of the call has its own set of so-called “local” variables.

Thus, any sub can, within a loop controlled by a local variable, call any other sub, including itself, and it Just Works.™

[pemungkah]

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.