develooper Front page | perl.perl5.porters | Postings from January 2001

Can Perl do tail recursion?

Thread Previous | Thread Next
From:
Ben Tilly
Date:
January 24, 2001 11:09
Subject:
Can Perl do tail recursion?
Message ID:
LAW2-F232ekDQqj3Upz00001418@hotmail.com
I know it doesn't do it by default, but documentation
in various places (including perlfunc, and
http://perl.plover.com/book/announce/02 led me to think
that you could force it.  But the following example does
not seem to show the hope-for speedup of tail recursion:

print sum(1..20_000);

sub sum {
  my $count = @_;
  unless ($count % 100) {
    print "At $count args\n";
  }
  if (@_ > 1) {
    unshift @_, shift() + shift();
    goto ∑
  }
  else {
    return shift;
  }
}

The slowness then characteristic speedup as @_ shrinks
indicates that tail recursion is not happening.  I
verified that it is not due to the operations that
am doing by comparing with:

print test_shift(1..20_000);

sub test_shift {
  while (@_) {
    my $count = @_;
    unless ($count % 100) {
      print "At $count args\n";
    }
    if (@_ > 1) {
      unshift @_, shift() + shift();
    }
    else {
      return shift;
    }
  }
}

So does anyone know why it doesn't work (5.005) and are
there plans to make it work efficiently some day?

BTW at least one person who tried on 5.6 indicated that
there that the first version ran out of memory.  The
first at least managed to keep memory usage down even if
it was slow...

Thanks,
Ben
_________________________________________________________________
Get your FREE download of MSN Explorer at http://explorer.msn.com


Thread Previous | Thread Next


nntp.perl.org: Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at ask@perl.org | Group listing | About