no warnings 'recursion';
within the same scope as that code (use a naked block if you have/need to), provided you're sure that you wish to silence those warnings (more complete example in readmore).
Cheers.
BazB.
Update: Added useful(-ish) example.
If the information in this post is inaccurate, or just plain wrong, don't just downvote - please post explaining what's wrong.
That way everyone learns.
| [reply]
[d/l]
[select] |
From perldiag (you can get these explanations for error messages automatically using use diagnostics;):
Deep recursion on subroutine "%s"
(W recursion) This subroutine has called itself (directly or indirectly) 100 times more than it has returned. This probably indicates an infinite recursion, unless you're writing strange benchmark programs, in which case it indicates something else.
Update: changed 'use warnings' to 'use diagnostics', which is what I meant, as jsprat pointed out later...
| [reply]
[d/l] |
If you are expecting deep recursion, you can use no warnings 'recursion'; to suppress that warning. Use it in the smallest possible scope. Full details are in perllexwarn.
BTW, I think jasonk meant to say use diagnostics; (not use warnings) to have perl look up the long winded definition for you. | [reply]
[d/l]
[select] |
Is deep recursion bad?
Yes and no.
No, it's not bad because:
- In general, recursion is a very elegant solution to a lot of tree-walking and other, similarly structured problems.
- 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.
Yes, it is bad because:
- Recursion is a memory and resource HOG. It's much more efficient to code the solution using global variables.
Like most things, there is a trade off between the two. I guess that in your case, the real questions are:
- Is performance a problem and/or goal?
- If so, does performance hit outweigh code readability?
And of couse performance is a relative term in itself. What is a performance issue on my old 486 with a whoping 16MB of RAM is not an issue on my 1Ghz iMac with half a gig of RAM. | [reply] |
-
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:
- Is performance a problem and/or goal?
- 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.
| [reply] |
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.
| [reply] |
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
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
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
| [reply]
[d/l]
[select] |
There was a great article in Dr. Dobb's Journal recently entitled: "Considering Recursion" that explored many of these issues. Unfortunately this article is not free to download, but you could pay to download it or find a copy somewhere. Here's the link. | [reply] |
