perl - 如何重构 for 循环中发生的递归以使其成为尾调用？

Question

考虑递归子程序 append_until_exhausted .递归发生在主体的中间。我想把它放在最后进行进一步处理，也就是说一个简单的尾调用(没有任何优化，在 Perl 中通常涉及 goto)。除了子例程和两个辅助子例程的签名之外，您可以更改任何内容。
涉及数字的算法看起来很愚蠢，因为是我真实代码的浓缩/混淆，但子程序调用的代码执行路径/结构没有改变。

use 5.032;
use strictures;
use experimental qw(signatures);

# Returns mostly one value, sometimes multiple,
# and an occasional end condition which will cause
# the recursion to end because then the for loop will
# iterate over an empty list.
# This sub is also called from elsewhere,
# do not change, do not inline.
sub some_complicated_computation($foo) { # → ArrayRef[$foo]
    return [] if $foo > 45;
    return $foo % 5
        ? [$foo + 1]
        : [$foo + 2, $foo + 3];
}

# do not inline
sub make_key($foo) { # → Str
    chr(64 + $foo / 5)
}

sub append_until_exhausted($foo, $appendix) { # → HashRef[ArrayRef[$foo]]
    my $computed = some_complicated_computation($foo);
    for my $new_foo ($computed->@*) {
        {
            push $appendix->{make_key $new_foo}->@*, $new_foo;
        }
        __SUB__->($new_foo, $appendix);
    }
    return $appendix;
}

my $new_appendix = append_until_exhausted(
    7, # start value for foo
    { dummy => [], dummy2 => [], dummy3 => [], }
);

这里的目标是让我理解原理，以便我可以在类似的情况和类似的语言中应用它。如果您建议使用一些 {Sub::*, B::*, XS} 魔法，这无济于事。

Answer 1

由于您的递归调用在循环内，您不能使您的函数尾递归。那么，当some_expensive_computation返回 0 或 1 个元素，您可以，但是一旦返回两个，就结束了。
我建议改用堆栈。基本上，改变你的子 append_until_exhausted到:

sub append_until_exhausted_stack($init_foo, $appendix) { # → HashRef[ArrayRef[$foo]]
    my @stack = ($init_foo);
    while (@stack) {
        my $foo = pop @stack;
        my $computed = some_complicated_computation($foo);
        for my $new_foo (@$computed) {
            push @{$appendix->{make_key $new_foo}}, $new_foo;
        }
        push @stack, @$computed;
    }
    return $appendix;
}

小警告:它不会按照与原始函数相同的顺序执行工作。如果这对您很重要，那么请参阅池上的 answer .
我很快对它进行了基准测试，它似乎比递归实现快了不到 10%，所以不是那么多。基准代码如下:

sub append_until_exhausted($foo, $appendix) { # → HashRef[ArrayRef[$foo]]
    my $computed = some_complicated_computation($foo);
    for my $new_foo (@$computed) {
        {
            push @{$appendix->{make_key $new_foo}}, $new_foo;
        }
        __SUB__->($new_foo, $appendix);
    }
    return $appendix;
}


sub append_until_exhausted_stack($init_foo, $appendix) { # → HashRef[ArrayRef[$foo]]
    my @stack = ($init_foo);
    while (@stack) {
        my $foo = pop @stack;
        my $computed = some_complicated_computation($foo);
        for my $new_foo (@$computed) {
            push @{$appendix->{make_key $new_foo}}, $new_foo;
        }
        push @stack, @$computed;
    }
    return $appendix;
}

use Benchmark qw(:all);

cmpthese(2000, {
         'Recursive' => sub {
             append_until_exhausted(7, { dummy => [], dummy2 => [], dummy3 => [] })},
         'Stack'   => sub {
             append_until_exhausted_stack(7, { dummy => [], dummy2 => [], dummy3 => [] })},
         });

这产生以下结果:

            Rate Recursive     Stack
Recursive 1384/s        --       -8%
Stack     1505/s        9%        --

我尝试通过添加特殊情况来优化它，以避免将某些内容插入堆栈并立即将其删除，但这几乎不会影响性能(例如，在 $foo = $computed->[0]; redo 时执行 @$computed == 1 )。不过，可能值得尝试使用您的实际代码。