Tail-recursion in perl?!

neniro has asked for the wisdom of the Perl Monks concerning the following question:

This one causes headaches to me:

#!/usr/bin/perl 

use strict;
use warnings;

print "iterFac_for:\t", iterFac_for(6), "\n";
print "recFac:\t\t",       recFac(6),      "\n";
print "iterFac:\t",       iterFac(6),     "\n";
exit;

sub iterFac_for {            # straight iterativ (perl-style)
    my ($max, $val) = (shift, 1);
    $val *= $_ for (1..$max);
    return $val;
}

sub recFac {                # linear recursive
    my $n = shift;
    return 1 if $n == 1;
    $n *= recFac($n-1);
}

sub iterFac {                # linear iterativ but recursive defined?!
    my $max = shift;
    my $val = shift || 1;
    my $cnt = shift || 1;

    return $val if $cnt > $max;
    iterFac( $max, $val*$cnt, ++$cnt );
}
[download]

As you can see, all of those functions calculates factorial of a given number. The first is the way I would solve this kinda task in perl, the second one is recursive and I would say using recursion in this case is deprecated (even if it isn't so bad as calculating fibonacci-numbers recursive) and the last one is linear iterative but recursive defined. I found it in the SICP-book http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.1 and choosed to code it in perl instead of scheme. What gives me a headache is what they say about the implementation in scheme allows tail-recursion for the last function, that means it doesn't create an overhead on the stack for each recursive call of this function. Is there something similar in perl, or is it useless cause we have different ways to build iterative functions (as my first example)?

Comment on Tail-recursion in perl?! Download Code

Replies are listed 'Best First'.
Re: Tail-recursion in perl?! by TimToady (Parson) on Jul 09, 2005 at 15:20 UTC
You can emulate tail recursion in Perl 5, but it's not terribly efficient either in notation or in performance. But I wouldn't call it "deprecated"... more like "preprecated". Perl 6 is specced to support automatic tail recursion elimination, and in fact, I believe your examples already work in Pugs, the bootstrap implementation of Perl 6.	[reply]
Re: Tail-recursion in perl?! by Tanktalus (Canon) on Jul 09, 2005 at 14:55 UTC
I think this is what you want: `#! perl -w use strict; use diagnostics; use Carp; sub iterFac { my $max = shift; my $val = shift \|\| 1; my $cnt = shift \|\| 1; Carp::cluck("we are currently here:"); return $val if $cnt > $max; #iterFac($max, $val$cnt, ++$cnt); @_ = ($max, $val$cnt, ++$cnt); goto &iterFac; } my $x = iterFac(5); print "Factorial 5 = $x\n";` [download] Note how I've used Carp::cluck to show where we are at all times. If you remove the # from the iterFac call and comment out the @_ assignment and the goto, and run this, you'll see how it cluck's that it gets 5 subroutine calls deep. But as-is, the cluck always shows only a single subroutine deep. I think that's what you're looking for, but someone with an actual CS degree may show me wrong ;-)	[reply] [d/l]
Re: Tail-recursion in perl?! by Fletch (Bishop) on Jul 09, 2005 at 14:47 UTC
Higher Order Perl (ISBN 1558607013) discusses tail recursion in Perl. The electronic version's not online yet but you can get the relevant page numbers in the print edition with the full text search. -- We're looking for people in ATL	[reply]
Re: Tail-recursion in perl?! by pg (Canon) on Jul 09, 2005 at 19:28 UTC
"Is there something similar in perl, or is it useless cause we have different ways to build iterative functions (as my first example)?" In this sense, Perl is no different from other languages, especially c-group languages. Although not all languages have the "$val *= $_ for (1..$max);" syntax, this syntax didn't express any logic that can not be easily expressed otherwise. Use recursion is not "deprecated", but rather unneccessary in this particular example. This recursion version can be found almost in all text books, not because it is the best way to code this particular logic, but it is probably the best example one can use to demo recursion.	[reply]
Re: Tail-recursion in perl?! by jonadab (Parson) on Jul 10, 2005 at 01:21 UTC
This recursion version can be found almost in all text books, not because it is the best way to code this particular logic, but it is probably the best example one can use to demo recursion. A better example would be quicksort. The reason I say it's better is because it demonstrates how recursion is a more natural way to think about certain problems. With the factorial example, the iterative version is at least as easy to follow as the recursive version, but with quicksort the recursive version is MUCH easier to understand. Perhaps an even better example would be a depth-first traversal of a general tree.	[reply]
Re: Tail-recursion in perl?! by mvaline (Friar) on Jul 10, 2005 at 04:56 UTC
I had the same question (Iterative vs Recursive Processes) when I was working through SICP. There is some good discussion to read through in the comments on my post.	[reply]
Re^2: Tail-recursion in perl?! by neniro (Priest) on Jul 10, 2005 at 08:28 UTC
Thank you, that discussion is very usefull and detailed.	[reply]
Re: Tail-recursion in perl?! by anonymized user 468275 (Curate) on Jul 10, 2005 at 13:05 UTC
All these solutions contain the same essential steps, but the first one (no recursion) has no unnecessary extras. The only way I can imagine doing better on long-term performance would be for a persistent program to maintain previously requested results in a hash, which can be looked up instead of calculated; but that seems way overkill. One world, one people	[reply]
Re^2: Tail-recursion in perl?! by Tanktalus (Canon) on Jul 10, 2005 at 16:43 UTC
We all can disagree what constitutes overkill. But someone has gone a step further, and generalised persistant programs' ability to remember previously requested results. Check out Memoize ("trade space for time"). It inserts itself into the call-stream somewhat magically, and detects function calls that are identical, and returns the previously-computed value for the same input. Of course, this only makes sense when the same input always results in the same output, as it would here. This can really speed up recursive results to the point where, for some functions, the recursively-computed value is faster than the iterative. And, of course, Memoize can help simplify non-recursive functions as well. It does require a bit of caution to ensure that there are no side effects possible on a function, though. [time elapses...] Oddly, Memoize has a bunch of add-ons that I just saw when I checked it out on CPAN (to ensure I got the link correct above) which allows this to work even for non-persistant programs. That merits some more thought. Man, do I love perl. This would be incredibly programmer-intensive in basically any other language. But in perl, someone did it already, and I can just use it. That's too cool.	[reply]


Think about Loose Coupling
	PerlMonks