Beefy Boxes and Bandwidth Generously Provided by pair Networks
Just another Perl shrine

Re: Recursion Alternatives?

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

in reply to Recursion Alternatives?

“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.

See Also

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

Comment on Re: Recursion Alternatives?
Select or Download Code
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.

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://239019]
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others avoiding work at the Monastery: (5)
As of 2014-11-01 10:33 GMT
Find Nodes?
    Voting Booth?

    For retirement, I am banking on:

    Results (229 votes), past polls