深度递归与尾递归性能优化问询：Perl实现性能异常分析

我在Perl中实现了一个基于树形结构的深度递归算法：

• 算法深度约100层，节点分支数为1至5个，每次迭代最多发起700-800次调用
• 初始深度递归实现耗时20秒，通过no warnings 'recursion'屏蔽递归警告
• 改为尾递归子程序后耗时反而增至32秒，进一步调整为while风格尾递归后耗时仍为32秒

递归方法性能较差的核心原因之一是每个分支都需要检查$diagonal_board[$Y][$j]的布尔值；此前尝试的启发式方法无需该检查，耗时仅13秒，但代码混乱、逻辑繁杂且无明确终止条件。

我尝试了三种递归实现方式（深度递归、尾递归子程序、while风格尾递归），这些实现代码简洁清晰、终止条件明确，但性能始终不及启发式方法。当前基准测试基于约5万次调用，最终需支持百万级调用规模；我用C实现的基础while风格尾递归耗时仅1秒，未达到C比Perl快50倍的普遍预期，显然我对尾递归和子程序开销存在误解，现寻求递归版本的性能优化方案及认知纠正。

相关代码如下：

sub recursive_flow_current() {
    my $wire_in = $loop[0][0][0];
    our @diagonal_board;    # @diagonal_board[cable][wire] c.f. @wire[cable][wire] for heuristic
    our @flow_stack;

    # clear all cable/wire
    for my $i (0..25) {
        for my $j (0..25) {
            $diagonal_board[$i][$j] = 0;
        }
    }

=ccc (deep recursion)
    &flow($test_register, $wire_in);
    &flow($wire_in, $test_register);    # diagonal board

    sub flow($$) {    # flow from $diagonal_board[cable][wire]
        my ($X, $i) = @_;    # cable, wire
        $diagonal_board[$X][$i] = $diagonal_board[$i][$X] = 1;

        foreach my $Y ( @{ $star_X[$X] } ) {
            foreach my $n ( @{ $star_XY[$X][$Y] } ) {    # keys %hash takes longer than pre-calculated @list
                my $j = $scramblers[$n][$i];
                unless ($diagonal_board[$Y][$j]) {
                    &flow($Y, $j);
                    &flow($j, $Y);    # diagonal board
                }
            } # end n
        } # end Y
    } # end sub flow (also end X)
=cut

=ccc (tail recursion using subroutine)
    unshift @flow_stack, $test_register, $wire_in, $wire_in, $test_register;     # first in last out
    &flow();

    sub flow() {    # tail recursion using subroutine
        return unless @flow_stack;
        my ($X, $i) = splice @flow_stack, 0, 2;    # shift 2 elements at once
        $diagonal_board[$X][$i] = $diagonal_board[$i][$X] = 1;

        foreach my $Y ( @{ $star_X[$X] } ) {
            foreach my $n ( @{ $star_XY[$X][$Y] } ) {
                my $j = $scramblers[$n][$i];
                unless ($diagonal_board[$Y][$j]) {
                    unshift @flow_stack, $Y, $j, $j, $Y;    # 1-D array is faster than a 2-D array
                }
            } # end n
        } # end Y
        goto &flow;
    } # end sub flow (also end unless)
=cut

### =ccc (tail recursion with a while style loop)
    unshift @flow_stack, $test_register, $wire_in, $wire_in, $test_register;    # add two elements

    STACK:
        my ($X, $i) = splice @flow_stack, 0, 2;    # use one elements
        $diagonal_board[$X][$i] = $diagonal_board[$i][$X] = 1;

        foreach my $Y ( @{ $star_X[$X] } ) {
            foreach my $n ( @{ $star_XY[$X][$Y] } ) {
                my $j = $scramblers[$n][$i];
                unless ($diagonal_board[$Y][$j]) {
                    unshift @flow_stack, $Y, $j, $j, $Y;   # add two elements
                }
            } # end n
        } # end Y
        goto STACK if exists $flow_stack[0];    # tail recursion if @flow_stack not empty
### =cut
}

我希望使用简洁清晰的递归实现，并将其性能优化至最优水平。

内容的提问来源于stack exchange，提问作者Chan Tai Man