你说得对，Perl不执行尾递归优化。
如果你有尾递归，你可以自己进行优化。但是话说回来，你没有尾递归。递归调用之后紧跟着一个加法。
因此让我们从将子程序改为只有尾递归开始。这可以通过向前传递执行最后一次操作所需的信息来完成。
sub _sum {
my ($acc, $first, @rest) = @_;
$acc += $first;
return @rest ? _sum( $acc, @rest ) : $acc;
}
sub sum {
my (@rest) = @_;
return undef if !@rest;
return _sum( 0, @rest );
}
现在我们可以进行尾调用优化。
- 将递归子例程的主体放置在一个无限循环中。
- 用
do { @_ = ...; next; }替换recurse(...)。
首先是在辅助函数中。
sub _sum {
while (1) {
my ($acc, $first, @rest) = @_;
$acc += $first;
if (@rest) {
@_ = ( $acc, @rest );
} else {
return $acc;
}
}
}
sub sum {
my (@rest) = @_;
return undef if !@rest;
return _sum( 0, @rest );
}
然后在主子程序中。
sub sum {
my (@rest) = @_;
return undef if !@rest;
@_ = ( 0, @rest );
while (1) {
my ($acc, $first, @rest) = @_;
$acc += $first;
if (@rest) {
@_ = ( $acc, @rest );
} else {
return $acc;
}
}
}
完成了。
...有点。现在我们可以执行很多其他的清理和优化。
让我们从改善流程开始。
sub sum {
my (@rest) = @_;
return undef if !@rest;
@_ = ( 0, @rest );
while (1) {
my ($acc, $first, @rest) = @_;
$acc += $first;
return $acc if !@rest;
@_ = ( $acc, @rest );
}
}
不需要在循环中每次创建一个新的 $acc。
sub sum {
my (@rest) = @_;
return undef if !@rest;
my $acc = 0;
while (1) {
my ($first, @rest) = @_;
$acc += $first;
return $acc if !@rest;
@_ = @rest;
}
}
不再需要使用@_了。
sub sum {
my (@rest) = @_;
return undef if !@rest;
my $acc = 0;
while (1) {
(my $first, @rest) = @rest;
$acc += $first;
return $acc if !@rest;
}
}
让我们使用更经济的列表赋值替换它。
sub sum {
my (@rest) = @_;
return undef if !@rest;
my $acc = 0;
while (1) {
my $first = shift(@rest);
$acc += $first;
return $acc if !@rest;
}
}
让我们简化循环。
sub sum {
my (@rest) = @_;
return undef if !@rest;
my $acc = 0;
while (@rest) {
my $first = shift(@rest);
$acc += $first;
}
return $acc;
}
我们可以用更便宜的foreach循环来替换while循环。
sub sum {
my (@rest) = @_;
return undef if !@rest;
my $acc = 0;
for my $first (@rest) {
$acc += $first;
}
return $acc;
}
$first和@rest不再是合适的变量名。在此过程中，我们将消除一个无用的 @_ 的副本。
sub sum {
return undef if !@_;
my $acc = 0;
$acc += $_ for @_;
return $acc;
}
如果我们将
$acc初始化为
undef，则不再需要进行初始检查。
sub sum {
my $acc;
$acc += $_ for @_;
return $acc;
}
达达！
goto语句。 - ShawnList::Util中的reduce函数，它执行左折叠。或者用循环实现。如果想要尝试 TCO 和深递归，可以使用其他语言（我比较偏爱 Scheme）。这不是 Perl 擅长的领域。但是，这里有一个例子，展示了如何在 Perl 中使用基于goto的尾调用。 - ShawnList::Util中的reduce和sum以及循环。我的问题是如何在Perl中实现TCO（尾递归优化），如果可能的话。 - Miroslav Popov