|
Re: Tail recursion elimination
by Limbic~Region (Chancellor) on Apr 29, 2006 at 14:02 UTC
|
| [reply] |
|
|
| [reply] |
|
|
| [reply] |
|
|
|
|
|
|
|
|
Thanks for the link!
The topic has some history obviously.
Update:
"tail recursion elimination", yeah, I guess I kind of made that up, I meant something like "elimination of the stack overhead of tail recursion".
Bill H
perl -e 'print sub { "Hello @{[shift]}!\n" }->("World")'
| [reply]
[d/l] |
Re: Tail recursion elimination
by diotalevi (Canon) on Apr 28, 2006 at 19:48 UTC
|
It's not an error, it's just a warning and you'd do better to just turn it off with no warnings 'recursion' than to do this ugly thing you just posted. I'm sure there's a valid reason to use goto &{...} to get around recursion in perl but I haven't seen it yet.
| [reply]
[d/l] |
|
|
There's a very good reason to eliminate tail recursion (in any language): to save memory if the recursion runs deep. Unfortunately, it only works when you have tail recursion.
The other "unfortunately" is that, at least the last time I checked, goto& was slower than recursing.
We're building the house of the future together.
| [reply]
[d/l] |
|
|
You appear to have misunderstood. I didn't say that eliminating recursion was bad, I said that using goto &{...} nearly always is. There are probably better ways to do this in perl but one of the "best" ways I know of is to just go back to the top of the routine after setting @_ with the new args. For short routines and such.
sub foo {
{
...
# Recurse but without actually calling foo() again.
@_ = ...;
redo;
}
}
I also expect that there are better ways to save on memory than eliminating stack frames. | [reply]
[d/l]
[select] |
|
|
|
|
Ugly! :-)
Ok, I admit I wasn't aware that the warning could be disabled, but in any case for truly deep recursion, such as when continuation passiing, you might want to do this rather than actually running out of memory/stack.
Bill H
perl -e 'print sub { "Hello @{[shift]}!\n" }->("World")'
| [reply]
[d/l] |
|
|
Well maybe it's not that wise to advertise my worst node ever, since it has already been heavily donwvoted, but in it I had a program meant to run indefinitely and to alternate two "phases": a sleeping one and active one. Their respective behaviour was implemented with a pair of subs switching one another upon a certain condition through a magical goto. There may be more serious situations in which a similar scheme could be desirable, I guess.
| [reply] |
Re: Tail recursion elimination
by TedPride (Priest) on Apr 30, 2006 at 00:48 UTC
|
Aren't tail recursions easily eliminated through use of a loop? You don't need to store the values currently in any of the variables, so you can just replace them:
use strict;
use warnings;
my $p = 0;
$p = { 'value' => 5, 'next' => $p };
$p = { 'value' => 4, 'next' => $p };
$p = { 'value' => 3, 'next' => $p };
$p = { 'value' => 2, 'next' => $p };
$p = { 'value' => 1, 'next' => $p };
display1($p);
display2($p);
sub display1 {
my $p = $_[0];
return if !$p;
print $p->{'value'}, ' ';
display1($p->{'next'});
}
sub display2 {
my $p = $_[0];
while ($p) {
print $p->{'value'}, ' ';
$p = $p->{'next'};
}
}
It's recursive calls elsewhere in the code, or branching recursion, that's more complicated. However, this can still be handled by substituting a stack for the recursion:
sub display1 {
my $p = $_[0];
return if !$p;
display1($p->{'next'});
print $p->{'value'}, ' ';
}
sub display2 {
my $p = $_[0];
my @stack;
while ($p) {
push @stack, $p;
$p = $p->{'next'};
}
while ($p = pop @stack) {
print $p->{'value'}, ' ';
}
}
I don't see why trying to fool Perl into working around the "deep recursion" is a good idea. If your recursion is that deep, you're doing something wrong. For instance, if you're trying to use quicksort on an already sorted array, then you could start by scrambling the array, or substitute a different algorithm. You would NOT try to fool Perl into letting you go thousands of levels deep.
| [reply]
[d/l]
[select] |
|
|
If your recursion is that deep, you're doing something wrong.
I don't think you can (validly) say that. It totally depends on the
algorithm. Quite often it depends on the data structure.
You may as well say if you have a tree that's more than 100 levels
deep, you're doing something wrong. Preposterous.
You would NOT try to fool Perl into letting you go thousands of levels deep.
It's not a matter of "fooling Perl". The deep recursion warning is there to
alert you just in case you have a runaway recursion.
We're building the house of the future together.
| [reply] |
|
|
Of course maintaining your own stack is often a valid alternative, and might even have benefits in that you can do direct stack manipulations, but it's starting to sound like a register machine implementation at that point and many people won't want to go that far.
Bill H
perl -e 'print sub { "Hello @{[shift]}!\n" }->("World")'
| [reply]
[d/l] |
|
|
Aren't for-loops/while-loops easily eliminated through use of a goto? I don't see why trying to fool Perl into working around "gotos" is a good idea. If your goto is that complicated, you're doing something wrong. You would NOT try to fool Perl into letting you use for-loops.
| [reply]
[d/l] |