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

In reply to Re^3: Is deep recursion bad? by Anonymous Monk
in thread Is deep recursion bad? by ezekiel

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.