Performance of deep recursion versus tail recursion

Question

I have an algorithm using deep recursion (20 seconds). Perl complains and I shut it up with "no warnings 'recursion'". I change it to tail recursion (32 seconds) in the hope that it will be quicker. However the result is the opposite. In another attempt to cut the run time by reducing the overhead of calling subroutines, I change tail recursion using subroutine to tail recursion with a while style loop (32 seconds). The result is about the same. It is basically a tree where each node has one or two to less than about six branches. It is about a hundred levels deep, give or take. Each iteration makes 700-800 calls maximum.

One thing, that makes recursive approach slow, is that I need to check if $diagonal_board[$Y][$j] is TRUE or FALSE. Whereas, in a previously tried heuristic method, I do blindly without checking at each branch.

I must get them very wrong on tail recursion and subroutine overhead. Any ideas to make an improvement and/or correcting my misconceptions are welcome.

P.S. Incidentally, before all these, the first approach, that I used, was using heuristics (13 seconds). I do it blindly. I am looking for a particular pattern at the output of a 26x26 matrix. If that pattern doesn't emerge, I loop more and again blindly. This approach has a bunch of spaghetti code. It is not as clean or as concise as any of the three versions of the recursion method. The latter has a definitive end condition.

I have been looking at Tail recursion vs non tail recursion. Is the former slower? (s/he found tail recursion slower too), Tail recursion vs non tail recursion and Tail recursion vs recursion . I wasn't able to apply them to my situation.

P.P.S. The above benchmarks were taken against about 50,000 calls. Eventually, I need about 1 million calls at each go. My rudimentary C implementation using a while style tail recursion took about 1.0 second. It is not as good as the usually quoted value that C is about 50 times faster than Perl. I need to work on my algorithm. I need to know more about tail recursion optimisation.

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

I tried two methods. Firstly, I used a heuristic method. It is the fastest, but the code is complicated. It is a mess. Secondly, I have also tried three different versions of a recursive approach. The code is short, clean and easy to understand. I wish to use some form of recursion and make it the fastest.