There's more than one way to do things PerlMonks

### Re: Recursion Alternatives?

by Arguile (Hermit)
 on Feb 27, 2003 at 06:14 UTC ( #239019=note: print w/replies, xml ) Need Help??

“Recursion is beautiful, but computers don't really grok beauty.”
-- Larry Wall

Unfortunately this is true of Perl. While Perl 6 still holds some hope for tail-recursion optimisation, there’s no way to get the performance and elegance in Perl 5.

### Tail Recursion

Tail recursion is signified by the recursive call being last executed statement. It can match iterative algorithms for speed and space usage as there is no unwinding phase needed, so the same stack frame can be used repeatedly instead of pushing another one on each call.

In your above code (repeated below) you used straight recursion.

```    # A classic, recursive soulution.
sub Rfactorial {
my \$i = shift;
return 1 if \$i == 0;
return 1 if \$i == 1;
return \$i * Rfactorial(\$i - 1);
}

Compare that to the same function rewritten in a tail recursive manner.

```    # Tail recursive
sub factorial {
my \$n = shift;
return 0 unless \$n > 0;
fact( \$n, 1 );

sub fact {
my(\$n, \$a) = @_;
return \$a unless \$n > 1;
fact( \$n-1, \$n*\$a );
}
}

With an optimising compiler the tail recursive version would be comparable to an iterative approach in performance, while retaining it’s (arguable) elegance. This particular example doesn't look much easier or more elegant, but it can be.

As stated above though, Perl doesn’t optimise any form of recursion. So the best bet is to write it in some iterative fashion if you want performance.

(1) I didn’t bother trying to keep the fact() sub local for reasons of claity

Replies are listed 'Best First'.
Re^2: Recursion Alternatives?
by adrianh (Chancellor) on Feb 27, 2003 at 10:49 UTC

You can "optimise" out the stack frame in tail recursive code in perl5 using goto. E.g.:

```sub fact {
my(\$n, \$a) = @_;
return \$a unless \$n > 1;
@_ = (\$n-1, \$n*\$a);
goto &fact;
}

However, this is so wildly slow it's rarely worth the effort :-)

If perl6 doesn't manage to do tail-recursion optimisation I hope we at least get an efficient way to throw away a call-stack level so we can code it by hand.

Create A New User
Node Status?
node history
Node Type: note [id://239019]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others contemplating the Monastery: (14)
As of 2017-06-27 15:11 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
How many monitors do you use while coding?

Results (609 votes). Check out past polls.