• The code you write is more elgant (cleaner) and will be easier to maintain and less likely to contain obscure bugs that are hard to track down.

This isn't always true. In general, recursive solutions tend to be more abstract rather than elegant (Although my definition of elegant is "efficient and concise", which isn't the same as everyone else's definition).

• Recursion is a memory and resource HOG. It's much more efficient to code the solution using global variables.

I'm not quite sure what you mean here. Recursive subs can use global variables the same way as any sub can. Do you mean to compare recursive vs non-recursive? (i.e. a recursion algorithm implemented with a recursion solution as opposed to being implemented with a pure iterative solution) In general, an iterative solution will be much faster and much easier to work with after it is complete; however, an iterative solution might be much more difficult to write, since a recursion allows you to think more abstractly about a problem.

I guess that in your case, the real questions are:

1. Is performance a problem and/or goal?
2. If so, does performance hit outweigh code readability?

With Perl, this is a pretty big deal. Perl needs to save a heck of a lot of stuff on the stack when doing a recursive call, making a recursive algorithm proportionally much, much slower in Perl than in another langauge, say, C (slower than normal, I mean). In my opinion, if you're hitting the "deep recursion" warning, then it is probably a good idea to see if there are some areas that can be done more efficiently by flattening the recursion.

Just my 2 cents, anyways.

This isn't always true. In general, recursive solutions tend to be more abstract rather than elegant (Although my definition of elegant is "efficient and concise", which isn't the same as everyone else's definition).

I believe that's a matter of opinion, but point taken.

I'm not quite sure what you mean here. Recursive subs can use global variables the same way as any sub can.

Sure they can use globals, but that's not the recursive part. I agree with the remainder of your response though. You just said it better than I did.

With Perl, this is a pretty big deal.

Agreed, as long as you take into context the power of the machine its running on. That makes both C and Perl speed relative.

Overall, I like you comments. You added a lot of clarity that I didn't express very well.

In my opinion, though I am known to be biaised towards FP programming, which is lovely to do in Perl, recursion is not so much of a memory hindrance problem when one can manage to produce a tail-call optimized pureFP algorithm.

In such situations, and for non-trivial algorithms only, one may find that the straight FP algorithms are often much more cleaner, clearer and performant, in terms of CPU cycles, than their derecursived iterative counterparts.

Also, it should be added that, apart from trivial algorithms, deriving functionally identical iterative algorithms may often prove to be a hell of a call!

Then when reached, the iterative solutions, when they are correct (try to prove the correctness of such iterative algorithms!), are unfortunately often not only far from being trivial to understand (not to mention to debug and maintain) but also much less efficient, due to the necessity to often simulate within the language external constructs the recursion stack which is otherwise naturally managed internally by the language engine.

Check these facts on the famous simple Hanoi Tower problem !

1. RECURSIVE METHOD (straightforward)

sub hanoi {
    my ($n, $a, $b, $c) = @_;
    
    return if $n < 1;

    hanoi($n-1, $a, $c, $b);
    print "Moving plate from $a to $b\n";
    return hanoi($n-1, $c, $b, $a);
}

-- Example of call
$ hanoi(8, "A", "B", "C")
=> 2^8 - 1 moves
    
-- Comment
   $n is the number of plates (> 0) to move
   from pole A to pole B using auxiliary pole C 
   
   The final 'return' allows for a slight
   tail-call optimization
[download]

2. ITERATIVE METHOD (my best solution so far)

##
# hanoi n a b c
# Without recursivity nor goto.
# Franck PORCHER

use constant log_2 => log(2);

sub hanoi {
   my ($n, $a, $b, $c) = @_;

   my $p = 1;
   my $k;

   do {
      if ( $n ) {
         $p <<= $n;
         ($b, $c) = ($c, $b) if ($n & 1);
         $n = 0;
      }

      if ( ($p - 1) && ( $p & 1) ){
         $k   = log(($p ^ ($p + 1)) & ($p + 1)) / log_2;
         $p >>= $k;
         ($a, $b) = ($b, $a) if ($k & 1);
         $n += $k;
         $p ||= 1;
      }
 
      if ( $p - 1 ) {
         print "Moving plate from $a to $b\n";
         ($a, $b, $c) = ($c, $a, $b);
         $p++;
      }

   } while $p - 1;
}

-- Example of call
$ hanoi(8, "A", "B", "C")
=> 2^8 - 1 moves
[download]

Question: who feels out there that this last iterative version of Hanoi problem is trivial and self-explanatory ?

There are many problem much more complicated than that out there for which we are happy to be able to provide straight purely functional recursive algorithms, easy to write, and easy to prove correct !

Franck PORCHER, PhD
franck.porcher@gmail.com

Recursion is well suited only for depth-first and iterative deepening depth-first search strategies.

Once you advance pass toy problems as the Towers of Hanoi and start solving problems that require better strategies, you learn that just using directly the built-in support for recursion on the language to implement a search (or some other related operations) is not always a good idea because then, later, there is no way to change the algorithm without rewriting it fully.

A more open approach is to keep the state of the explored problem space in an explicit data-structure (in contra-position to keeping it implicitly on the language stack as built-in recursion does). Then, you can change the search strategy just changing that data structure (i.e. FIFO => breadth-first, LIFO => depth-first, queue => best-first, etc.)

Note that I don't see a great difference between iteration and linear-recursion, as they are equivalent, even if sometimes expressing an algorithm in the recursive way is simpler. For me the breaking point is having unbounded tree-like recursion or not.

In the particular case of your iterative implementation of the Towers of Hanoy that's utterly complex, the problem is that you are being too clever. You are avoiding to keep the state because for that particular problem it is possible to derive it just from the iteration counter.

Also, the strategy you use to solve the problem is hard-coded. What would happen if for instance, there were 4 sticks instead of 3, could you modify it to provide the best solution (that which minimizes the number of moves) easily? what if every disk could only be placed in a given subset of the sticks?