Re^3: Is deep recursion bad?

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

Comment on Re^3: Is deep recursion bad? Select or Download Code

Replies are listed 'Best First'.
Re^4: Is deep recursion bad? by salva (Canon) on Feb 13, 2015 at 13:26 UTC
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?	[reply]
Re^5: Is deep recursion bad? by Anonymous Monk on May 09, 2015 at 11:00 UTC
Hi, That's exactly my point, which you seem to be missing. I'm nowhere trying to be smart, but only to show that even for a simplistic problem as the classical 3-poles Hanoi Tower, getting an iterative solution than does better than the iterative counterpart, that is NOT mimic a call stack in any way (since in that event, you better off with the recursive approach in the first place), is a hell of a proposition, as you can see (my personal solution, not yet published, does not use a stack, is sound by design, but utterly complex). Therefore this is my point : general recursive functions (whether implemented thru the built-in support of the language or thru functional continuations to render the stack explicit and provide potential for applying various traversal strategies) are not only powerful in their abilities to capture complex algorithms, but sometimes unavoidable when the iterative counterpart (which does not mimic a stack) is too complex or even not known (egAckerman iterative is not known). In conclusion, one should not conceive recursion as limited to what built-in support actual languages offer, but as an abstract conceptual tool, as it is with pure FP. This is the point I wanted to emphasize on a simple example. Cheers	[reply]